The Library
A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem
Tools
Tools
Tools
UNSPECIFIED (2000) A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem. MATHEMATICAL PROGRAMMING, 87 (3). pp. 519-542. ISSN 0025-5610
Full text not available from this repository.Abstract
This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively, the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods. First, we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be declined in a simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. we identify several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably lends to an NP-complete optimization problem for the QAP.
| Item Type: | Journal Article |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management Q Science > QA Mathematics |
| Journal or Publication Title: | MATHEMATICAL PROGRAMMING |
| Publisher: | SPRINGER VERLAG |
| ISSN: | 0025-5610 |
| Date: | May 2000 |
| Volume: | 87 |
| Number: | 3 |
| Number of Pages: | 24 |
| Page Range: | pp. 519-542 |
| Publication Status: | Published |
| URI: | http://wrap.warwick.ac.uk/id/eprint/13320 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
