The random quadratic assignment problem

DOI10.1007/S10955-011-0308-6zbMATH Open1252.82062arXiv1101.0779OpenAlexW3098667632MaRDI QIDQ658428FDOQ658428

Authors: Gerald Paul, Jia Shao, H. Eugene Stanley 

Publication date: 12 January 2012

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

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$.

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

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

zbMATH Keywords

quadratic assignment problemreplica method

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• The Distribution of Values in the Quadratic Assignment Problem
• Title not available (Why is that?)
• Autocorrelation measures for the quadratic assignment problem
• Matrix optimization under random external fields
• The quadratic Gaussian CEO problem

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)