Approximate Local Search in Combinatorial Optimization
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....
| Main Authors: | , , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
2003
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/3539 |
| _version_ | 1826211183093350400 |
|---|---|
| author | Orlin, James B. Punnen, Abraham P. Schulz, Andreas S. |
| author_facet | Orlin, James B. Punnen, Abraham P. Schulz, Andreas S. |
| author_sort | Orlin, James B. |
| collection | MIT |
| description | 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 |
| first_indexed | 2024-09-23T15:01:53Z |
| format | Working Paper |
| id | mit-1721.1/3539 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:01:53Z |
| publishDate | 2003 |
| record_format | dspace |
| spelling | mit-1721.1/35392019-04-10T23:47:30Z Approximate Local Search in Combinatorial Optimization Orlin, James B. Punnen, Abraham P. Schulz, Andreas S. Local Search Neighborhood Search Approximation Algorithms Computational Complexity Combinatorial Optimization 0/1-Integer Programming 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 2003-08-15T19:49:25Z 2003-08-15T19:49:25Z 2003-08-15T19:49:25Z Working Paper http://hdl.handle.net/1721.1/3539 en_US MIT Sloan School of Management Working Paper;4325-03 173594 bytes application/pdf application/pdf |
| spellingShingle | Local Search Neighborhood Search Approximation Algorithms Computational Complexity Combinatorial Optimization 0/1-Integer Programming Orlin, James B. Punnen, Abraham P. Schulz, Andreas S. Approximate Local Search in Combinatorial Optimization |
| title | Approximate Local Search in Combinatorial Optimization |
| title_full | Approximate Local Search in Combinatorial Optimization |
| title_fullStr | Approximate Local Search in Combinatorial Optimization |
| title_full_unstemmed | Approximate Local Search in Combinatorial Optimization |
| title_short | Approximate Local Search in Combinatorial Optimization |
| title_sort | approximate local search in combinatorial optimization |
| topic | Local Search Neighborhood Search Approximation Algorithms Computational Complexity Combinatorial Optimization 0/1-Integer Programming |
| url | http://hdl.handle.net/1721.1/3539 |
| work_keys_str_mv | AT orlinjamesb approximatelocalsearchincombinatorialoptimization AT punnenabrahamp approximatelocalsearchincombinatorialoptimization AT schulzandreass approximatelocalsearchincombinatorialoptimization |