Combinatorial Dominance Guarantees for Heuristic Algorithms

Daniel Berend 1, 2 Steven S. Skiena 3 Yochai Twitto 2
1 Department of mathematics [Israel]
2 Ben-Gurion University of the Negev - Department of Computer Science
3 Computer Science Department [SUNY]
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.
Keywords : combinatorial optimization approximation algorithms domination analysis
Type de document :
Communication dans un congrès
Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.79-94, 2007, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01184785
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 16:59:38
Dernière modification le : samedi 3 mars 2018 - 01:04:57
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:16:54

Fichier

dmAH0106.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184785, version 1

Collections

INSMI | TDS-MACS

Citation

Daniel Berend, Steven S. Skiena, Yochai Twitto. Combinatorial Dominance Guarantees for Heuristic Algorithms. Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.79-94, 2007, DMTCS Proceedings. 〈hal-01184785〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

103

Téléchargements de fichiers

172

Contact


archive-ouverte@inria.fr