On the complexity of integer programming

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of integer programming

Full text

Pdf (206 KB)

Source

Journal of the ACM (JACM) archive
Volume 28 , Issue 4 (October 1981) table of contents

Pages: 765 - 768

Year of Publication: 1981

ISSN:0004-5411

Author

Christos H. Papadimitriou

Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, Massachusetts and National Technical University, Athens, Greece

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 34, Downloads (12 Months): 246, Citation Count: 17

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322276.322287 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BOROSH, i, AND TREYBIG, L B.Bounds on posmve integral sohuons to hnear Dlophantlne equauons. Proc Amer Math Soc 55 (1976), 299-304
	2	COOK, S A Private communication, 1978
	3	DANTZIG, G B Linear Programmmg and Extenswns Princeton Umverslty Press, Princeton, N J, 1962
	4	M. R. Garey , D. S. Johnson, `` Strong '' NP-Completeness Results: Motivation, Examples, and Implications, Journal of the ACM (JACM), v.25 n.3, p.499-508, July 1978 [doi>10.1145/322077.322090]
	5	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	6	KANNAN, R, AND MONMA, C.L. On the computaUonal complexity of integer programmmg problems In Lecture Notes tn Economlcs and Mathematical Systems, Vol 157, Sprmger-Verlag, 1978, pp 161-172
	7	KARP, R M. Reducihhty among combmatorial problems In Complexay of Computer Computattons, R E. Miller and J W Thatcher, Eds, Plenum, New York, 1972, pp 85-103.
	8	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982

CITED BY 17

	H. van der Holst , J. C. de Pina, Length-bounded disjoint paths in planar graphs, Discrete Applied Mathematics, v.120 n.1-3, p.251-261, 15 August 2002
	Diego Calvanese , Maurizio Lenzerini, Making object-oriented schemas more expressive, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.243-254, May 24-27, 1994, Minneapolis, Minnesota, United States
	Isto Aho, New polynomial-time instances to various knapsack-type problems, Fundamenta Informaticae, v.53 n.3,4, p.199-228, December 2002
	Diego Calvanese , Giuseppe De Giacomo , Daniele Nardi , Maurizio Lenzerini, Reasoning in expressive description logics, Handbook of automated reasoning, Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 2001
	Wenfei Fan , Leonid Libkin, On XML integrity constraints in the presence of DTDs, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.114-125, May 2001, Santa Barbara, California, United States
	Arnaud Durand , Miki Hermann , Laurent Juban, On the complexity of recognizing the Hilbert basis of a linear diophantine system, Theoretical Computer Science, v.270 n.1-2, p.625-642, January
	Marcelo Arenas , Leonid Libkin, XML data exchange: consistency and query answering, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
	Carsten Lutz , Ulrike Sattler , Lidia Tendera, The complexity of finite model reasoning in description logics, Information and Computation, v.199 n.1-2, p.132-171, 25 May 2005
	Endre Boros , Peter L. Hammer , Ron Shamir, A Polynomial Algorithm for Balancing Acyclic Data Flow Graphs, IEEE Transactions on Computers, v.41 n.11, p.1380-1385, November 1992
	Po Rong Chang , C. S. G. Lee, A Decomposition Approach for Balancing Large-Scale Acyclic Data Flow Graphs, IEEE Transactions on Computers, v.39 n.1, p.34-46, January 1990
	Marcelo Arenas , Wenfei Fan , Leonid Libkin, On verifying consistency of XML specifications, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	Wenfei Fan , Leonid Libkin, On XML integrity constraints in the presence of DTDs, Journal of the ACM (JACM), v.49 n.3, p.368-406, May 2002
	Ian Pratt-Hartmann, Complexity of the Two-Variable Fragment with Counting Quantifiers, Journal of Logic, Language and Information, v.14 n.3, p.369-395, June 2005
	Miki Hermann , Phokion G. Kolaitis, Computational Complexity of Simultaneous Elementary Matching Problems, Journal of Automated Reasoning, v.23 n.2, p.107-136, August 1999
	Amir M. Ben-Amram, Size-change termination with difference constraints, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.3, p.1-31, May 2008
	Mikoaj Bojańczyk , Anca Muscholl , Thomas Schwentick , Luc Segoufin, Two-variable logic on data trees and XML reasoning, Journal of the ACM (JACM), v.56 n.3, p.1-48, May 2009
	Freddy Lécué , Alexandre Delteil , Alain Léger, Optimizing Causal Link Based Web Service Composition, Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence, p.45-49, June 27, 2008