Analysis of Heuristic Combinatorial Algorithms

In many practical situations heuristic algorithms reliably give satisfactory solutions to real-life instances of optimization problems, despite evidence from computational complexity theory that the problems are intractable. Our goal is to understand this seeming contradiction, and to put the construction and evaluation of heuristic algorithms on a firmer footing. We will develop a general empirical method for selecting an optimal choice of parameters and subroutines within a well defined heuristic algorithmic strategy. The method is empirical, and assumes the availability of a supply of typical problem instances which can be used to train the algorithmic strategy and evaluate its performance. The search for optimal parameters and subroutines will be treated as an optimization problem in its own right. We expect to systematically derive and evaluate heuristic algorithms for three NP-hard problems that lie within a broad class of implicit hitting set problems: multi-genome alignment, the feedback vertex set problem, and the feedback arc set problem.