Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems (Q1080776)

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.