Name
Title | ||
|---|---|---|
Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s12351-008-0020-8 | Operational Research |
Keywords | DocType | Volume |
Worst-case complexity,Dominance conditions,Set covering,Max cut | Journal | 8 |
Issue | ISSN | Citations |
3 | 1866-1505 | 0 |
PageRank | References | Authors |
0.34 | 9 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Federico Della Croce | 1 | 399 | 41.60 |
| Vangelis Th. Paschos | 2 | 633 | 63.97 |