Back to Search
Start Over
Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost.
- Source :
-
Algorithmica . May2013, Vol. 66 Issue 1, p113-152. 40p. - Publication Year :
- 2013
-
Abstract
- This paper describes a simple greedy Δ-approximation algorithm for any covering problem whose objective function is submodular and non-decreasing, and whose feasible region can be expressed as the intersection of arbitrary (closed upwards) covering constraints, each of which constrains at most Δ variables of the problem. (A simple example is Vertex Cover, with Δ=2.) The algorithm generalizes previous approximation algorithms for fundamental covering problems and online paging and caching problems. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 66
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 85746568
- Full Text :
- https://doi.org/10.1007/s00453-012-9629-3