• Mon espace de travail
  • Aide IRIS
  • Par Publication Par Personne Par Unité
    • English
    • Français
  • Se connecter
Logo du site

IRIS | Système d’Information de la Recherche Institutionnelle

  • Accueil
  • Personnes
  • Publications
  • Unités
  • Périodiques
UNIL
  • English
  • Français
Se connecter
IRIS
  • Accueil
  • Personnes
  • Publications
  • Unités
  • Périodiques
  • Mon espace de travail
  • Aide IRIS

Parcourir IRIS

  • Par Publication
  • Par Personne
  • Par Unité
  1. Accueil
  2. IRIS
  3. Publication
  4. An asymptotical study of combinatorial optimization problems by means of statistical mechanics
 
  • Détails
Titre

An asymptotical study of combinatorial optimization problems by means of statistical mechanics

Type
article
Institution
Externe
Périodique
Journal of Computational and Applied Mathematics  
Auteur(s)
Albrecher, H.
Auteure/Auteur
Burkard, R. E.
Auteure/Auteur
Cela, E.
Auteure/Auteur
Liens vers les personnes
Albrecher, Hansjoerg  
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.
Sujets

Combinatorial problem...

Asymptotic behavior

Probabilistic analysi...

Statistical mechanics...

PID Serval
serval:BIB_ED01F7B21F42
DOI
10.1016/j.cam.2005.03.068
WOS
000232817000010
Permalien
https://iris.unil.ch/handle/iris/251202
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)
En cours de chargement...
Vignette d'image
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

  • Copyright © 2024 UNIL
  • Informations légales