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
2008Journal name
Operational ResearchVolume
8Number
3Publisher
Springer
Pages
235-256
Publication identifier
Metadata
Show full item recordAbstract (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 CutRelated items
Showing items related by title and author.
-
Paschos, Vangelis; Della Croce, Federico; Escoffier, Bruno (2007) Article accepté pour publication ou publié
-
Della Croce, Federico; Escoffier, Bruno; Kaminski, Marcin; Paschos, Vangelis (2008) Chapitre d'ouvrage
-
Della Croce, Federico; Paschos, Vangelis (2005) Communication / Conférence
-
Grosso, Andrea; Della Croce, Federico; Paschos, Vangelis (2004) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2012) Article accepté pour publication ou publié