Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number

DOI10.1016/S0166-218X(01)00267-0zbMath0996.90061OpenAlexW2072269936MaRDI QIDQ1602705

Anders Yeo, Gregory Gutin

Publication date: 24 June 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00267-0

zbMATH Keywords

quadratic assignmenttravelling salesmanapproximation algorithmsdomination number

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP, A survey for the quadratic assignment problem, When the greedy algorithm fails, The bilinear assignment problem: complexity and polynomially solvable special cases, Computing the variance of tour costs over the solution space of the TSP in polynomial time, A parallel water flow algorithm with local search for solving the quadratic assignment problem, Domination analysis of combinatorial optimization problems., Upper bounds on ATSP neighborhood size., Domination analysis of greedy heuristics for the frequency assignment problem., 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, Minimum number of below average triangles in a weighted complete graph, Memetic algorithms: The polynomial local search complexity theory perspective, A survey of very large-scale neighborhood search techniques, Extended neighborhood: Definition and characterization, TSP tour domination and Hamilton cycle decompositions of regular digraphs, Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems, A domination algorithm for {0,1}-instances of the travelling salesman problem, Using the method of conditional expectations to supply an improved starting point for CCLS, Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number, Domination analysis of some heuristics for the traveling salesman problem, Anti-matroids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• A Hamiltonian decomposition of \(K^*_{2m},2m\geq 8\)
• Exponential neighbourhood local search for the traveling salesman problem
• The quadratic assignment problem. Theory and algorithms
• A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
• Ejection chains, reference structures and alternating path methods for traveling salesman problems
• p-solvable doubly transitive permutation groups
• The Travelling Salesman and the PQ-Tree
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• Implementation of a linear time algorithm for certain generalized traveling salesman problems
• A new heuristic for the traveling salesman problem
• Construction heuristics for the asymmetric TSP.