On the quality of local search for the quadratic assignment problem

DOI10.1016/S0166-218X(97)00129-7zbMath0896.90157OpenAlexW2078027863MaRDI QIDQ1383366

Eric Angel, Vassilios Zissimopoulos

Publication date: 2 June 1998

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

traveling salesmanlocal searchmaximum independent setNP-complete combinatorial optimizationgraph bipartitioning

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

A survey for the quadratic assignment problem ⋮ The bilinear assignment problem: complexity and polynomially solvable special cases ⋮ Analysis of 2-Opt Heuristic for the Winner Determination Problem Under the Chamberlin-Courant System ⋮ On the classification of NP-complete problems in terms of their correlation coefficient ⋮ 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 ⋮ Random assignment problems ⋮ Neutrality in fitness landscapes. ⋮ A multi-start dynasearch algorithm for the time dependent single-machine total weighted tardiness scheduling problem ⋮ On the landscape ruggedness of the quadratic assignment problem ⋮ Adaptive memory programming: a unified view of metaheuristics ⋮ Bilinear Assignment Problem: Large Neighborhoods and Experimental Analysis of Algorithms ⋮ Classes of quadratic assignment problem instances: Isomorphism and difficulty measure using a statistical approach

Cites Work

• Unnamed Item
• Unnamed Item
• How easy is local search?
• Algodesk: An experimental comparison of eight evolutionary heuristics applied to the quadratic assignment problem
• Traveling salesman problem and local search
• Local search and the local structure of NP-complete problems
• A new exact algorithm for the solution of quadratic assignment problems
• Simple Local Search Problems that are Hard to Solve
• Assignment Problems and the Location of Economic Activities