A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.

DOI10.1007/s101070050010zbMath1043.90075OpenAlexW2027764232MaRDI QIDQ1575073

Gerhard J. Woeginger, Vladimir G. Deǐneko

Publication date: 2000

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s101070050010

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

Multiobjective traveling salesperson problem on Halin graphs, The bipartite quadratic assignment problem and extensions, A survey for the quadratic assignment problem, The stable set problem and the thinness of a graph, Split-merge: using exponential neighborhood search for scheduling a batching machine, A new asymmetric pyramidally solvable class of the traveling salesman problem, The exponential multi-insertion neighborhood for the vehicle routing problem with unit demands, The parameterized complexity of local search for TSP, more refined, The bilinear assignment problem: complexity and polynomially solvable special cases, Very Large-Scale Neighborhood Search: Overview and Case Studies on Coloring Problems, An exponential (matching based) neighborhood for the vehicle routing problem, Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems, Upper bounds on ATSP neighborhood size., Heuristics for vehicle routing problems: sequence or set optimization?, Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis, Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms, Dominance guarantees for above-average solutions, Polynomially solvable cases of the bipartite traveling salesman problem, Construction heuristics for the asymmetric TSP., A survey of very large-scale neighborhood search techniques, Extended neighborhood: Definition and characterization, Further extension of the TSP assign neighborhood, Creating very large scale neighborhoods out of smaller ones by compounding moves, A multi-start dynasearch algorithm for the time dependent single-machine total weighted tardiness scheduling problem, A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem, Very Large-Scale Neighborhoods with Performance Guarantees for Minimizing Makespan on Parallel Machines, A class of exponential neighbourhoods for the quadratic travelling salesman problem, Fast local search algorithms for the handicapped persons transportation problem, Four-point conditions for the TSP: the complete complexity classification, A new ILP-based refinement heuristic for vehicle routing problems, New exponential neighbourhood for polynomially solvable TSPs, Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number