Two Variable Linear Programming (TVLP)

Input

A linear system of inequalities $Ax \leq b$ over $\Q$, where each row of $A$ has at most two nonzero elements. $A$ is an $n \times d$ matrix and $b$ is an $n \times 1$ vector.

Problem

Find a feasible solution if one exists.

Status

Open (Lueker, Megiddo, and Ramachandran [1]).

Remarks

There is a polylogarithmic algorithm that uses $n(\log n)^{O(1)}$ processors on a CREW-PRAM [1]. See also Problems LI, LE, LP and Opt2ILP.