Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems
type: Item
instance of: scholarly article
title: Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems
zbMATH Open document ID: 0599.90085
DOI: 10.1016/0167-6377(86)90007-6
author: Maurice Queyranne
published in: Operations Research Letters
publication date: 1986-01-01T00:00:00Z
review text: Heuristics are considered for the Koopmans-Beckmann version of the quadratic assignment problem with symmetric distance matrix satisfying the triangle inequality. Under the assumption that \(P=NP\) it is shown that no polynomial heuristic can asymptotically yield an objective value, systematically remaining within a fixed multiple of the optimal value. The result is obtained by a reduction to the strongly NP-hard 3-PARTITION problem, in the sense that the existence of such a polynomial heuristic would solve 3-PARTITION. Some analogues concerning other, more restricted, families of quadratic assignment problems are indicated as remaining open questions.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90B05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90C20
zbMATH DE Number: 3968332
zbMATH Keywords: performance ratio
zbMATH Keywords: location
zbMATH Keywords: worst-case performance
zbMATH Keywords: linear arrangement
zbMATH Keywords: quadratic assignment
zbMATH Keywords: symmetric distance matrix
zbMATH Keywords: polynomial heuristic
reviewed by: Frank Plastria
MaRDI profile type: Publication
full work available at URL: 0167-6377(86)90007-6
OpenAlex ID: W2006506149
cites work: Optimal Linear Ordering
cites work: Quadratic assignment problems
cites work: Q4744064
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: Q3677509
cites work: P-Complete Approximation Problems
description: scientific article; zbMATH DE number 3968332