The Distribution of Values in the Quadratic Assignment Problem

DOI10.1287/MOOR.28.1.64.14262MaRDI QIDQ5704114zbMATH OpenOpenAlexFDO

Authors Tamon Stephen, Alexander Barvinok

Publication date 11 November 2005

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0104229

zbMATH Keywords

distributionheuristicsquadratic assignment problemrandomized algorithmsrepresentation theorysymmetric group

Mathematics Subject Classification ID

Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59) Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Abstract: We obtain a number of results regarding the distribution of values of a quadratic function f on the set of nxn permutation matrices (identified with the symmetric group S_n) around its optimum (minimum or maximum). In particular, we estimate the fraction of permutations sigma such that f(sigma) lies within a given neighborhood of the optimal value of f. We identify some ``extreme functions f (there are 4 of those for n even and 5 for n odd) such that the distribution of every quadratic function around its optimum is a certain ``mixture of the distributions of the extremes and describe a natural class of functions (which includes, for example, the objective function in the Traveling Salesman Problem) with a relative abundance of near-optimal permutations. In particular, we identify a large class of functions f with the property that permutations in the vicinity of the optimal permutation (in the Hamming metric of S_n) tend to produce near optimal values of f (such is, for example, the objective function in the symmetric Traveling Salesman Problem) and show that for general f, just the opposite behavior may take place: an average permutation in the vicinity of the optimal permutation may be much worse than an average permutation in the whole group S_n.

Recommendations

• scientific article; zbMATH DE number 2086934
• scientific article; zbMATH DE number 1985298
• scientific article; zbMATH DE number 1803767
• scientific article; zbMATH DE number 1302195
• The random quadratic assignment problem
• A contribution to quadratic assignment problems
• The quadratic assignment problem. Theory and algorithms
• scientific article; zbMATH DE number 3982880
• Experimental results on quadratic assignment problem.

Cited in

(11)

• On permutation polytopes
• A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP
• A survey for the quadratic assignment problem
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• c-Birkhoff polytopes
• Exact solution of emerging quadratic assignment problems
• scientific article; zbMATH DE number 1985298 (Why is no real title available?)
• Faces of Birkhoff Polytopes
• scientific article; zbMATH DE number 2086934 (Why is no real title available?)
• On a special case of the quadratic assignment problem with an application to storage-and-retrieval devices
• On permutation polytopes: notions of equivalence

Describes a project that uses

Uses Software

• ZRAM

This page was built for publication: The Distribution of Values in the Quadratic Assignment Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5704114)