Combinatorial optimization problems for which almost every algorithm is asymptotically optimal

Wojciec Szpankowski 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : Let Zmax and Zmin be respectively the maximum and minimum of the objective function in a combinatorial problem for which the cardinality of the set of feasible solutions is m and the size of every feasible solution is N. We prove that in a certain probabilistic framework Zmax ~ Zmin almost surely (a.s.) provided log m = o (N) for N and m become large. This result implies that for such a class of combinatorial optimization probblems almost every algorithm finds asymptotically optimal solution. The quadratic assignment problem, the location problem on graphs, and some pattern matching problems fall into this class.
Type de document :
Rapport
[Research Report] RR-1770, INRIA. 1992
Liste complète des métadonnées

https://hal.inria.fr/inria-00077010
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 29 mai 2006 - 11:49:52
Dernière modification le : vendredi 25 mai 2018 - 12:02:02
Document(s) archivé(s) le : vendredi 13 mai 2011 - 22:31:20

Fichiers

Identifiants

  • HAL Id : inria-00077010, version 1

Collections

Citation

Wojciec Szpankowski. Combinatorial optimization problems for which almost every algorithm is asymptotically optimal. [Research Report] RR-1770, INRIA. 1992. 〈inria-00077010〉

Partager

Métriques

Consultations de la notice

101

Téléchargements de fichiers

48