Combinatorial Dominance Guarantees for Heuristic Algorithms
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 domin...
| Main Authors: | , , |
|---|---|
| פורמט: | Article |
| שפה: | English |
| יצא לאור: |
Discrete Mathematics & Theoretical Computer Science
2007-01-01
|
| סדרה: | Discrete Mathematics & Theoretical Computer Science |
| נושאים: | |
| גישה מקוונת: | https://dmtcs.episciences.org/3537/pdf |