Approximation Algorithms

Carla P. Gomes and Ryan Williams
Additional contact information
Carla P. Gomes: Cornell University, Department of Computer Science
Ryan Williams: Carnegie Mellon University, Computer Science Department

Chapter Chapter 18 in Search Methodologies, 2005, pp 557-585 from Springer

Abstract: Abstract Most interesting real-world optimization problems are very challenging from a computational point of view. In fact, quite often, finding an optimal or even a near-optimal solution to a large-scale optimization problem may require computational resources far beyond what is practically available. There is a substantial body of literature exploring the computational properties of optimization problems by considering how the computational demands of a solution method grow with the size of the problem instance to be solved (see e.g. Chapter 11 or Aho et al., 1979). A key distinction is made between problems that require computational resources that grow polynomially with problem size versus those for which the required resources grow exponentially. The former category of problems are called efficiently solvable, whereas problems in the latter category are deemed intractable because the exponential growth in required computational resources renders all but the smallest instances of such problems unsolvable.

Keywords: Approximation Algorithm; Polynomial Time; Constraint Satisfaction Problem; Vertex Cover; Hamiltonian Path (search for similar items in EconPapers)
Date: 2005
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:sprchp:978-0-387-28356-2_18

Ordering information: This item can be ordered from
http://www.springer.com/9780387283562

DOI: 10.1007/0-387-28356-0_18

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().