serval:BIB_ED01F7B21F42
An asymptotical study of combinatorial optimization problems by means of statistical mechanics
10.1016/j.cam.2005.03.068
000232817000010
Albrecher
H.
author
Burkard
R. E.
author
Cela
E.
author
article
2006
Journal of Computational and Applied Mathematics
journal
186
1
148-162
The analogy between combinatorial optimization and statistical mechanics has proven to be a fruitful object of study. Simulated annealing, a metaheuristic for combinatorial optimization problems, is based on this analogy. In this paper we show how a statistical mechanics formalism can be utilized to analyze the asymptotic behavior of combinatorial optimization problems with sum objective function and provide an alternative proof for the following result: Under a certain combinatorial condition and some natural probabilistic assumptions on the coefficients of the problem, the ratio between the optimal solution and an arbitrary feasible solution tends to one almost surely, as the size of the problem tends to infinity, so that the problem of optimization becomes trivial in some sense. Whereas this result can also be proven by purely probabilistic techniques, the above approach allows one to understand why the assumed combinatorial condition is essential for such a type of asymptotic behavior.
Combinatorial problem
Asymptotic behavior
Probabilistic analysis
Statistical mechanics
eng
60_published
true
peer-reviewed
University of Lausanne
mailto:serval_help@unil.ch
http://www.unil.ch/serval
http://serval.unil.ch/disclaimer
https://serval.unil.ch/notice/serval:BIB_ED01F7B21F42