Lu Han, Min Li, Dachuan Xu et al. · Journal of Industrial and Management Optimization · 2020
<p style='text-indent:20px;'>The problem of maximizing a given set function with a cardinality constraint has widespread applications. A number of algorithms have been provided to solve the maximization problem when the set function is monotone and submodular. However, reality-based set functions may not be submodular and may involve large-scale and noisy data sets. In this paper, we present the Stochastic-Lazier-Greedy Algorithm (SLG) to solve the corresponding non-submodular maximization problem and offer a performance guarantee of the algorithm. The guarantee is related to a submodularity ratio, which characterizes the closeness of to submodularity. Our algorithm also can be viewed as an extension of several previous greedy algorithms.
Cited by 1Open access
Lecturer Lap, Chi Lau, Scribe Sean et al. · 2008
In this lecture, the focus is on submodular function in combinatorial optimizations. The first class of submodular functions which was studied thoroughly was the class of matroid rank functions. The flourishing stage of matroid theory came with Jack Edmonds ’ work in 1960s, when he gave a minmax formula and an efficient algorithm to the matroid partition problem, from which the matroid intersection theorem and its algorithm can be derived. Generalizing certain basic properties of matroid polyhedra, Edmonds began the systematical study of submodularity. An important work along this line is Edmonds and Giles ’ 1977 paper on submodular flow, which models a large class of useful and efficiently solvable combinatorial optimization problems. Although we will not introduce matroids in this course, we can still try to see how submodularity provides a unifying theme for many polynomial time solvable problems. 8.1 Submodular Function Let S be a infinite set and f: 2 S → R be a real valued function defined on the subsets of S. The set-function f is called submodular if the following inequality holds for any two subsets X and Y of S: f(X) + f(Y) ≥ f(X ∪ Y) + f(X ∩ Y)
Cited by 0
Yishuo Shi, Hui Zhao · Theoretical Computer Science · 2024
The problem of maximizing submodular set functions has received increasing attention in recent years, and significant improvements have been made, particularly in relation to objective functions that satisfy monotonic submodularity. However, in practice, the objective function may not be monotonically submodular. While greedy algorithms have strong theoretical guarantees for maximizing submodular functions, their performance is barely guaranteed for non-submodular functions. Therefore, in this paper, we investigate the problem of maximizing non-monotone non-submodular functions under knapsack constraints based on the problem of infectious diseases and provides a more sophisticated analysis through the idea of segmentation. Since our definition characterizes the function more elaborately, a better bound, i.e., a tighter approximation guarantee, is achieved. Finally, we generalize the relevant results for the more general problems.
Cited by 2Open access
Qiqiang Hou, Andrew Clark · 2019
Submodular maximization has applications in networked control, data summarization, and path planning, among other areas. While several efficient algorithms with provable optimality bounds have been developed for maximizing a single submodular function, the more computationally challenging problem of maximizing the minimum of a set of submodular functions (robust submodular maximization) has received less research attention. In this paper, we investigate robust submodular maximization when the objective functions are correlated, i.e., the marginal benefits of adding elements to each function are within a given ratio of each other. We propose a modified greedy algorithm that exploits the correlation ratio to achieve a provable optimality bound. As a case study, we consider minimization of graph effective resistance, and derive bounds on the correlation ratio using the graph spectrum. Our results are evaluated through numerical study.
Cited by 1
Harb, Elfarouk, Yassin, Yousef, Chekuri, Chandra · arXiv (Cornell University) · 2025
We study the problem of minimizing or maximizing the average value $ f(S)/|S| $ of a submodular or supermodular set function $ f: 2^V \to \mathbb{R} $ over non-empty subsets $ S \subseteq V $. This generalizes classical problems such as Densest Subgraph (DSG), Densest Supermodular Set (DSS), and Submodular Function Minimization (SFM). Motivated by recent applications, we introduce two broad formulations: Unrestricted Sparsest Submodular Set (USSS) and Unrestricted Densest Supermodular Set (UDSS), which allow for negative and non-monotone functions. We show that DSS, SFM, USSS, UDSS, and the Minimum Norm Point (MNP) problem are equivalent under strongly polynomial-time reductions, enabling algorithmic crossover. In particular, viewing these through the lens of the MNP in the base polyhedron, we connect Fujishige's theory with dense decomposition, and show that both Fujishige-Wolfe's algorithm and the heuristic \textsc{SuperGreedy++} act as universal solvers for all these problems, including sub-modular function minimization. Theoretically, we explain why \textsc{SuperGreedy++} is effective beyond DSS, including for tasks like submodular minimization and minimum $ s $-$ t $ cut. Empirically, we test several solvers, including the Fujishige-Wolfe algorithm on over 400 experiments across seven problem types and large-scale real/synthetic datasets. Surprisingly, general-purpose convex and flow-based methods outperform task-specific baselines, demonstrating that with the right framing, general optimization techniques can be both scalable and state-of-the-art for submodular and supermodular ratio problems.
Cited by 0Open access
Mohammad Mamun Ur Rashid, Elahe Ghasemi, Javad B. Ebrahimi · 2022
It is known that the entropy function over a set of jointly distributed random variables is a submodular set function. However, not any submodular function is of this form. In this paper, we consider a family of submodular set functions, called weighted rank functions of matroids, and study the necessary or sufficient conditions under which they are entropic. We prove that weighted rank functions are located on the boundary of the submodularity cone. For the representable matroids over a characteristic 2 field, we show that the integer valued weighted rank functions are entropic. We derive a necessary condition for constant weight rank functions to be entropic and show that for the case of graphic matroids, this condition is indeed sufficient. Since these functions generalize the rank of a matroid, our findings generalize some of the results of Abbe et. al. in [1] about entropic properties of the rank function of matroids.
Cited by 0
Shaojing Du, Bo Hou · Journal of Combinatorial Mathematics and Combinatorial Computing · 2024
In this paper, we study the submodular hitting set problem (SHSP), which is a variant of the hitting set problem. In the SHSP, we are given a supergraph H = ( V , C ) and a nonnegative submodular function on the set 2 V . The objective is to determine a vertex subset to cover all hyperedges such that the cost of submodular covering is minimized. Our main work is to present a rounding algorithm and a primal-dual algorithm respectively for the SHSP and prove that they both have the approximation ratio k , where k is the maximum number of vertices in all hyperedges.
Cited by 0Open access
Andrew Clark, Basel Alomair, Linda Bushnell et al. · 2014
Maximization of submodular set functions arises in wireless applications such as scheduling, caching, and leader selection. For a centralized entity with oracle access to the submodular function, submodular maximization can be approximated up to a constant factor using polynomial-time algorithms; such an entity, however, may be unavailable in decentralized wireless networks. In this paper, we consider maximization of a time-varying submodular function by distributed, resource-constrained nodes. We present algorithms for unconstrained distributed submodular maximization, as well as monotone submodular maximization subject to cardinality constraints. For the unconstrained submodular maximization problem, our algorithm achieves an expected optimality gap of 1/3. For cardinality-constrained submodular maximization, our algorithm achieves an expected optimality gap of 1/2, while reducing the storage and communication overhead, as well as the computation requirements of the nodes, compared to existing techniques. We evaluate our approach through an experimental study using sensor scheduling data, and find that our approach is within ten percent of the best achievable utility in the unconstrained case and within five percent in the constrained case.
Cited by 6
Jegelka, S. · MPG.PuRe (Max Planck Society) · 2011
Combinatorial problems with submodular cost functions have recently drawn interest. In a standard combinatorial problem, the sum-of-weights cost is replaced by a submodular set function. The result is a powerful model that is though very hard. In this talk, I will introduce cooperative cuts, minimum cuts with submodular edge weights. I will outline methods to approximately solve this problem, and show an application in computer vision. If time permits, the talk will also sketch regret-minimizing online algorithms for submodular-cost combinatorial problems. This is joint work with Jeff Bilmes (University of Washington).
Cited by 0
Harb, Elfarouk, Yassin, Yousef, Chekuri, Chandra · ArXiv.org · 2025
We study the problem of minimizing or maximizing the average value $ f(S)/|S| $ of a submodular or supermodular set function $ f: 2^V \to \mathbb{R} $ over non-empty subsets $ S \subseteq V $. This generalizes classical problems such as Densest Subgraph (DSG), Densest Supermodular Set (DSS), and Submodular Function Minimization (SFM). Motivated by recent applications, we introduce two broad formulations: Unrestricted Sparsest Submodular Set (USSS) and Unrestricted Densest Supermodular Set (UDSS), which allow for negative and non-monotone functions. We show that DSS, SFM, USSS, UDSS, and the Minimum Norm Point (MNP) problem are equivalent under strongly polynomial-time reductions, enabling algorithmic crossover. In particular, viewing these through the lens of the MNP in the base polyhedron, we connect Fujishige's theory with dense decomposition, and show that both Fujishige-Wolfe's algorithm and the heuristic \textsc{SuperGreedy++} act as universal solvers for all these problems, including sub-modular function minimization. Theoretically, we explain why \textsc{SuperGreedy++} is effective beyond DSS, including for tasks like submodular minimization and minimum $ s $-$ t $ cut. Empirically, we test several solvers, including the Fujishige-Wolfe algorithm on over 400 experiments across seven problem types and large-scale real/synthetic datasets. Surprisingly, general-purpose convex and flow-based methods outperform task-specific baselines, demonstrating that with the right framing, general optimization techniques can be both scalable and state-of-the-art for submodular and supermodular ratio problems.
Cited by 0Open access
Sang-Il Oum, Paul Seymour · 2008
Branch-width is defined for graphs, matroids, and, more generally, arbitrary symmetric submodular functions. For a finite set V, a function f on the set of subsets 2 V of V is submodular if f(X) + f(Y) ≥ f(X ∩ Y) + f(X ∪ Y), and symmetric if f(X) = f(V \\ X). We discuss the computational complexity of recognizing that symmetric submodular functions have branch-width at most k for fixed k. An integer-valued symmetric submodular function f on 2 V is a connectivity function if f(∅) = 0 and f({v}) ≤ 1 for all v ∈ V. We show that for each constant k, if a connectivity function f on 2 V is presented by an oracle and the branch-width of f is larger than k, then there is a certificate of polynomial size (in |V |) such that a polynomialtime algorithm can verify the claim that branch-width of f is larger than k. In particular it is in coNP to recognize matroids represented over a fixed field with branch-width at most k for fixed k.
Cited by 0
Zhu, Yanhui, Basu, Samik, Pavan, A. · arXiv (Cornell University) · 2024
Submodular optimization finds applications in machine learning and data mining. In this paper, we study the problem of maximizing functions of the form $h = f-c$, where $f$ is a monotone, non-negative, weakly submodular set function and $c$ is a modular function. We design a deterministic approximation algorithm that runs with ${O}(\frac{n}ε\log \frac{n}{γε})$ oracle calls to function $h$, and outputs a set ${S}$ such that $h({S}) \geq γ(1-ε)f(OPT)-c(OPT)-\frac{c(OPT)}{γ(1-ε)}\log\frac{f(OPT)}{c(OPT)}$, where $γ$ is the submodularity ratio of $f$. Existing algorithms for this problem either admit a worse approximation ratio or have quadratic runtime. We also present an approximation ratio of our algorithm for this problem with an approximate oracle of $f$. We validate our theoretical results through extensive empirical evaluations on real-world applications, including vertex cover and influence diffusion problems for submodular utility function $f$, and Bayesian A-Optimal design for weakly submodular $f$. Our experimental results demonstrate that our algorithms efficiently achieve high-quality solutions.
Cited by 0Open access
Peter Stobbe · 2013
The connections between convexity and submodularity are explored, for purposes of minimizing and learning submodular set functions. First, we develop a novel method for minimizing a particular class of submodular functions, which can be expressed as a sum of concave functions composed with modular functions. The basic algorithm uses an accelerated first order method applied to a smoothed version of its convex extension. The smoothing algorithm is particularly novel as it allows us to treat general concave potentials without needing to construct a piecewise linear approximation as with graph-based techniques. Second, we derive the general conditions under which it is possible to find a minimizer of a submodular function via a convex problem. This provides a framework for developing submodular minimization algorithms. The framework is then used to develop several algorithms that can be run in a distributed fashion. This is particularly useful for applications where the submodular objective function consists of a sum of many terms, each term dependent on a small part of a large data set. Lastly, we approach the problem of learning set functions from an unorthodox perspective---sparse reconstruction. We demonstrate an explicit connection between the problem of learning set functions from random evaluations and that of sparse signals. Based on the observation that the Fourier transform for set functions satisfies exactly the conditions needed for sparse reconstruction algorithms to work, we examine some different function classes under which uniform reconstruction is possible.
Cited by 6
Yanhao Wang, Tianchen Zhou, Cen Chen et al. · IEEE Internet of Things Journal · 2023
Submodular maximization is a fundamental problem in many Internet of Things applications, such as sensor placement, resource allocation, and mobile crowdsourcing. Despite being intensively studied over the last two decades, the problem of submodular maximization has not yet been considered in an emerging federated computation setting. In this article, we first comprehensively study federated submodular maximization, where a set of clients aims to cooperate in finding a set of items to maximize a monotone submodular function under the orchestration of a central server while providing strong privacy guarantees for their sensitive data. We consider the problem in a client-level differential privacy (DP) setting: the server is not necessarily trusted and the clients should perturb their results locally before sending them to the server. Specifically, we propose a novel approximation algorithm for federated submodular maximization by incorporating client-level DP mechanisms and decomposed function evaluations into the greedy algorithm, along with two heuristics to further reduce the privacy budget, computational cost, and communication overhead. Finally, we perform extensive experiments to demonstrate the effectiveness and efficiency of our proposed algorithms.
Cited by 3
Stobbe, Peter · CaltechTHESIS (California Institute of Technology) · 2013
The connections between convexity and submodularity are explored, for purposes of minimizing and learning submodular set functions. First, we develop a novel method for minimizing a particular class of submodular functions, which can be expressed as a sum of concave functions composed with modular functions. The basic algorithm uses an accelerated first order method applied to a smoothed version of its convex extension. The smoothing algorithm is particularly novel as it allows us to treat general concave potentials without needing to construct a piecewise linear approximation as with graph-based techniques. Second, we derive the general conditions under which it is possible to find a minimizer of a submodular function via a convex problem. This provides a framework for developing submodular minimization algorithms. The framework is then used to develop several algorithms that can be run in a distributed fashion. This is particularly useful for applications where the submodular objective function consists of a sum of many terms, each term dependent on a small part of a large data set. Lastly, we approach the problem of learning set functions from an unorthodox perspective---sparse reconstruction. We demonstrate an explicit connection between the problem of learning set functions from random evaluations and that of sparse signals. Based on the observation that the Fourier transform for set functions satisfies exactly the conditions needed for sparse reconstruction algorithms to work, we examine some different function classes under which uniform reconstruction is possible.
Cited by 0Open access
Naonori Kakimura, Ildikó Schlotter · arXiv (Cornell University) · 2024
This paper studies the computational complexity of a robust variant of a two-stage submodular minimization problem that we call Robust Submodular Minimizer. In this problem, we are given $k$ submodular functions~$f_1,\dots,f_k$ over a set family~$2^V$, which represent $k$ possible scenarios in the future when we will need to find an optimal solution for one of these scenarios, i.e., a minimizer for one of the functions. The present task is to find a set $X \subseteq V$ that is close to \emph{some} optimal solution for each $f_i$ in the sense that some minimizer of~$f_i$ can be obtained from $X$ by adding/removing at most $d$ elements for a given integer $d \in \mathbb{N}$. The main contribution of this paper is to provide a complete computational map of this problem with respect to parameters~$k$ and~$d$, which reveals a tight complexity threshold for both parameters: (1) Robust Submodular Minimizer can be solved in polynomial time when $k \leq 2$, but is NP-hard if $k$ is a constant with $k \geq 3$.(2)Robust Submodular Minimizer can be solved in polynomial time when $d=0$, but is NP-hard if $d$ is a constant with $d \geq 1$. (3) Robust Submodular Minimizer is fixed-parameter tractable when parameterized by~$(k,d)$. We also show that if some submodular function $f_i$ has a polynomial number of minimizers, then the problem becomes fixed-parameter tractable when parameterized by $d$. On the other hand, the problem remains $\mathsf{W}[1]$-hard parameterized by $k$ even if each function $f_i$ has at most~$|V|$ minimizers. We remark that all our hardness results hold even if each submodular function is given by a cut function of a directed graph.
Cited by 0Open access
Junpei Nakashima, Yukiko Yamauchi, Shuji Kijima et al. · SIAM Journal on Discrete Mathematics · 2020
A set function $f$ on a finite set $V$ is submodular if $f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y)$ for any pair $X, Y \subseteq V$. The symmetric difference transformation (SD-transformation) of $f$ by a canonical set $S \subseteq V$ is a set function $g$ given by $g(X) = f(X \vartriangle S)$ for $X \subseteq V$, where $X \vartriangle S = (X \setminus S) \cup (S \setminus X)$ denotes the symmetric difference between $X$ and $S$. Submodularity and SD-transformations are regarded as the counterparts of convexity and affine transformations in a discrete space, respectively. However, submodularity is not preserved under SD-transformations, in contrast to the fact that convexity is invariant under affine transformations. This paper presents a characterization of SD-transformations preserving submodularity. Then, we are concerned with the problem of discovering a canonical set $S$, given the SD-transformation $g$ of a submodular function $f$ by $S$, provided that $g(X)$ is given by a function value oracle. A submodular function $f$ on $V$ is said to be strict if $f(X) + f(Y) > f(X \cup Y) + f(X \cap Y)$ holds whenever both $X \setminus Y$ and $Y \setminus X$ are nonempty. We show that the problem is solved by using $\mathrm{O}(|V|)$ oracle calls when $f$ is strictly submodular, although it requires exponentially many oracle calls in general.
Cited by 1
Chandra Chekuri, et al. · 2015
We consider the problem of maximizing a nonnegative submodular set function f: 2N → R+ subject to a p-matchoid constraint in the single-pass streaming setting. Previous work in this context has considered streaming algorithms for modular functions and monotone submodular functions. The main result is for submodular functions that are non-monotone. We describe deterministic and randomized algorithms that obtain a Ω(1p)-approximation using O(k log k)-space, where k is an upper bound on the cardinality of the desired set. The model assumes value oracle access to f and membership oracles for the matroids defining the p-matchoid constraint.
Cited by 0
Andreas Krause, Carlos Guestrin · Figshare · 2018
Abstract: "Many set functions F in combinatorial optimization satisfy the diminishing returns property F(A [union of] X) - F(A) [> or =] F(A' [union of] X) - F(A') for A [element of] A'. Such functions are called submodular. A result from Nemhauser et.al. states that the problem of selecting k-element subsets maximizing a nondecreasing submodular function can be approximated with a constant factor (1 - 1/e) performance guarantee. Khuller et.al. showed that for the special submodular function involved in the MAX-COVER problem, this approximation result generalizes to a budgeted setting under linear nonnegative cost-functions. In this note, we extend this result to general submodular functions. Motivated by the problem of maximizing entropy in discrete graphical models, where the submodular objective cannot be evaluated exactly, we generalize our result to account for absolute errors."
Cited by 132Open access
Shaojie Tang · arXiv (Cornell University) · 2021
The goal of a sequential decision making problem is to design an interactive policy that adaptively selects a group of items, each selection is based on the feedback from the past, in order to maximize the expected utility of selected items. It has been shown that the utility functions of many real-world applications are adaptive submodular. However, most of existing studies on adaptive submodular optimization focus on the average-case. Unfortunately, a policy that has a good average-case performance may have very poor performance under the worst-case realization. In this study, we propose to study two variants of adaptive submodular optimization problems, namely, worst-case adaptive submodular maximization and robust submodular maximization. The first problem aims to find a policy that maximizes the worst-case utility and the latter one aims to find a policy, if any, that achieves both near optimal average-case utility and worst-case utility simultaneously. We introduce a new class of stochastic functions, called \emph{worst-case submodular function}. For the worst-case adaptive submodular maximization problem subject to a $p$-system constraint, we develop an adaptive worst-case greedy policy that achieves a $\frac{1}{p+1}$ approximation ratio against the optimal worst-case utility if the utility function is worst-case submodular. For the robust adaptive submodular maximization problem subject to cardinality constraints (resp. partition matroid constraints), if the utility function is both worst-case submodular and adaptive submodular, we develop a hybrid adaptive policy that achieves an approximation close to $1-e^{-\frac{1}{2}}$ (resp. $1/3$) under both worst- and average-case settings simultaneously. We also describe several applications of our theoretical results, including pool-base active learning, stochastic submodular set cover and adaptive viral marketing.
Cited by 0Open access