Abstract
Recently much effort has been devoted to determining the computational complexity for a variety of integer programming problems. In this paper a general integer programming problem is shown to be NP-complete; the proof given for this result uses only elementary linear algebra. Complexity results are also summarized for several particularizations of this general problem, including knapsack problems, problems which relax integrality or non-negativity restrictions and integral optimization problems with a fixed number of variables.
The authors were partially supported by N.S.F. Grant ENG-76-09936 and by SFB 21 (DFG), Institut für Operations Research, Universität Bonn, Bonn
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
A.J. Ano, J.E. Hopcroft, J.D. Ullman. The Design and Analysis of Computer Algorithms, Addison Wesley, 1974.
A. Bachern, personal communication.
I. Borosh, L.B. Treybig, Bounds on Positive Solutions of Linear Diophantine Equations, Proc. Amer. Math. Soc., Vol. 55, 299, 1976.
G.H. Bradley, Algorithm and Bound for the Greatest Common Divisor of n Integer, Comm. ACM 13, 433–436, 1970.
G.H. Bradley, Algorithms for Hermite and Smith Normal Matrices and Linear Diophantine Equations, Mathematics Computation 25, No. 116, 897–907, 1971.
S.A. Cook, The complexity of theorem proving procedures, Proc. Third ACM Symp. on Th. of Computation (1971), 151–158.
S.A. Cook, A short proof that the linear diophantine problem is in NP, Oct., 1976, Unpublished.
J. Edmonds, F.R. Giles, A Min-Max Relation for Submodular Functions on Graphs, Annals of Discrete Mathematics 1, 185–204, 1977.
M.R. Garey, D.S. Johnson, Computers and Intractability : A. Guide to the Theory of NP-Completeness, to appear W.H. Freeman, publisher, 1978.
R.S. Garfinkel, G.L. Nemhauser, Integer Programming, John Wiley, 1972.
J. Gathen, M. Sieveking, Linear integer inequalities are NP-Complete, submitted to SIAM J. Computing.
P.C. Gilmore, R.E. Gomory, The Theory and Computation of Knapsack Functions, Operations Research 14, (1966), 1045–1074.
D.S. Hirschberg, C.K. Wong, A polynomial time algorithm for the knapsack problem with two variables, JACM 23 (1976), 147–154.
R. Kannan, A proof that integer programming is in NP, unpublished, (1976).
R. Kannan, A Polynomial Algorithm For the Two-Variable Integer Programming Problem, Tech. Report 348, Dept. Oper. Res., Cornell Univ., July 1977.
R.M. Karp, Reducibilities among combinatorial problems, in Complexity of Computer Computations, (eds. R.E. Miller, J.W. Thatcher), Plenum Press, (1972), 85–103.
R.M. Karp, On the computational complexity of combinatorial problems, Networks 5, (1975), 44–68.
G.S. Lueker, Two polynomial complete problems in nonnegative integer programming, TR-178, Dept. Computer Science, Princeton Univ., March 1975.
S. Sahni, Computationally related problems, SIAM J. Cpt. 3 (1974).
E. Specker, V. Strassen, Komplexitaet von Entscheidungsproblemen, Chapter IV by J.v.z. Gathen, M. Sieveking, Lecture Notes in Computer Science 43, Springer-Verlag, New York, 1976.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1978 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kannan, R., Monma, C.L. (1978). On the Computational Complexity of Integer Programming Problems. In: Henn, R., Korte, B., Oettli, W. (eds) Optimization and Operations Research. Lecture Notes in Economics and Mathematical Systems, vol 157. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-95322-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-95322-4_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-08842-4
Online ISBN: 978-3-642-95322-4
eBook Packages: Springer Book Archive