Titre
An asymptotical study of combinatorial optimization problems by means of statistical mechanics
Type
article
Institution
Externe
Auteur(s)
Albrecher, H.
Auteure/Auteur
Burkard, R. E.
Auteure/Auteur
Cela, E.
Auteure/Auteur
Liens vers les personnes
Statut éditorial
Publié
Date de publication
2006
Volume
186
Numéro
1
Première page
148
Dernière page/numéro d’article
162
Peer-reviewed
Oui
Langue
anglais
Résumé
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.
PID Serval
serval:BIB_ED01F7B21F42
Open Access
Oui
Date de création
2009-02-09T18:29:27.358Z
Date de création dans IRIS
2025-05-21T06:41:41Z
Fichier(s)![Vignette d'image]()
En cours de chargement...
Nom
BIB_ED01F7B21F42.P001.pdf
Version du manuscrit
preprint
Taille
246.99 KB
Format
Adobe PDF
PID Serval
serval:BIB_ED01F7B21F42.P001
Somme de contrôle
(MD5):5631802e29910392780a7868255de4ea