• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

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

Paschos, Vangelis; Della Croce, Federico (2008), Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems, Operational Research, 8, 3, p. 235-256. http://dx.doi.org/10.1007/s12351-008-0020-8

Type
Article accepté pour publication ou publié
External document link
http://hal.archives-ouvertes.fr/hal-00116639/en/
Date
2008
Journal name
Operational Research
Volume
8
Number
3
Publisher
Springer
Pages
235-256
Publication identifier
http://dx.doi.org/10.1007/s12351-008-0020-8
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Della Croce, Federico
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.
Subjects / Keywords
Worst-case Complexity; Dominance Conditions; Set Covering; Max Cut

Related items

Showing items related by title and author.

  • Thumbnail
    Improved worst-case complexity for the MIN 3-SET COVERING problem 
    Paschos, Vangelis; Della Croce, Federico; Escoffier, Bruno (2007) Article accepté pour publication ou publié
  • Thumbnail
    Worst-case complexity of exact algorithms for NP-hard problems 
    Della Croce, Federico; Escoffier, Bruno; Kaminski, Marcin; Paschos, Vangelis (2008) Chapitre d'ouvrage
  • Thumbnail
    Computing optimal solutions for the MIN 3-SET COVERING problem 
    Della Croce, Federico; Paschos, Vangelis (2005) Communication / Conférence
  • Thumbnail
    Lower bounds on the approximation ratios of leading heuristics for the single machine total tardiness problem 
    Grosso, Andrea; Della Croce, Federico; Paschos, Vangelis (2004) Article accepté pour publication ou publié
  • Thumbnail
    Algorithms for dominating clique problems 
    Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2012) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo