Lower time bounds for integer programming with two variables (Q1072938): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0020-0190(85)90042-0 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2088530796 / rank | |||
Normal rank |
Revision as of 19:29, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lower time bounds for integer programming with two variables |
scientific article |
Statements
Lower time bounds for integer programming with two variables (English)
0 references
1985
0 references
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 \}\).
0 references
computation with polynomial order
0 references
lower time bounds
0 references
algebraic computation tree
0 references
polynomial algorithm
0 references
recognition problem
0 references
floor function
0 references