Exact Algorithm Analysis And Design By Measure And Conquer Approach

Exact exponential algorithm for solving NP-hard problems is one of the most important fields in algorithm research since the approximation algorithm sometimes can not satisfy the computing requirements. When designing such algorithms, we often use the so-called search tree algorithm which is proposed by Davis Putnam, i.e. the branch and reduce algorithm. This type of algorithm can divide the problem into subproblems and recursively solve it.To get faster algorithms, researchers would like to add more and more compli-cated reduction rules in the branch and reduce algorithm to simplify the problem in-stance before branching. This will lead to hard implementation and understanding of algorithms. Though at the same time, the analysis of branch and reduce algorithm has not been improved very much and the measure of the problem instance used in the standard analysis is simple as well. In most cases, such a measure can not provide a precise and tight bound for the running time of algorithms.Recently, Fomin et al. designed a new technique called measure and conquer which can weight the different aspects of a problem instance to get an non-standard measure for algorithm analysis. This paper focused on this new idea and introduced the basic notion and the analysis process of the measure-and-conquer approach. Besides, this paper also used measure-and-conquer approach to improve and design algorithms. The topics included in this paper involves:Starting from the branch and reduce algorithm for minimum set cover problem based on Fomin's analysis, this paper focused on solving minimum dominating set problem and showed how to use measure-and-conquer approach to design weighted measures, analyze subcases and search the weights. This paper proved that Grandoni's algorithm can solve the minimum dominating set problem in O(1.5260n) and polynomial space while in O(1.5160n) and exponential space.This paper pointed out a flaw in Fomin's measure-and-conquer analysis and explained why this happened with the modified analysis.This paper reviewed the worst cases existed in the measure-and-conquer analysis and proposed some new reduction rules based on the review to improve the algorithm. Moreover, this paper refined the algorithm with new reduction rules and proved that when using polynomial and exponential space the new algorithm can solve the minimum dominating set problem in O(1.5152n) and O(1.5105n) respectively.This paper also introduced the quasiconvex programming which is used for searching weights in the measure. Based on Eppstein's work, a slightly modified smooth quasiconvex programming algorithm was proposed here to effectively solve the weights searching problem in the measure-and-conquer approach.