Orlin, James B. Punnen, Abraham P. Schulz, Andreas S.
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 epsilon-local optimality and show that an epsilon-local optimum can be identified in time polynomial in the problem size and 1/epsilon whenever the corresponding neighborhood can be searched in polynomial time, for epsilon > 0. If the neighborhood can be searched in polynomial time for a delta-local optimum, we present an algorithm that produces a (delta+epsilon)-local optimum in time polynomial in the problem size and 1/epsilon. As a consequence, a combinatorial optimization problem has a fully polynomial-time approximation scheme if and only if it has a fully polynomial-time augmentation schem
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Publisher Info
Paper provided by Massachusetts Institute of Technology (MIT), Sloan School of Management in its series Working papers with number
4325-03.
Length: Date of creation: 15 Aug 2003 Date of revision: Handle: RePEc:mit:sloanp:3539
Contact details of provider: Postal: MASSACHUSETTS INSTITUTE OF TECHNOLOGY (MIT), SLOAN SCHOOL OF MANAGEMENT, 50 MEMORIAL DRIVE CAMBRIDGE MASSACHUSETTS 02142 USA Phone: 617-253-2659 Web page: http://mitsloan.mit.edu/ More information through EDIRC
Order Information: Postal: MASSACHUSETTS INSTITUTE OF TECHNOLOGY (MIT), SLOAN SCHOOL OF MANAGEMENT, 50 MEMORIAL DRIVE CAMBRIDGE MASSACHUSETTS 02142 USA
For technical questions regarding this item, or to correct its listing, contact: (Christian Zimmermann).