TY - JOUR

T1 - Algorithms for covering multiple submodular constraints and applications

AU - Chekuri, Chandra

AU - Inamdar, Tanmay

AU - Quanrud, Kent

AU - Varadarajan, Kasturi

AU - Zhang, Zhao

N1 - Funding Information:
Open access funding provided by University of Bergen (incl Haukeland University Hospital). Chandra Chekuri was partially supported by National Science Foundation (NSF) Grants CCF-1526799 and CCF-1910149. Work of Tanmay Inamdar and Kasturi Varadarajan was partially supported by NSF grants CCF-1318996 and CCF-1615845. Kent Quanrud was partially supported by NSF grant CCF-1526799. Work of Zhao Zhang was partially supported by NSFC (U20A2068, 11771013) and ZJNSFC (LD19A010001). In addition to the aforementioned funding sources, the authors have no relevant financial or non-financial interests to disclose.
Publisher Copyright:
© 2022, The Author(s).

PY - 2022/9

Y1 - 2022/9

N2 - 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 f1, f2, … , fr over N and requirements k1, k2, … , kr the goal is to find a minimum weight subset S⊆ N such that fi(S) ≥ ki 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.03260Har-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= ∑ iki 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- ε) while incurring an approximation of O(1ϵlogr) in the cost. Second, we consider the special case when each fi 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.

AB - 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 f1, f2, … , fr over N and requirements k1, k2, … , kr the goal is to find a minimum weight subset S⊆ N such that fi(S) ≥ ki 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.03260Har-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= ∑ iki 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- ε) while incurring an approximation of O(1ϵlogr) in the cost. Second, we consider the special case when each fi 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.

KW - Partial Set Cover

KW - Set Cover

KW - Submodular functions

UR - http://www.scopus.com/inward/record.url?scp=85132272858&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85132272858&partnerID=8YFLogxK

U2 - 10.1007/s10878-022-00874-x

DO - 10.1007/s10878-022-00874-x

M3 - Article

AN - SCOPUS:85132272858

VL - 44

SP - 979

EP - 1010

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 2

ER -