 NSFPAR ID:
 10315635
 Date Published:
 Journal Name:
 Mathematics of operations research
 ISSN:
 15265471
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

We study the problem of maximizing a nonmonotone submodular function subject to a cardinality constraint in the streaming model. Our main contributions are two singlepass (semi)streaming algorithms that use $\tilde{O}(k)\cdot\mathrm{poly}(1/\varepsilon)$ memory, where $k$ is the size constraint. At the end of the stream, both our algorithms postprocess their data structures using any offline algorithm for submodular maximization, and obtain a solution whose approximation guarantee is $\frac{\alpha}{1+\alpha}\varepsilon$, where $\alpha$ is the approximation of the offline algorithm. If we use an exact (exponential time) postprocessing algorithm, this leads to $\frac{1}{2}\varepsilon$ approximation (which is nearly optimal). If we postprocess with the algorithm of BuchbinderFeldman '19, that achieves the stateoftheart offline approximation guarantee of $\alpha=0.385$, we obtain $0.2779$approximation in polynomial time, improving over the previously best polynomialtime approximation of $0.1715$ due to Feldman'18. One of our algorithms is combinatorial and enjoys fast update and overall running times. Our other algorithm is based on the multilinear extension, enjoys an improved space complexity, and can be made deterministic in some settings of interest.more » « less

Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground set
N , a weight function ,$$w: N \rightarrow \mathbb {R}_+$$ $w:N\to {R}_{+}$r monotone submodular functions over$$f_1,f_2,\ldots ,f_r$$ ${f}_{1},{f}_{2},\dots ,{f}_{r}$N and requirements the goal is to find a minimum weight subset$$k_1,k_2,\ldots ,k_r$$ ${k}_{1},{k}_{2},\dots ,{k}_{r}$ such that$$S \subseteq N$$ $S\subseteq N$ for$$f_i(S) \ge k_i$$ ${f}_{i}\left(S\right)\ge {k}_{i}$ . We refer to this problem as$$1 \le i \le r$$ $1\le i\le r$MultiSubmodCover and it was recently considered by HarPeled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260 HarPeled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$ $r=1$MultiSubmodCover generalizes the wellknown Submodular Set Cover problem (SubmodSC ), and it can also be easily reduced toSubmodSC . A simple greedy algorithm gives an approximation where$$O(\log (kr))$$ $O(log(kr\left)\right)$ 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$$k = \sum _i k_i$$ $k={\sum}_{i}{k}_{i}$MultiSubmodCover that covers each constraint to within a factor of while incurring an approximation of$$(11/e\varepsilon )$$ $(11/e\epsilon )$ in the cost. Second, we consider the special case when each$$O(\frac{1}{\epsilon }\log r)$$ $O(\frac{1}{\u03f5}logr)$ is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover ($$f_i$$ ${f}_{i}$PartialSC ), 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 highlevel model and the lens of submodularity in addressing this class of covering problems. 
Maximizing a monotone ksubmodular function subject to cardinality constraints is a general model for several applications ranging from influence maximization with multiple products to sensor placement with multiple sensor types and online ad allocation. Due to the large problem scale in many applications and the online nature of ad allocation, a need arises for algorithms that process elements in a streaming fashion and possibly make online decisions. In this work, we develop a new streaming algorithm for maximizing a monotone ksubmodular function subject to a percoordinate cardinality constraint attaining an approximation guarantee close to the state of the art guarantee in the offline setting. Though not typical for streaming algorithms, our streaming algorithm also readily applies to the online setting with free disposal. Our algorithm is combinatorial and enjoys fast running time and small number of function evaluations. Furthermore, its guarantee improves as the cardinality constraints get larger, which is especially suited for the large scale applications. For the special case of maximizing a submodular function with large budgets, our combinatorial algorithm matches the guarantee of the stateoftheart continuous algorithm, which requires significantly more time and function evaluations.more » « less

We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of adaptive rounds of evaluation queries. We obtain the first algorithms with low adaptivity for submodular maximization with a matroid constraint. Our algorithms achieve a $11/e\epsilon$ approximation for monotone functions and a $1/e\epsilon$ approximation for nonmonotone functions, which nearly matches the best guarantees known in the fully adaptive setting. The number of rounds of adaptivity is $O(\log^2{n}/\epsilon^3)$, which is an exponential speedup over the existing algorithms. We obtain the first parallel algorithm for nonmonotone submodular maximization subject to packing constraints. Our algorithm achieves a $1/e\epsilon$ approximation using $O(\log(n/\epsilon) \log(1/\epsilon) \log(n+m)/ \epsilon^2)$ parallel rounds, which is again an exponential speedup in parallel time over the existing algorithms. For monotone functions, we obtain a $11/e\epsilon$ approximation in $O(\log(n/\epsilon)\log(m)/\epsilon^2)$ parallel rounds. The number of parallel rounds of our algorithm matches that of the state of the art algorithm for solving packing LPs with a linear objective (Mahoney et al., 2016). Our results apply more generally to the problem of maximizing a diminishing returns submodular (DRsubmodular) function.more » « less

null (Ed.)In this paper we describe a new parallel algorithm called Fast Adaptive Sequencing Technique (FAST) for maximizing a monotone submodular function under a cardinality constraint k. This algorithm achieves the optimal 11/e approximation guarantee and is orders of magnitude faster than the stateoftheart on a variety of experiments over realworld data sets. Following recent work by Balkanski & Singer (2018a), there has been a great deal of research on algorithms whose theoretical parallel runtime is exponentially faster than algorithms used for sub modular maximization over the past 40 years. However, while these new algorithms are fast in terms of asymptotic worstcase guarantees, it is computationally infeasible to use them in practice even on small data sets because the number of rounds and queries they require depend on large constants and highdegree polynomials in terms of precision and confidence. The design principles behind the FAST algorithm we present here are a significant departure from those of recent theoretically fast algorithms. Rather than optimize for asymptotic theoretical guarantees, the design of FAST introduces several new techniques that achieve remarkable practical and theoretical parallel runtimes. The approximation guarantee obtained by FAST is arbitrarily close to 11/e, and its asymptotic parallel runtime (adaptivity) is O(log(n) log2(log k)) using O(n log log(k)) total queries. We show that FAST is orders of magnitude faster than any algorithm for submodular maximization we are aware of, including hyperoptimized parallel versions of stateoftheart serial algorithms, by running experiments on large data sets.more » « less