Logo image
Back
Algorithms for covering multiple submodular constraints and applications
Journal article   Open access   Peer reviewed

Algorithms for covering multiple submodular constraints and applications

Chandra Chekuri, Tanmay Inamdar, Kent Quanrud, Kasturi Varadarajan and Zhao Zhang
Journal of combinatorial optimization, Vol.44(2), pp.979-1010
09/01/2022
DOI: 10.1007/s10878-022-00874-x
url
https://doi.org/10.1007/s10878-022-00874-xView
Published (Version of record) Open Access

Abstract

We consider the problem of covering multiple submodular constraints. Given a finite ground set N, a weight function w : N -> R+, r monotone submodular functions , f(1), f(2), ..., f(r) r over N and requirements k(1), k(2), ..., k(r) the goal is to find a minimum weight subset S subset of N such that f(i)(S) >= k(i) for 1 <= i <= r. We refer to this problem as MULTI SUBMOD COVER and it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR. arxiv:abs1808.03260 Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with r = 1 MULTI SUBMOD-COVER generalizes the well-known Submodular Set Cover problem (SuBmoD-SC), and it can also be easily reduced to SuBmoD-SC. A simple greedy algorithm gives an O(log(kr)) approximation where k = Sigma(i) k(i) and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm for MULTI SUBMOD COVER that covers each constraint to within a factor of (1 - 1/e - epsilon) while incurring an approximation of O(1/epsilon log r) in the cost. Second, we consider the special case when each f(i) is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (PARTIAL-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2-8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems.
 Computer Science Mathematics Physical Sciences Technology Computer Science, Interdisciplinary Applications Mathematics, Applied Science & Technology

Details

Metrics

28 Record Views
9 Times Cited - Web of Science
Logo image