• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems

Thumbnail
Date
2008
Link to item file
http://hal.archives-ouvertes.fr/hal-00116639/en/
Dewey
Recherche opérationnelle
Sujet
Worst-case Complexity; Dominance Conditions; Set Covering; Max Cut
Journal issue
Operational Research
Volume
8
Number
3
Publication date
11-2008
Article pages
235-256
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s12351-008-0020-8
URI
https://basepub.dauphine.fr/handle/123456789/2850
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Paschos, Vangelis
Della Croce, Federico
Type
Article accepté pour publication ou publié
Abstract (EN)
In the design of branch-and-bound methods for NP-hard combinatorial optimization problems, dominance conditions have always been applied. In this work we show how the use of dominance conditions within search tree algorithms can lead to non trivial worst-case upper time bounds for the considered algorithms on bounded combinatorial optimization problems. We consider here the MIN 3-SET COVERING and the max cut problem with maximum degree three. Combining dominance conditions and intuitive combinatorial arguments, we derive two exact algorithms with worst-case complexity bounded above by O * (1.4492 n ) and O * (1.2920 n ) for the former and the latter problem, respectively, where notation O * (·) takes into account only exponential factors, and n is the number of subsets for MIN 3-SET COVERING and the number of vertices of the input-graph for max cut.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.