Skip to Main content Skip to Navigation
Conference papers

Combinatorial Dominance Guarantees for Heuristic Algorithms

Abstract : An $f(n)$ $\textit{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 $\textit{Vertex Cover}$, $\textit{Set Cover}$, and $\textit{Knapsack}$ for dominance bounds. In particular, we show that the well-known $\textit{maximal matching}$ heuristic of $\textit{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.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184785
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 4:59:38 PM
Last modification on : Tuesday, August 13, 2019 - 11:22:21 AM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:16:54 PM

File

dmAH0106.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184785, version 1

Collections

Citation

Daniel Berend, Steven S. Skiena, Yochai Twitto. Combinatorial Dominance Guarantees for Heuristic Algorithms. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. pp.79-94. ⟨hal-01184785⟩

Share

Metrics

Record views

285

Files downloads

1030