Let $p$ be a prime number with $N$ bits, let $a,b,c$ be constants. The problem is to find solutions to the equivalent $a x + b y \equiv c \pmod p$ with both having at most $N/2$ bits.
What algorithmic approaches can solve this problem? Does it have any known hardness reduction?
You can use lattice reduction to solve this problem.
Pick a large constant $S\in\mathbb Z$ and consider the lattice spanned by the rows of the following matrix: $$ L = \begin{pmatrix} S a & -1 & 0 & 0 \\ S b & 0 & -1 & 0 \\ S c & 0 & 0 & S \\ S p & 0 & 0 & 0 \\ \end{pmatrix} $$
Now the crucial thing to notice is that some pair $(x,y)\in\mathbb Z^2$ is a solution to your modular equation if and only if $(0,x,y,S)$ is a vector in this lattice.
Moreover, some vector of the form $\vec v=(Sz,x,y,\pm S)$ must be part of a short basis, since $\begin{pmatrix}S c & 0 & 0 & S\end{pmatrix}$ is the only row of $L$ that is non-zero in the last column. Due to the large scaling factor $S$ in the first column, the vector $\vec v$ will in fact satisfy $z=0$, and therefore you can find a short solution by computing a reduced basis of $L$.
Here's a sage transcript that demonstrates this:
sage: p = next_prime(2**32)
sage: N = 1+floor(log(p,2)) # bit length
sage: S = 10**N
sage: a, b, c = randrange(p), randrange(p), randrange(p)
sage: a, b, c
(2206104035, 3690588304, 373686466)
sage: L = matrix(ZZ, [[S*a,-1,0,0], [S*b,0,-1,0], [S*c,0,0,S], [S*p,0,0,0]])
sage: L
[22061040350000000000 -1 0 0]
[36905883040000000000 0 -1 0]
[ 3736864660000000000 0 0 10000000000]
[42949673110000000000 0 0 0]
sage: L.LLL()
[ 0 49124 -7835 0]
[ 0 -31049 -82479 0]
[-10000000000 2330 -37438 0]
[ 0 4276 -42601 10000000000]
sage: (4276*a -42601*b) % p == c
True
