Francesco Cellinese, Gianlorenzo D’Angelo, Gianpiero Monaco et al. · arXiv (Cornell University) · 2018
In this paper we consider a generalization of the well-known budgeted maximum coverage problem. We are given a ground set of elements and a set of bins. The goal is to find a subset of elements along with an associated set of bins, such that the overall cost is at most a given budget, and the profit is maximized. Each bin has its own cost and the cost of each element depends on its associated bin. The profit is measured by a monotone submodular function over the elements. We first present an algorithm that guarantees an approximation factor of $\frac{1}{2}\left(1-\frac{1}{e^α}\right)$, where $α\leq 1$ is the approximation factor of an algorithm for a sub-problem. We give two polynomial-time algorithms to solve this sub-problem. The first one gives us $α=1- ε$ if the costs satisfies a specific condition, which is fulfilled in several relevant cases, including the unitary costs case and the problem of maximizing a monotone submodular function under a knapsack constraint. The second one guarantees $α=1-\frac{1}{e}-ε$ for the general case. The gap between our approximation guarantees and the known inapproximability bounds is $\frac{1}{2}$. We extend our algorithm to a bi-criterion approximation algorithm in which we are allowed to spend an extra budget up to a factor $β\geq 1$ to guarantee a $\frac{1}{2}\left(1-\frac{1}{e^{αβ}}\right)$-approximation. If we set $β=\frac{1}α\ln \left(\frac{1}{2ε}\right)$, the algorithm achieves an approximation factor of $\frac{1}{2}-ε$, for any arbitrarily small $ε>0$.
Cited by 2Open access
Francesco Cellinese, Gianlorenzo D’Angelo, Gianpiero Monaco et al. · Information and Computation · 2021
Cited by 1
Naoyuki Kamiyama · Lecture notes in computer science · 2018
Cited by 0
Zhu Xiao-zhong, William Zhu, Xinnan Fan · Soft Computing · 2016
Cited by 15
June M. Parker · Archiv der Mathematik · 1992
Cited by 4
Eszter Csókás, Tamás Vinkó · Acta Cybernetica · 2024
A crucial problem in combinatorial optimization is the submodular function maximization (SFM), and in many cases it involves graphs on which the maximization is specified. The problem is well-studied and hence there are several proposed algorithms in the literature. The greedy strategy quickly finds a feasible solution that guarantees an approximation of (1-1/e). However, there are many applications that expect an optimal result within a reasonable computational time. One popular method for finding the global optimum is the constraint generation (CG) algorithm. Traditionally, the initial feasible solution of CG is given by the greedy algorithm. It turns out that choosing different starting point than the greedy solution might lead to better performance in terms of running time. In this paper we introduce such a strategy which is beneficial on non-complete bipartite graphs. Benchmarking results on different versions of the solution methods are shown to demonstrate the efficiency of the proposed methods.
Cited by 0Open access
Gruiă Cälinescu, Chandra Chekuri, Martin Pál et al. · Lecture notes in computer science · 2007
Cited by 187
Amol Deshpande, Lisa Hellerstein, Devorah Kletenik · 2013
We present approximation algorithms for two problems: Stochastic Boolean Function Evaluation (SBFE) and Stochastic Submodular Set Cover (SSSC). Our results for SBFE problems are obtained by reducing them to SSSC problems through the construction of appropriate utility functions. We give a new algorithm for the SSSC problem that we call Adaptive Dual Greedy. We use this algorithm to obtain a 3-approximation algorithm solving the SBFE problem for linear threshold formulas. We also get a 3-approximation algorithm for the closely related Stochastic Min-Knapsack problem, and a 2-approximation for a natural special case of that problem. In addition, we prove a new approximation bound for a previous algorithm for the SSSC problem, Adaptive Greedy. We consider an approach to approximating SBFE problems using existing techniques, which we call the Q-value approach. This approach easily yields a new result for evaluation of CDNF formulas, and we apply variants of it to simultaneous evaluation problems and a ranking problem. However, we show that the Q-value approach provably cannot be used to obtain a sublinear approximation factor for the SBFE problem for linear threshold formulas or read-once DNF.
Cited by 25
Chandra Chekuri, Kent Quanrud · arXiv (Cornell University) · 2018
We consider parallel, or low adaptivity, algorithms for submodular function\nmaximization. This line of work was recently initiated by Balkanski and Singer\nand has already led to several interesting results on the cardinality\nconstraint and explicit packing constraints. An important open problem is the\nclassical setting of matroid constraint, which has been instrumental for\ndevelopments in submodular function maximization. In this paper we develop a\ngeneral strategy to parallelize the well-studied greedy algorithm and use it to\nobtain a randomized $\\left(\\frac{1}{2} - \\epsilon\\right)$-approximation in\n$\\operatorname{O}\\left( \\frac{\\log^2 n}{\\epsilon^2} \\right)$ rounds of\nadaptivity. We rely on this algorithm, and an elegant amplification approach\ndue to Badanidiyuru and Vondr\\'ak to obtain a fractional solution that yields a\nnear-optimal randomized $\\left( 1 - 1/e - \\epsilon \\right)$-approximation in\n$O\\left( {\\frac{\\log^2 n}{\\epsilon^3}} \\right) $ rounds of adaptivity. For\nnon-negative functions we obtain a $\\left( {3-2\\sqrt{2}}\\right)$-approximation\nand a fractional solution that yields a $\\left( {\\frac{1}{e} -\n\\epsilon}\\right)$-approximation. Our approach for parallelizing greedy yields\napproximations for intersections of matroids and matchoids, and the\napproximation ratios are comparable to those known for sequential greedy.\n
Cited by 1Open access
Hiroshi Nagamochi, Takashi Shiraki, Toshihide Ibaraki · 1999
Given a nite set V and a set function f : 2 7! Z, we consider the problem of constructing an undirected multigraph G = (V; E) such that the cut function c G : 2 7! Z of G and f together has value at least 2 for all non-empty and proper subsets of V . If f is intersecting submodular and posi-modular, and satis es the tripartite inequality, then we show that such a multigraph G with the minimum number of edges can be found in O((T f + 1)n log n) time, where n = jV j and T f is the time to compute the value of f(X) for a subset X V .
Cited by 0
Maxim Sviridenko · Operations Research Letters · 2003
Cited by 682
Amol Deshpande, Lisa Hellerstein, Devorah Kletenik · ACM Transactions on Algorithms · 2016
We present a new approximation algorithm for the stochastic submodular set cover (SSSC) problem called adaptive dual greedy . We use this algorithm to obtain a 3-approximation algorithm solving the stochastic Boolean function evaluation (SBFE) problem for linear threshold formulas (LTFs). We also obtain a 3-approximation algorithm for the closely related stochastic min-knapsack problem and a 2-approximation for a variant of that problem. We prove a new approximation bound for a previous algorithm for the SSSC problem, the adaptive greedy algorithm of Golovin and Krause. We also consider an approach to approximating SBFE problems using the adaptive greedy algorithm, which we call the Q -value approach. This approach easily yields a new result for evaluation of CDNF (conjunctive / disjunctive normal form) formulas, and we apply variants of it to simultaneous evaluation problems and a ranking problem. However, we show that the Q -value approach provably cannot be used to obtain a sublinear approximation factor for the SBFE problem for LTFs or read-once disjunctive normal form formulas.
Cited by 25
Wenqi Wang, Zhicheng Liu, Donglei Du et al. · Asia Pacific Journal of Operational Research · 2023
The set cover problem has been studied extensively for many years. Submodular function plays a key role in combinatorial optimization. Extending the set cover problem, we consider three submodular cover problems. The first two problems minimize linear and submodular functions, respectively, subject to the same non-submodular cover constraint. The third problem minimizes a submodular function subject to non-submodular cover and precedence constraints. Based on the concepts of submodular ratio and gap, and Lovász extension, we devise greedy and primal–dual approximation algorithms for these problems.
Cited by 0
Yajing Liu, Edwin K. P. Chong, Ali Pezeshki et al. · arXiv (Cornell University) · 2019
The greedy strategy is an approximation algorithm to solve optimization problems arising in decision making with multiple actions. How good is the greedy strategy compared to the optimal solution? In this survey, we mainly consider two classes of optimization problems where the objective function is submodular. The first is set submodular optimization, which is to choose a set of actions to optimize a set submodular objective function, and the second is string submodular optimization, which is to choose an ordered set of actions to optimize a string submodular function. Our emphasis here is on performance bounds for the greedy strategy in submodular optimization problems. Specifically, we review performance bounds for the greedy strategy, more general and improved bounds in terms of curvature, performance bounds for the batched greedy strategy, and performance bounds for Nash equilibria.
Cited by 0Open access
Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar · arXiv (Cornell University) · 2020
A real-valued set function is (additively) approximately submodular if it satisfies the submodularity conditions with an additive error. Approximate submodularity arises in many settings, especially in machine learning, where the function evaluation might not be exact. In this paper we study how close such approximately submodular functions are to truly submodular functions. We show that an approximately submodular function defined on a ground set of $n$ elements is $O(n^2)$ pointwise-close to a submodular function. This result also provides an algorithmic tool that can be used to adapt existing submodular optimization algorithms to approximately submodular functions. To complement, we show an $Ω(\sqrt{n})$ lower bound on the distance to submodularity. These results stand in contrast to the case of approximate modularity, where the distance to modularity is a constant, and approximate convexity, where the distance to convexity is logarithmic.
Cited by 0Open access
Navid Rezazadeh, Solmaz S. Kia · arXiv (Cornell University) · 2020
Constrained submodular set function maximization problems often appear in multi-agent decision-making problems with a discrete feasible set. A prominent example is the problem of multi-agent mobile sensor placement over a discrete domain. However, submodular set function optimization problems are known to be NP-hard. In this paper, we consider a class of submodular optimization problems that consists of maximization of a monotone and submodular set function subject to a uniform matroid constraint over a group of networked agents that communicate over a connected undirected graph. Our objective is to obtain a distributed suboptimal polynomial-time algorithm that enables each agent to obtain its respective policy via local interactions with its neighboring agents. Our solution is a fully distributed gradient-based algorithm using the multilinear extension of the submodular set functions and exploiting a maximum consensus scheme. This algorithm results in a policy set that when the team objective function is evaluated at worst case the objective function value is in $1-1/e-O(1/T)$ of the optimal solution. An example demonstrates our results.
Cited by 0Open access
Satoru Fujishige, Shin-ichi Tanigawa · 2013
A. Huber and V. Kolmogorov (ISCO 2012) introduced a concept of k-submodular function as a generalization of ordinary submodular (set) functions and bisubmodular functions and obtained a min-max theorem for minimization of k-submodular functions. Also F. Kuivinen (2011) considered submodular functions on (product lattices of) diamonds and showed a min-max theorem for minimization of submodular functions on diamonds. In the present paper we consider a common generalization of k-submodular functions and submodular functions on diamonds, which we call a transversal submodular function (or a t-submodular function, for short). We show a min-max theorem for minimization of t-submodular functions in terms of a new norm composed of ℓ1 and ℓ ∞ norms. This reveals a relationship between the obtained min-max theorem and that for minimization of ordinary submodular set functions due to J. Edmonds (1970). We also show how our min-max theorem for t-submodular functions can be used to prove the min-max theorem for k-submodular functions by Huber and Kolmogorov and that for submodular functions on diamonds by Kuivinen. Moreover, we show a counterexample to a characterization, given by Huber and Kolmogorov (ISCO 2012), of extreme points of the k-submodular polyhedron and make it a correct one by fixing a flaw therein.
Cited by 0
Wu, Yizhan · KTH Publication Database DiVA (KTH Royal Institute of Technology) · 2022
Recently, Udwani defined a new class of set functions under monotonicity and subadditivity, called submodular order functions, which is a subfamily of submodular functions. Informally, the submodular order function admits a very limited form of submodularity which is defined over a specific permutation of the ground set. His work pointed out the intriguing connection between streaming submodular maximization and submodular order maximization. Inspired by a 0.25-approximation streaming algorithm for maximizing a monotone submodular function subject to a matroid constraint, Udwani gave a 0.25-approximation algorithm for submodular order functions maximization subject to a matroid constraint. Based on the above results, we would like to explore further in which cases it is feasible to generalize from streaming submodular maximization algorithms to submodular order maximization algorithms. As a more general constraint than matroid, p-matchoid is a collection of p matroids with each matroid defined on some subsets of the ground set. Related work gave a 1/4p-approximation streaming algorithm for monotone submodular functions maximization under a p-matchoid constraint. Inspired by the above algorithms and the intriguing connection, we used some techniques to try to generalize several streaming algorithms for submodular functions to the offline algorithms for submodular order functions, including interleaved partitions and incremental values. Assuming that the objective function f is subadditive and non-negative, we gave a 1/4p-approximation algorithm for monotone submodular order maximization to a p-matchoid constraint. In addition, we summarize the failures of other cases.
Cited by 0Open access
Wu, Yizhan · Aaltodoc (Aalto University) · 2022
Recently, Udwani defined a new class of set functions under monotonicity and subadditivity, called submodular order functions, which is a subfamily of submodular functions. Informally, the submodular order function admits a very limited form of submodularity which is defined over a specific permutation of the ground set. His work pointed out the intriguing connection between streaming submodular maximization and submodular order maximization. Inspired by a 0.25-approximation streaming algorithm for maximizing a monotone submodular function subject to a matroid constraint, Udwani gave a 0.25-approximation algorithm for submodular order functions maximization subject to a matroid constraint. Based on the above results, we would like to explore further in which cases it is feasible to generalize from streaming submodular maximization algorithms to submodular order maximization algorithms. As a more general constraint than matroid, p-matchoid is a collection of p matroids with each matroid defined on some subsets of the ground set. Related work gave a 1/4p-approximation streaming algorithm for monotone submodular functions maximization under a p-matchoid constraint. Inspired by the above algorithms and the intriguing connection, we used some techniques to try to generalize several streaming algorithms for submodular functions to the offline algorithms for submodular order functions, including interleaved partitions and incremental values. Assuming that the objective function f is subadditive and non-negative, we gave a 1/4p-approximation algorithm for monotone submodular order maximization to a p-matchoid constraint. In addition, we summarize the failures of other cases.
Cited by 0
Francis Bach · arXiv (Cornell University) · 2015
Submodular set-functions have many applications in combinatorial optimization, as they can be minimized and approximately maximized in polynomial time. A key element in many of the algorithms and analyses is the possibility of extending the submodular set-function to a convex function, which opens up tools from convex optimization. Submodularity goes beyond set-functions and has naturally been considered for problems with multiple labels or for functions defined on continuous domains, where it corresponds essentially to cross second-derivatives being nonpositive. In this paper, we show that most results relating submodularity and convexity for set-functions can be extended to all submodular functions. In particular, (a) we naturally define a continuous extension in a set of probability measures, (b) show that the extension is convex if and only if the original function is submodular, (c) prove that the problem of minimizing a submodular function is equivalent to a typically non-smooth convex optimization problem, and (d) propose another convex optimization problem with better computational properties (e.g., a smooth dual problem). Most of these extensions from the set-function situation are obtained by drawing links with the theory of multi-marginal optimal transport, which provides also a new interpretation of existing results for set-functions. We then provide practical algorithms to minimize generic submodular functions on discrete domains, with associated convergence rates.
Cited by 31Open access