COMPUTATIONAL COMPLEXITY OF DISCRETE OPTIMIZATION PROBLEMS

J. K. Lenstra and A. H. G. Rinnooy Kan

No 272162, Econometric Institute Archives from Erasmus University Rotterdam

Abstract: Recent developments in the theory of computational complexity as applied to combinatorial problems have revealed the existence of a large class of so-called NP-complete problems, either all or none of which are solvable in polynomial time. Since many infamous combinatorial problems have been proved to be NP-complete, the latter alternative seems far more likely. In that sense, NP-completeness of a problem justifies the use of enumerative optimization methods and of approximation algorithms. In this paper we give an informal introduction to the theory of NP-completeness and derive some fundamental results, in the hope of stimulating further use of this valuable analytical tool.

Keywords: Agricultural and Food Policy; Research and Development/Tech Change/Emerging Technologies (search for similar items in EconPapers)
Pages: 31
Date: 1977
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://ageconsearch.umn.edu/record/272162/files/erasmus099.pdf (application/pdf)
https://ageconsearch.umn.edu/record/272162/files/erasmus099.pdf?subformat=pdfa (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ags:eureia:272162

DOI: 10.22004/ag.econ.272162

Access Statistics for this paper

More papers in Econometric Institute Archives from Erasmus University Rotterdam Contact information at EDIRC.
Bibliographic data for series maintained by AgEcon Search ().