Approximate Local Search in Combinatorial Optimization

James B. Orlin, Abraham P. Punnen, Andreas S. Schulz

Publikation: KonferenzbeitragPapierBegutachtung

20 Zitate (Scopus)

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.

OriginalspracheEnglisch
Seiten580-589
Seitenumfang10
PublikationsstatusVeröffentlicht - 2004
Extern publiziertJa
VeranstaltungProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., USA/Vereinigte Staaten
Dauer: 11 Jan. 200413 Jan. 2004

Konferenz

KonferenzProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Land/GebietUSA/Vereinigte Staaten
OrtNew Orleans, LA.
Zeitraum11/01/0413/01/04

Fingerprint

Untersuchen Sie die Forschungsthemen von „Approximate Local Search in Combinatorial Optimization“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren