Skip to main navigation Skip to search Skip to main content

Approximate Local Search in Combinatorial Optimization

  • MIT Sloan School of Management
  • University of New Brunswick

Research output: Contribution to conference › Paper › peer-review

20 Scopus citations

Abstract

Local search algorithms for combinatorial optimization problems are in general of pseudopolynomial running time and polynomial-time algorithms are often not known for finding locally optimal solutions for NP-hard optimization problems. We introduce the concept of ε-local optimality and show that an ε-local optimum can be identified in time polynomial in the problem size and 1/ε whenever the corresponding neighborhood can be searched in polynomial time, for ε > 0. If the neighborhood can be searched in polynomial time for a δ-local optimum, a variation of our main algorithm produces a (δ + ε)-local optimum in time polynomial in the problem size and 1/ε. As a consequence, a combinatorial optimization problem has a fully polynomial-time approximation scheme if and only if the problem of determining a better solution - the so-called augmentation problem - has a fully polynomial-time approximation scheme.

Original languageEnglish
Pages580-589
Number of pages10
StatePublished - 2004
Externally publishedYes
EventProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
Duration: 11 Jan 2004 → 13 Jan 2004

Conference

ConferenceProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityNew Orleans, LA.
Period11/01/04 → 13/01/04

Fingerprint

Dive into the research topics of 'Approximate Local Search in Combinatorial Optimization'. Together they form a unique fingerprint.

Cite this