Physics – Condensed Matter – Statistical Mechanics
Scientific paper
2011-01-04
Physics
Condensed Matter
Statistical Mechanics
Scientific paper
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_{\rm min}$ and $C_{\rm max}$, the costs of the minimal and maximum solutions respectively. Notable features of our results are the symmetry of the results for $C_{\rm min}$ and $C_{\rm max}$ 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$.
Paul Gerald
Shao Jia
Stanley Eugene H.
No associations
LandOfFree
The Random Quadratic Assignment Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Random Quadratic Assignment Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Random Quadratic Assignment Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-75357