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
TypeArticle accepté pour publication ou publié
External document linkhttp://hal.archives-ouvertes.fr/hal-00116639/en/
Journal nameOperational Research
MetadataShow full item record
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 / KeywordsWorst-case Complexity; Dominance Conditions; Set Covering; Max Cut
Showing items related by title and author.
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é