Shaojie Tang · arXiv (Cornell University) · 2018
CMO Council reports that 71\% of internet users in the U.S. were influenced by coupons and discounts when making their purchase decisions. It has also been shown that offering coupons to a small fraction of users (called seed users) may affect the purchase decisions of many other users in a social network. This motivates us to study the optimal coupon allocation problem, and our objective is to allocate coupons to a set of users so as to maximize the expected cascade. Different from existing studies on influence maximizaton (IM), our framework allows a general utility function and a more complex set of constraints. In particular, we formulate our problem as an approximate submodular maximization problem subject to matroid and knapsack constraints. Existing techniques relying on the submodularity of the utility function, such as greedy algorithm, can not work directly on a non-submodular function. We use $ε$ to measure the difference between our function and its closest submodular function and propose a novel approximate algorithm with approximation ratio $β(ε)$ with $\lim_{ε\rightarrow 0}β(ε)=1-1/e$. This is the best approximation guarantee for approximate submodular maximization subject to a partition matroid and knapsack constraints, our results apply to a broad range of optimization problems that can be formulated as an approximate submodular maximization problem.
Cited by 0Open access
Ruidong Yan, Yi Li, Weili Wu et al. · ACM Transactions on Knowledge Discovery from Data · 2019
In recent years, social networks have become important platforms for people to disseminate information. However, we need to take effective measures such as blocking a set of links to control the negative rumors spreading over the network. In this article, we propose a Rumor Spread Minimization (RSM) problem, i.e., we remove an edge set from network such that the rumor spread is minimized. We first prove the objective function of RSM problem is not submodular. Then, we propose both submodular lower-bound and upper-bound of the objective function. Next, we develop a heuristic algorithm to approximate the objective function. Furthermore, we reformulate our objective function as the DS function (the Difference of Submodular functions). Finally, we conduct experiments on real-world datasets to evaluate our proposed method. The experiment results show that the upper and lower bounds are very close, which indicates the good quality of them. And, the proposed method outperforms the comparison methods.
Cited by 73Open access
Zhongzheng Tang, Jingwen Chen, Chenhao Wang · Theoretical Computer Science · 2023
A k-submodular function takes k distinct, non-overlapping subsets of a ground set as input and outputs a value. It is a generalization of the well-known submodular function, which is the case when k=1 and takes a single subset as input. We study the problem of maximizing a non-negative k-submodular function under a knapsack constraint. Greedy+Singleton is an algorithm that chooses the better solution between the fully greedy solution and the best single-element solution, with query complexity and running time of O(n2k). We show that Greedy+Singleton has an approximation ratio of 0.273 for monotone functions, which improves the previous analysis of 0.158 in the literature. Moreover, we give the first analysis of Greedy+Singleton for non-monotone k-submodular functions, and prove an approximation ratio of 0.219.
Cited by 2Open access
Andrei Graur, Tristan Pollner, V. Ramaswamy et al. · arXiv (Cornell University) · 2019
We consider submodular function minimization in the oracle model: given black-box access to a submodular set function $f:2^{[n]}\rightarrow \mathbb{R}$, find an element of $\arg\min_S \{f(S)\}$ using as few queries to $f(\cdot)$ as possible. State-of-the-art algorithms succeed with $\tilde{O}(n^2)$ queries [LeeSW15], yet the best-known lower bound has never been improved beyond $n$ [Harvey08]. We provide a query lower bound of $2n$ for submodular function minimization, a $3n/2-2$ query lower bound for the non-trivial minimizer of a symmetric submodular function, and a $\binom{n}{2}$ query lower bound for the non-trivial minimizer of an asymmetric submodular function. Our $3n/2-2$ lower bound results from a connection between SFM lower bounds and a novel concept we term the cut dimension of a graph. Interestingly, this yields a $3n/2-2$ cut-query lower bound for finding the global mincut in an undirected, weighted graph, but we also prove it cannot yield a lower bound better than $n+1$ for $s$-$t$ mincut, even in a directed, weighted graph.
Cited by 2Open access
Qi Zhang, Hao Zhong · INNO-PRESS Journal of Emerging Applied AI · 2025
Quasi-submodularity is a unified measurement to characterize submodularity or approximate submodularity of a set function. In this paper, we consider a variant of Minimum Cardinality Cover named Minimum Cardinality Multiple Quasi-submodular Cover, which requires to find the smallest subset of given ground set such that multiple quasi-submodular functions reach a maximum. We design and analyze a greedy approximation algorithm for Minimum Cardinality Multiple Quasi-submodular Cover. As some applications of our results, we achieve a O(ln n)-approximation algorithm for Minimum Resolving Restrained Dominating Set, and a O(ln delta)-approximation algorithm for Minimum Dominating Set in multiplex networks, where $n$ is the node number and delta is the maximum node degree of the input graph.
Cited by 0Open access
Hiroshi Nagamochi · 2007
Abstract: Let f be a set function on a finite set V.Apair{u, v} ⊆V is called flat in f if f(X) ≥ minx∈X f({x}) holds for all subsets X ⊆ V with |X ∩{u, v} | =1. A subset X ⊆ V is called an extreme subset of f if f(Y)>f(X) holds for all nonempty and proper subsets Y of X. In this paper, we first define a minimum degree ordering (MD ordering) of V, and show that the last two elements in an MD ordering give a flat pair of f if f is symmetric and crossing submodular. Based on this, we then give a simple O(|V | 3)-oracle time algorithm for computing all extreme subsets of a set function g if g is symmetric and crossing submodular or intersecting submodular and posi-modular.
Cited by 1
Hao-Hsiang Wu, Si̇mge Küçükyavuz · arXiv (Cornell University) · 2019
We consider a class of risk-averse submodular maximization problems (RASM) where the objective is the conditional value-at-risk (CVaR) of a random nondecreasing submodular function at a given risk level. We propose valid inequalities and an exact general method for solving RASM under the assumption that we have an efficient oracle that computes the CVaR of the random function. We demonstrate the proposed method on a stochastic set covering problem that admits an efficient CVaR oracle for the random coverage function.
Cited by 0Open access
Andrew Downie, Bahman Gharesifard, Stephen L. Smith · 2022 IEEE 61st Conference on Decision and Control (CDC) · 2022
We consider a class of submodular maximization problems in which decision-makers have limited access to the objective function. We explore scenarios where the decision-maker has access to only k-wise information about the objective function; that is, they can evaluate the submodular objective function on sets of size at most k. We begin with a negative result that no algorithm using only k-wise information can guarantee performance better than k/n, where n is the size of the selected set. We present an algorithm that utilizes only k-wise information about the function and characterizes its performance relative to the optimal, which depends on a new notion of curvature of the submodular function. Finally, we present an experiment in maximum entropy sampling that highlight the approximation performance of our proposed algorithm.
Cited by 1
Qimeng Yu, Si̇mge Küçükyavuz · arXiv (Cornell University) · 2020
A natural and important generalization of submodularity -- $k$-submodularity -- applies to set functions with $k$ arguments and appears in a broad range of applications, such as infrastructure design, machine learning, and healthcare. In this paper, we study maximization problems with $k$-submodular objective functions. We propose valid linear inequalities, namely the $k$-submodular inequalities, for the hypograph of any $k$-submodular function. This class of inequalities serves as a novel generalization of the well-known submodular inequalities. We show that maximizing a $k$-submodular function is equivalent to solving a mixed-integer linear program with exponentially many $k$-submodular inequalities. Using this representation in a delayed constraint generation framework, we design the first exact algorithm, that is not a complete enumeration method, to solve general $k$-submodular maximization problems. Our computational experiments on the multi-type sensor placement problems demonstrate the efficiency of our algorithm in constrained nonlinear $k$-submodular maximization problems for which no alternative compact mixed-integer linear formulations are available. The computational experiments show that our algorithm significantly outperforms the only available exact solution method -- exhaustive search. Problems that would require over 13 years to solve by exhaustive search can be solved within ten minutes using our method.
Cited by 2Open access
K.S. Kumar, Francis Bach · arXiv (Cornell University) · 2015
We consider the submodular function minimization (SFM) and the quadratic minimization problemsregularized by the Lov'asz extension of the submodular function. These optimization problemsare intimately related; for example,min-cut problems and total variation denoising problems, wherethe cut function is submodular and its Lov'asz extension is given by the associated total variation.When a quadratic loss is regularized by the total variation of a cut function, it thus becomes atotal variation denoising problem and we use the same terminology in this paper for "general" submodularfunctions. We propose a new active-set algorithm for total variation denoising with theassumption of an oracle that solves the corresponding SFM problem. This can be seen as localdescent algorithm over ordered partitions with explicit convergence guarantees. It is more flexiblethan the existing algorithms with the ability for warm-restarts using the solution of a closely relatedproblem. Further, we also consider the case when a submodular function can be decomposed intothe sum of two submodular functions F1 and F2 and assume SFM oracles for these two functions.We propose a new active-set algorithm for total variation denoising (and hence SFM by thresholdingthe solution at zero). This algorithm also performs local descent over ordered partitions and itsability to warm start considerably improves the performance of the algorithm. In the experiments,we compare the performance of the proposed algorithms with state-of-the-art algorithms, showingthat it reduces the calls to SFM oracles.
Cited by 2Open access
Hassan Jaleel, Jeff S. Shamma · arXiv (Cornell University) · 2017
We develop a framework for the distributed minimization of submodular functions. Submodular functions are a discrete analog of convex functions and are extensively used in large-scale combinatorial optimization problems. While there has been significant interest in the distributed formulations of convex optimization problems, distributed minimization of submodular functions has received relatively little research attention. Our framework relies on an equivalent convex reformulation of a submodular minimization problem, which is efficiently computable. We then use this relaxation to exploit methods for the distributed optimization of convex functions. The proposed framework is applicable to submodular set functions as well as to a wider class of submodular functions defined over certain lattices. We also propose an approach for solving distributed motion coordination problems in discrete state space based on submodular function minimization. We establish through a challenging setup of capture the flag game that submodular functions over lattices can be used to design artificial potential fields over discrete state space in which the agents are attracted towards their goals and are repulsed from obstacles and from each other for collision avoidance.
Cited by 3Open access
Francis Bach · Foundations and Trends® in Machine Learning · 2013
Submodular functions are relevant to machine learning for at least two\nreasons: (1) some problems may be expressed directly as the optimization of\nsubmodular functions and (2) the lovasz extension of submodular functions\nprovides a useful set of regularization functions for supervised and\nunsupervised learning. In this monograph, we present the theory of submodular\nfunctions from a convex analysis perspective, presenting tight links between\ncertain polyhedra, combinatorial optimization and convex optimization problems.\nIn particular, we show how submodular function minimization is equivalent to\nsolving a wide variety of convex optimization problems. This allows the\nderivation of new efficient algorithms for approximate and exact submodular\nfunction minimization with theoretical guarantees and good practical\nperformance. By listing many examples of submodular functions, we review\nvarious applications to machine learning, such as clustering, experimental\ndesign, sensor placement, graphical model structure learning or subset\nselection, as well as a family of structured sparsity-inducing norms that can\nbe derived and used from submodular functions.\n
Cited by 199Open access
Emma Pollard, Mokshay Madiman · 2023
We prove a new class of inequalities for submodular set functions, indexed by chordal graphs. Since entropy is a particularly useful example of a submodular function, we deduce some entropy inequalities. As a further corollary, we construct a novel family of determinant inequalities for sums of positive definite Hermitian matrices, and also recover an inequality of Barrett, Johnson, and Lundquist (1989).
Cited by 0
Bommireddi, Venkata Abhinav · UWSpace (University of Waterloo) · 2017
We show that for any constants $\\epsilon > 0$ and $p \\ge 1$, given oracle access to an unknown function $f : \\{0,1\\}^n \\to [0,1]$ it is possible to determine if the function is submodular or is $\\epsilon$-far from every submodular function, in $\\ell_p$ distance, with a \\emph{constant} number of queries to the oracle. We refer to the process of determining if an unknown function has a property, or is far from every function having the property, as \\emph{property testing}, and we refer to the algorithm that does that as a tester or a testing algorithm. \n \n A function $f : \\{0,1\\}^n \\to [0,1]$ is a \\emph{$k$-junta} if there is a set $J \\subseteq [n]$ of cardinality $|J| \\le k$ such that the value of $f$ on any input $x$ is completely determined by the values $x_i$ for $i \\in J$. For any constant $\\epsilon > 0$ and a set of $k$-juntas $\\mathcal{F}$, we give an algorithm which determines if an unknown function $f : \\{0,1\\}^n \\to [0,1]$ is $\\frac{\\epsilon}{10^6}$-close to some function in $\\mathcal{F}$ or is $\\epsilon$-far from every function in $\\mathcal{F}$, in $\\ell_2$ distance, with a constant number of queries to the unknown function. This result, combined with a recent junta theorem of Feldman and \\Vondrak (2016) in which they show every submodular function is $\\epsilon$-close, in $\\ell_2$ distance, to another submodular function which is a $\\tilde{O}(\\frac{1}{\\epsilon^2})$-junta, yields the constant-query testing algorithm for submodular functions. \n \nWe also give constant-query testing algorithms for a variety of other natural properties of valuation functions, including fractionally additive (XOS) functions, OXS functions, unit demand functions, coverage functions, and self-bounding functions.
Cited by 0Open access
Kevin M. Byrnes · ArXiv.org · 2009
We present a branch and bound method for maximizing an arbitrary set function h mapping 2^V to R. By decomposing h as f-g, where f is a submodular function and g is the cut function of a (simple, undirected) graph G with vertex set V, our original problem is reduced to a sequence of submodular maximization problems. We characterize a class of submodular functions, which when maximized in the subproblems, lead the algorithm to converge to a global maximizer of f-g. Two "natural" members of this class are analyzed; the first yields polynomially-solvable subproblems, the second, which requires less branching, yields NP-hard subproblems but is amenable to a polynomial-time approximation algorithm. These results are extended to problems where the solution is constrained to be a member of a subset system. Structural properties of the maximizer of f-g are also proved.
Cited by 1Open access
Kristã³f Bã©rczi, Tamã¡s Kirã¡ly, Daniel P. Szabo et al. · Theoretical Computer Science · 2026
The submodular partitioning problem asks to minimize, over all partitions P of a ground set V , the sum of a given submodular function f over the parts of P . The problem has seen considerable work in approximability, as it encompasses multiterminal cuts on graphs, k -cuts on hypergraphs, and elementary linear algebra problems such as matrix multiway partitioning. This research has been divided between the fixed terminal setting, where we are given a set of terminals that must be separated by P , and the global setting, where the only constraint is the size of the partition. We investigate a generalization that unifies these two settings: minimum submodular matroid-constrained partition. In this problem, we are additionally given a matroid over the ground set and seek to find a partition P in which there exists some basis that is separated by P . We explore the approximability of this problem and its variants for general, symmetric, and monotone submodular functions.
Cited by 0Open access
Tengyu Ma, Bo Tang, Yajun Wang · 2011
We study the matroid secretary problems with submodular valuation functions. In these prob-lems, the elements arrive in random order. When one element arrives, we have to make an immediate and irrevocable decision on whether to accept it or not. The set of accepted elements must form an independent set in a predefined matroid. Our objective is to maximize the value of the accepted elements. In this paper, we focus on the case that the valuation function is a non-negative and monotonically non-decreasing submodular function. We introduce a general algorithm for such submodular matroid secretary problems. In particu-lar, we obtain constant competitive algorithms for the cases of laminar matroids and transversal matroids. Our algorithms can be further applied to any independent set system defined by the intersection of a constant number of laminar matroids, while still achieving constant competitive ratios. Notice that laminar matroids generalize uniform matroids and partition matroids. On the other hand, when the underlying valuation function is linear, our algorithm achieves a competitive ratio of 9.6 for laminar matroids, which significantly improves the previous result.
Cited by 0
Genkin, Alexander Veniaminovich · OpenGrey (Institut de l'Information Scientifique et Technique) · 1995
The methods suggested make it possible to find clasters with the given properties and to optimize sets of solution rules for voting algorithms of recognition. Algorithms, realizing the methods suggested, have been constructed. The notion of the t-stable set has been introduced. Some methods and practical problems for the analysis of data have been represented in the form of the search of t-stable sets, in particular, maximum of a submodular function. The construction problem of a set of partial solutions for the voting has been conversed to maximization of a submodular function. The way of maximization - the method of the distributed teaching has been suggested. The generalization of the hierarchical claster analysis, generalization permitting clasters, crossing on a one level, and incomplete classifications, has been constructed. The optimum algorithm for the search of maximum of a submodular function has been constructed. The paper results may find their field of application in medicine, geology and other fields
Cited by 0
Piotr Skowron · arXiv (Cornell University) · 2015
We investigate the existence of approximation algorithms for maximization of submodular functions, that run in fixed parameter tractable (FPT) time. Given a non-decreasing submodular set function $v: 2^X \to \mathbb{R}$ the goal is to select a subset $S$ of $K$ elements from $X$ such that $v(S)$ is maximized. We identify three properties of set functions, referred to as $p$-separability properties, and we argue that many real-life problems can be expressed as maximization of submodular, $p$-separable functions, with low values of the parameter $p$. We present FPT approximation schemes for the minimization and maximization variants of the problem, for several parameters that depend on characteristics of the optimized set function, such as $p$ and $K$. We confirm that our algorithms are applicable to a broad class of problems, in particular to problems from computational social choice, such as item selection or winner determination under several multiwinner election systems.
Cited by 0Open access
Stephan Földes · 2001
Efficient algorithms that solve the generally hard set function minimization problem for certain special classes of functions, such as submodular functions, necessarily require the knowledge that the objective function belongs to the special class.
Cited by 0