Fomin, Fedor V. and Grandoni, Fabrizio and Kratsch, Dieter
(2009)
*
A measure & conquer approach for the analysis of exact algorithms.
*
*Journal of the ACM*, 56 (5).
ISSN 0004-5411

## Abstract

For more than 40 years Branch & Reduce exponential-time back tracking algorithms have been among the most common tools used for finding exact solutions of NP-hard problems. Despite that, the way to analyze such recursive algorithms is still far from producing tight worst-case running time bounds. Motivated by this we use an approach, that we call “Measure & Conquer”, as an attempt to step beyond such limitations. The approach is based on the careful design of a non-standard measure of the subproblem size; this measure is then used to lower bound the progress made by the algorithm at each ranching step. The idea is that a smarter measure may capture behaviors of the algorithm that a standard measure might not be able to exploit, and hence lead to a significantly better worst-case time analysis. In order to show the potentialities of Measure & Conquer, we consider two well-studied NP-hard problems: minimum dominating set and maximum independent set. For the first problem, we consider the current best algorithm, and prove (thanks to a better measure) a much tighter running time bound for it. For the second problem, we describe a new,simple algorithm, and show that its running time is competitive with the current besttime bounds, achieved with far more complicated algorithms(and standard analysis). Our examples show that a good choice of the measure, made in the very first stages of exact algorithms design, can have a tremendous impact on the running time bounds achievable.

Item Type: | Scientific journal article, Newspaper article or Magazine article |
---|---|

Uncontrolled Keywords: | Exact algorithm, dominating set, independent set |

Subjects: | Computer sciences |

Depositing User: | Fabrizio Grandoni |

Date Deposited: | 14 Mar 2014 08:58 |

Last Modified: | 23 May 2016 14:38 |

URI: | http://repository.supsi.ch/id/eprint/4497 |

### Actions (login required)

View Item |