Abstract
In the framework of the Blum-Shub-Smale real number model [3], we study the algebraic complexity of the integer linear programming problem (ILPR): Given a matrix A ∈ Rm×n and vectors b ∈ R m, d ∈ R n, decide whether there is x ∈ Z n such that Ax ≤ b, where 0 ≤ x ≤ d. The main contributions of the paper are the following:
-
An O (m log ∥d∥) algorithm for ILPR, when the value of n is fixed. As a corollary, we obtain under the same restriction a tight algebraic complexity bound Θ (log 1/amin, amin = min{a1,..., a n }, for the knapsack problem (KP R): Given a ∈ R + n, decide whether there is x ∈ Zn such that a T x = 1. We achieve these results in particular through a careful analysis of the algebraic complexity of the Lovász’ basis reduction algorithm and the Kannan-Bachem’s Hermite normal form algorithm, which may be of interest in its own.
-
An O mn5 log n (n + log ∥d∥)) depth algebraic decision tree for ILPR, for every m and n.
-
A new lower bound for 0/1 KP R. More precisely, no algorithm can solve 0/1 KP R in o (n log n) f (a1,..., a n ) time, even if f is an arbitrary continuous function of n variables. This result appears as an alternative to the well-known Ben-Or’s bound Ω(n2) [1] and is independent upon it.
Chapter PDF
Similar content being viewed by others
References
Ben-Or, M.: Lower Bounds for Algebraic Computation Tree. Proc. Of the 15th ACM STOC (1983) 80–86
Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer-Verlag, Berlin Heidelberg New York (1995)
Blum, L., Shub, M., Smale, S.: On a Theory of Computation and Complexity over the Real Numbers: NP-Completeness, Recursive Functions and Universal Machines. Bull. Amer. Math. Soc. (NS), 21 (1989) 1–46
Brimkov, V.E., Danchev, S.S.: Real Data-Integer Solution Problems within the Blum-Shub-Smale Computational Model: J. of Complexity, 13 (1997) 279–300
Brimkov, V.E., Danchev, S.S., Leoncini, M.: Tight Complexity Bounds for the Two-Dimensional Real Knapsack Problem. Calcolo, 36 (1999) 123–128
Brimkov, V.E., Dantchev, S.S.: Lower Bounds, “Pseudopolynomial” and Approximation Algorithms for the Knapsack Problem with Real Coefficients. Electronic Colloquium on Computational Complexity, TR98-015 (1998). http://www.eccc.uni-trier.de/eccc/
Cucker, F., Shub, M.: Generalized Knapsack Problem and Fixed Degree Separations. Theoret. Comput. Sci., 161 (1996) 301–306
Garey, M.S., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman & Co., San Francisco (1979)
Hastad, J., Just, B., Lagarias, J.C., Schnoor, C.P.: Polynomial Time Algorithms for Finding Integer Relations among Real Numbers. SIAM J. Comput., 18 (1989) 859–881
Kannan, R., Bachem, A.: Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix. SIAM J. Comput., 8 (1979) 499–507
Kellerer, H., Mansini, R., Pferschy, U., Speranza, M.G.: An Efficient Fully Polynomial Approximation Scheme for the Subset-Sum Problem. Proc. 8th ISAAC Symposium, Lecture Notes in Computer Science, Vol. 1350. Springer-Verlag, Berlin Heidelberg New York (1997) 394–403
Lenstra, H.W., Jr.: Integer Programming with a Fixed Number of Variables. Math. Oper. Res., 8 (1983) 538–548
Lenstra, A.K., Lenstra, H.W., Jr., Lovász, L.: Factoring Polynomials with Rational Coefficients. Math. Ann., 261 (1982) 515–534
Meyer Auf Der Heide, F.: A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem. J. of ACM, 31 (3) (1984) 668–676
Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, Chichester New York Brisbane Toronto Singapore (1990)
Megiddo, N.: Linear Programming in Linear Time when the Dimension is Fixed. J. of ACM, 31 (1) (1984) 114–127
Montaña, J.L., Pardo, L.M.: Lower Bounds for Arithmetic Networks. Appl. Algebra Eng. Comm. Comput., 4 (1993) 1–24
Novak, E., The Real Number Model in Numerical Analysis. J. of Complexity, 11 (1994) 57–73
Preparata, F.P., Shamos, M.I.: Computational Geometry. Springer-Verlag, Berlin Heidelberg New York (1985)
Rössner, C., Schnorr, C.P.: An Optimal, Stable Continued Fraction Algorithm for Arbitrary Dimension. In: Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 1084. Springer-Verlag, Berlin Heidelberg New York (1996) 31–43
Schrijver, A.: Theory of Linear and Integer Programming, Wiley, Chichester New York Brisbane Toronto Singapore (1986)
Strassen, V.: Algebraic Complexity Theory. In: van Leeuwen, J. (Ed.): Handbook of Theoretical Computer Science, Vol. A Elsevier, Amsterdam (1990) 633–672
Smale, S.: Some Remarks on the Foundations of Numerical Analysis. SIAM Rev., 32 (2) (1990) 211–220
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brimkov, V.E., Dantchev, S.S. (2000). On the Complexity of Integer Programming in the Blum-Shub-Smale Computational Model. In: van Leeuwen, J., Watanabe, O., Hagiya, M., Mosses, P.D., Ito, T. (eds) Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics. TCS 2000. Lecture Notes in Computer Science, vol 1872. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44929-9_22
Download citation
DOI: https://doi.org/10.1007/3-540-44929-9_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67823-6
Online ISBN: 978-3-540-44929-4
eBook Packages: Springer Book Archive