Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems

DOI10.1016/0167-6377(86)90007-6zbMath0599.90085OpenAlexW2006506149MaRDI QIDQ1080776

Maurice Queyranne

Publication date: 1986

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(86)90007-6

zbMATH Keywords

quadratic assignmentworst-case performancelocationperformance ratiolinear arrangementpolynomial heuristicsymmetric distance matrix

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Quadratic programming (90C20) Inventory, storage, reservoirs (90B05)

Related Items (10)

A survey for the quadratic assignment problem ⋮ Optimization of the quadratic assignment problem using an ant colony algorithm ⋮ A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems ⋮ A new greedy algorithm for the quadratic assignment problem ⋮ Localization in 1D non-parametric latent space models from pairwise affinities ⋮ Maximizing Polynomials Subject to Assignment Constraints ⋮ New special cases of the quadratic assignment problem with diagonally structured coefficient matrices ⋮ Selected topics on assignment problems ⋮ A Novel SDP Relaxation for the Quadratic Assignment Problem Using Cut Pseudo Bases ⋮ Approximating the maximum quadratic assignment problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quadratic assignment problems
• Some simplified NP-complete graph problems
• P-Complete Approximation Problems
• Optimal Linear Ordering

This page was built for publication: Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems