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
Full text not available from this repository.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 |