caa a22 4500 475769260 CHVBK 20180406123615.0 cr unu---uuuuu 170329e20000501xx s 000 0 eng 10.1007/s101070050010 doi (NATIONALLICENCE)springer-10.1007/s101070050010 A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem [Elektronische Daten] [Vladimir G. De&ıbreve;neko, Gerhard J. Woeginger] 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 defined 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 leads to an NP-complete optimization problem for the QAP. Springer-Verlag Berlin Heidelberg, 2000 Key words: neighborhood - local search - search problem - Travelling Salesman Problem - Quadratic Assignment Problem - polynomial time algorithm - NP-completeness - combinatorial optimization nationallicence Mathematics Subject Classification (1991): 90C27, 90C35, 68Q25 nationallicence De&ıbreve;neko Vladimir G. Warwick Business School, The University of Warwick, Coventry CV4 7AL, United Kingdom, e-mail: orsvd@wbs.warwick.ac.uk, UK aut Woeginger Gerhard J. TU Graz, Institut für Mathematik, Steyrergasse 30, A-8010 Graz, Austria, e-mail: gwoegi@opt.math.tu-graz.ac.at., AT aut https://doi.org/10.1007/s101070050010 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s101070050010 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- De&ıbreve;neko Vladimir G. Warwick Business School, The University of Warwick, Coventry CV4 7AL, United Kingdom, e-mail: orsvd@wbs.warwick.ac.uk, UK aut NATIONALLICENCE 700 1- Woeginger Gerhard J. TU Graz, Institut für Mathematik, Steyrergasse 30, A-8010 Graz, Austria, e-mail: gwoegi@opt.math.tu-graz.ac.at., AT aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer