A measure & conquer approach for the analysis of exact algorithms

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.


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.

Actions (login required)

View Item View Item