The random quadratic assignment problem

DOI10.1007/S10955-011-0308-6MaRDI QIDQ658428zbMATH OpenOpenAlexFDO

Authors Gerald Paul, Jia Shao, H. Eugene Stanley

Publication date 12 January 2012

Published in Journal of Statistical Physics (Search for Journal in Brave)

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

zbMATH Keywords

quadratic assignment problemreplica method

Mathematics Subject Classification ID

Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Discrete location and assignment (90B80) Combinatorial optimization (90C27)

Abstract: Optimal assignment of classes to classrooms cite{dickey}, design of DNA microarrays cite{carvalho}, cross species gene analysis cite{kolar}, creation of hospital layouts cite{elshafei}, and assignment of components to locations on circuit boards cite{steinberg} are a few of the many problems which have been formulated as a quadratic assignment problem (QAP). Originally formulated in 1957, the QAP is one of the most difficult of all combinatorial optimization problems. Here, we use statistical mechanical methods to study the asymptotic behavior of problems in which the entries of at least one of the two matrices that specify the problem are chosen from a random distribution $P$. Surprisingly, this case has not been studied before using statistical methods despite the fact that the QAP was first proposed over 50 years ago cite{Koopmans}. We find simple forms for $C_{mmin}$ and $C_{mmax}$, the costs of the minimal and maximum solutions respectively. Notable features of our results are the symmetry of the results for $C_{mmin}$ and $C_{mmax}$ and the dependence on $P$ only through its mean and standard deviation, independent of the details of $P$. After the asymptotic cost is determined for a given QAP problem, one can straightforwardly calculate the asymptotic cost of a QAP problem specified with a different random distribution $P$.

Recommendations

• The asymptotic behaviour of quadratic sum assignment problems: A statistical mechanics approach
• Asymptotic Properties of the Quadratic Assignment Problem
• scientific article; zbMATH DE number 1985298
• scientific article; zbMATH DE number 1302195
• Recent advances in the solution of quadratic assignment problems

Cites work

• A note on the asymptotic behaviour of bottleneck problems
• A survey for the quadratic assignment problem
• An asymptotical study of combinatorial optimization problems by means of statistical mechanics
• Application of statistical mechanics to NP-complete problems in combinatorial optimisation
• Assignment Problems and the Location of Economic Activities
• Asymptotic Properties of the Quadratic Assignment Problem
• Hospital Layout as a Quadratic Assignment Problem
• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• scientific article; zbMATH DE number 714526 (Why is no real title available?)
• On random quadratic bottleneck assignment problems
• Probabilistic asymptotic properties of some combinatorial optimization problems
• Random assignment problems
• Recent advances in the solution of quadratic assignment problems
• Stochastic Analysis of the Quadratic Assignment Problem
• The asymptotic behaviour of quadratic sum assignment problems: A statistical mechanics approach
• The Backboard Wiring Problem: A Placement Algorithm
• The quadratic assignment problem. Theory and algorithms

Cited in

(5)

• Matrix optimization under random external fields
• Autocorrelation measures for the quadratic assignment problem
• The quadratic Gaussian CEO problem
• scientific article; zbMATH DE number 1843033 (Why is no real title available?)
• The Distribution of Values in the Quadratic Assignment Problem

Describes a project that uses

Uses Software

• Concorde

This page was built for publication: The random quadratic assignment problem

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