Skip to main content
eScholarship
Open Access Publications from the University of California

UC Riverside

UC Riverside Previously Published Works bannerUC Riverside

Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost

Published Web Location

https://arxiv.org/pdf/0807.0644
No data is associated with this publication.
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. © 2012 Springer Science+Business Media, LLC.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item