×

zbMATH — the first resource for mathematics

The asymptotic behaviour of quadratic sum assignment problems: A statistical mechanics approach. (English) Zbl 0598.90065
We apply the statistical mechanics formalism to study quadratic sum assignment problems (QSAP). This formalism allows us to exhibit, in the limit of large problems, the asymptotic behaviour of the optimal value of the cost function. The conclusions of the study are confirmed by the results of Metropolis computer simulations.

MSC:
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bonomi, E.; Lutton, J.L., The N-city travelling salesman problem and the metropolis algorithm, SIAM review, 26, 551-568, (1984) · Zbl 0551.90095
[2] Burkard, R.E.; Fincke, U., The asymptotic probabilistic behaviour of quadratic sum assignment problems, Zeitschrifi für operations research, 27, 73-81, (1983) · Zbl 0518.90052
[3] Burkard, R.E.; Fincke, U., On random quadratic bottleneck assignment problems, Mathematical programming, 23, 227-232, (1982) · Zbl 0479.90063
[4] Burkard, R.E., Quadratic assignment problems, European journal of operations research, 15, 283-289, (1984) · Zbl 0526.90064
[5] Burkard, R.E.; Rendel, F., A thermodynamically motivated simulation procedure for combinatorial optimazation problems, European journal of operations research, 17, 169-174, (1984) · Zbl 0541.90070
[6] Frenk, J.B.; van Houveninge, M.; Rinnooy, A.H.G., Asymptotic properties of assignment problems, (), Roterdam
[7] Hammersley, J.M.; Handscomb, D.C., Monte-Carlo methods, (1984), Chapman and Hall London · Zbl 0121.35503
[8] Jaynes, E.T., Information theory and statistical mechanics, Physics review, 106, 620-630, (1957) · Zbl 0084.43701
[9] Karp, R.M., A patching algorithm for the non-symmetric TSP, SIAM journal on computing, 8, 561-573, (1979) · Zbl 0427.90064
[10] Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P., Optimization by simulated annealing, () · Zbl 1225.90162
[11] Metropolis, N.; Rosenbluth, A.; Teller, A.; Teller, E., Equation of state calculations by fast computing machines, Journal of chemical physics, 21, 1087-1092, (1953)
[12] Walkup, D.W., On the expected value of the random assignment problems, SIAM journal on computing, 8, 440-442, (1979) · Zbl 0413.68062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.