Lower time bounds for integer programming with two variables

Any integer programming problem is reformulated as the following recognition problem: Given a set of m linear inequalities, \[ \sum^{n}_{i=1}a_{ij}x_ i\leq b_ j\quad (j=1,2,...,m),\quad a_{ij},\quad b_ j\in Q \] (Q is the set of rationals), determine whether there is a solution \(x=(x_ 1,...,x_ n)\in Z^ n\) which fulfills all of them (where Z is the set of integers). This problem is well known to be NP-complete. A simple version of the integer programming problem with \(n=2\), \(m=3\) is discussed. In this case the problem reduces to deciding whether a given triangle in the plane contains a point with integer coordinates. At first, the authors define a problem with only one variable which can be reduced in constant time to their integer programming problem. Next it is proved that there exists an algorithm for the one-dimensional problem which works in time polynomial in the binary length p of the input. As a result, two lower bounds are shown for the number of operations necessary to solve the integer problem: (i) \(\Omega\) (p) steps are necessary if operations from \(\{+,-,\div,\leq \}\) are admissible, and (ii) \(\Omega\) (log p) steps are necessary if operations from \(\{+,-,(\cdot),\leq \}\) are admissible where (\(\cdot)\) denotes the floor function, i.e., (x) is the largest integer smaller or equal to x. New techniques are necessary for relating the bounds to the length of the input and for handling the floor function which prevents us from applying the well-known algebraic arguments. The best known algorithm is due to H. W. Lenstra, jun. and needs O(p) steps over \(\{+,-,*,\div,(\cdot),\leq \}\).

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Lower time bounds for integer programming with two variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1072938)