Geodesic
Combinatorial Dominance Guarantees for Heuristic Algorithms
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2007_special_253_a19,
     author = {Berend, Daniel and Skiena, Steven S. and Twitto, Yochai},
     title = {Combinatorial {Dominance} {Guarantees} for {Heuristic} {Algorithms}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)},
     year = {2007},
     doi = {10.46298/dmtcs.3537},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3537/}
}
TY  - JOUR
AU  - Berend, Daniel
AU  - Skiena, Steven S.
AU  - Twitto, Yochai
TI  - Combinatorial Dominance Guarantees for Heuristic Algorithms
JO  - Discrete mathematics & theoretical computer science
PY  - 2007
VL  - DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3537/
DO  - 10.46298/dmtcs.3537
LA  - en
ID  - DMTCS_2007_special_253_a19
ER  - 
%0 Journal Article
%A Berend, Daniel
%A Skiena, Steven S.
%A Twitto, Yochai
%T Combinatorial Dominance Guarantees for Heuristic Algorithms
%J Discrete mathematics & theoretical computer science
%D 2007
%V DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3537/
%R 10.46298/dmtcs.3537
%G en
%F DMTCS_2007_special_253_a19
Berend, Daniel; Skiena, Steven S.; Twitto, Yochai. Combinatorial Dominance Guarantees for Heuristic Algorithms. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007). doi : 10.46298/dmtcs.3537. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3537/

Cité par Sources :