DMTCS Proceedings, 2007 Conference on Analysis of Algorithms, AofA 07

Font Size:  Small  Medium  Large

Combinatorial Dominance Guarantees for Heuristic Algorithms

Daniel Berend, Steven S. Skiena, Yochai Twitto


An f(n) dominance bound on a heuristic for some problem is a guarantee that the heuristic always returns a solution not worse than at least f(n) solutions. In this paper, we analyze several heuristics for Vertex Cover, Set Cover, and Knapsack for dominance bounds. In particular, we show that the well-known maximal matching heuristic of Vertex Cover provides an excellent dominance bound. We introduce new general analysis techniques which apply to a wide range of problems and heuristics for this measure. Certain general results relating approximation ratio and combinatorial dominance guarantees for optimization problems over subsets are established. We prove certain limitations on the combinatorial dominance guarantees of polynomial-time approximation schemes (PTAS), and give inapproximability results for the problems above.

Full Text: GZIP Compressed PostScript PostScript PDF

Valid XHTML 1.0 Transitional