Optimal Two Variable Integer Linear Programming (Opt2ILP)

Input

A linear system of inequalities $Ax \leq b$ over $\Z$, where $A$ is an $n \times 2$ matrix and $b$ is an $n \times 1$ vector, and an ordered pair $u \in \Z^2$.

Problem

Find a $2 \times 1$ vector $x$, with $x^T \in \Z^2$ ($T$ denotes transpose), such that $Ax \leq b$ and $ux$ is a maximum.

Status

Open (Deng [1], Shallcross, Pan, and Lin-Kriz [2]).

Remarks

This problem is $\NC$-equivalent to the problem of computing the remainders produced by the Euclidean algorithm, see ExtendedGCD and [1][2]. Shallcross, Pan, and Lin-Kriz illustrate reductions among problems $\NC$-equivalent to this and related problems [2]. See [1] and the remarks for TVLP and ExtendedGCD as well.