HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00077010
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Monday, May 29, 2006 - 11:49:52 AM
Last modification on : Thursday, February 3, 2022 - 11:18:09 AM
Long-term archiving on: : Friday, May 13, 2011 - 10:31:20 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

51

Files downloads

13