Abstract
In this paper, we study the problem of maximizing a monotone non-decreasing submodular function \(f :2^\Omega \rightarrow {\mathbb {R}}_{+}\) subject to a cardinality constraint, i.e., \(\max \{ f(A) : |A| \le k, A \subseteq \Omega \} \). We propose a deterministic algorithm based on a new greedy strategy for solving this problem. We prove that when the objective function f satisfies certain assumptions, the algorithm we propose can return a \(1 - \kappa _f (1 - \frac{1}{k})^k\) approximate solution with O(kn) value oracle queries, where \(\kappa _f\) is the curvature of the monotone submodular function f. We also show that our algorithm outperforms the traditional greedy algorithm in some cases. Furthermore, we demonstrate how to implement our algorithm in practice.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
A set function is called submodular if it satisfies the diminishing returns property, which is a common notion in various disciplines such as economics, combinatorics and machine learning. Submodular functions arise naturally from combinatorial optimization as several combinatorial functions turn out to be submodular. A few examples of such functions include rank functions of matroids, cut functions of graphs and di-graphs, entropy functions and covering functions. Thus, combinatorial optimization problems with a submodular objective function are essentially submodular optimization problems. Unlike minimization of submodular functions which can be done in polynomial time [6, 8, 16], submodular maximization problems are usually NP-hard, for many classes of submodular functions, such as weighted coverage [3] or mutual information [12].
In this paper, we study the most prestigious submodular maximization problem :
where \(f :2^\Omega \rightarrow {\mathbb {R}}_{+}\) is a non-negative, monotone non-decreasing, submodular function. This problem not only captures many combinatorial optimization problems including Max-k-Coverage [10], Max-Bisection [5] and Max-Cut [1], but also has wide applications in viral marketing [9], sensor placement [13], and machine learning [11, 14].
1.1 Related works
The study of monotone submodular maximization subject to a cadinality constraint has a long history. In order to tackle Problem (1), Nemhauser et al. [15] designed an algorithm based on greedy strategy. Their main idea is to construct the solution to Problem (1) from an empty set, and iteratively augment the feasible solution with an element which has the maximum marginal gain with respect to the current solution in each iteration step. The greedy algorithm terminates when it finishes k iterations and returns a \(1 - (1 - \frac{1}{k})^k \approx 1 - \frac{1}{e} \) approximate solution for Problem (1). The results of Nemhauser et al. are not only of great theoretical significance, but also of practical value since the greedy algorithm they designed only requires O(kn) value oracle queries.
By introducing the concept of curvature, Conforti and Cornuéjols [2] proved that the greedy algorithm proposed by Nemhauser et al. [15] can actually return a \( \frac{1}{\kappa _f} [ 1 - (1 - \frac{\kappa _f}{k})^k ] \approx \frac{1}{\kappa _f} (1 - e^{-\kappa _f} )\) approximate solution for Problem (1), where \(\kappa _f\) is the curvature of function f. Moreover, Conforti and Cornuéjols [2] described a family of worst-case examples on which the greedy algorithm can only achieve the approximation ratio of \( \frac{1}{\kappa _f} [ 1 - (1 - \frac{\kappa _f}{k})^k ]\), which indicates that the bound \( \frac{1}{\kappa _f} [ 1 - (1 - \frac{\kappa _f}{k})^k ]\) is tight when utilizing the greedy algorithm to solve Problem (1). The bound \( \frac{1}{\kappa _f} (1 - e^{-\kappa _f} )\) dramatically improves the bound \( 1 - \frac{1}{e} \) due to \(\kappa _f \in [0,1]\) and \(\frac{1}{\kappa _f} (1 - e^{-\kappa _f} ) > 1 - \frac{1}{e}\) for any \(\kappa _f \in [0,1)\). Meanwhile, since the curvature defined by Conforti and Cornuéjols [2] can be computed in linear time with a value oracle access to the objective function, it’s also very attractive in the practical applications of greedy algorithm.
More than three decades later, Sviridenko et al. [17] showed that the bound \( \frac{1}{\kappa _f} (1 - e^{-\kappa _f} )\) is still not tight for Problem (1). They designed a new algorithm for solving Problem (1) and proved that it’s able to achieve an approximation ratio of \(1 - \kappa _f e^{-1}\). Furthermore, they also proved that the \(1 - \kappa _f e^{-1}\) approximation ratioFootnote 1 is the best possible for Problem (1) in the value oracle model. However, since Sviridenko et al. [17] utilized a sophisticated continuous greedy algorithm together with a time-consuming guessing step, their algorithm requires \({\tilde{O}}(n^6 \epsilon ^{-4})\) value oracle queries. Thus, their results are of mainly theoretical interest. Later, Feldman [4] designed a subtle distorted continuous greedy algorithm which can bypass the guessing step. But the optimization of multilinear extension prevents its practical application, since it still requires \({\tilde{O}}(n^5 \epsilon ^{-3})\) value oracle queries.
Harshaw et al. [7] studied a constrained maximization problem
where \(g :2^{\Omega } \rightarrow \mathbb {R}_+\) is a non-negative monotone \(\gamma \)-weakly submodular function and \(c :2^{\Omega } \rightarrow \mathbb {R}_+\) is a non-negative modular function. They introduced a subtle distorted objective function and showed that the distorted greedy algorithm they proposed can return a feasible solution S with \(g(S) - c(S) \ge (1 - e^{-\gamma }) g(OPT) - c(OPT)\). The techniques they used greatly inspired our work.
1.2 Our contributions
We restate the problem we study in this paper,
where \(f :2^\Omega \rightarrow {\mathbb {R}}_{+}\) is a non-negative, monotone non-decreasing, submodular function. Our goal is to design a practical algorithm, which not only achieves the tight bound \(1 - \kappa _f e^{-1}\), but also performs the same O(kn) value oracle queries as the traditional greedy algorithm requires.
Our main results are summerized in the following theorem.
Theorem 1
Given a non-negative, monotone non-decreasing, submodular function \(f :2^\Omega \rightarrow {\mathbb {R}}_{+}\) which satisfies certain assumptionFootnote 2, and a cardinality constraint k. There exists a deterministic algorithm which can return a feasible solution S with
and the algorithm performs O(kn) value oracle queries.
Though we are unable to prove that our algorithm achieves the approximation ratio of \(1 - \kappa _f (1 - \frac{1}{k})^k\) for an arbitrary monotone submodular function, we demonstrate that our algorithm does outperform the traditional greedy algorithm on certain instances.
1.3 Organization
The rest of this paper is organized as follows. In Sect. 2, we give the preliminary definitions and lemmas which will be used throughout the paper. We present an algorithm based on a new greedy strategy for solving Problem (1) and analyze its performance guarantee in Sect. 3. Then, in Sect. 4, we show that the algorithm we propose can outperform the traditional greedy algorithm on particular instances. In Sect. 5, we explain how to implement our algorithm in practice. Finally, we conclude this paper in Sect. 6.
2 Preliminaries
In this section, we describe the notations, definitions and lemmas which we will use in the paper.
2.1 Set functions
Given a set A and an element e, we use \(A+e\) and \(A-e\) as shorthands for the expression \(A \cup \{e\}\) and \(A \setminus \{ e \}\), respectively.
Let \(\Omega \) be a ground set of size n. A set function \(f :2^\Omega \rightarrow \mathbb {R}\) is submodular if and only if \(f(A) + f(B) \ge f(A\cup B) + f(A \cap B)\) for any \(A,B \subseteq \Omega \). Submodularity can equivalently be characterized in terms of marginal gains, which is defined as \(f(e|A) := f(A+e) - f(A)\). Then, f is submodular if and only if \(f(e|A) \ge f(e|B)\) for any \(A \subseteq B \subset \Omega \) and any \(e \in \Omega \setminus B\). We denote the marginal gain of a set B to a set A with respect to function f by \(f(B|A) := f(A \cup B) - f(A)\).
We say that a set function f is monotone non-decreasing if and only if \(f(A) \le f(B)\) for any \(A \subseteq B \subseteq \Omega \). An equivalent definition is that \(f(e|A) \ge 0\) for any \(A \subseteq \Omega \) and any \(e \in \Omega \).
2.2 Curvature
The curvature of a monotone non-decreasing submodular function \(f :2^\Omega \rightarrow \mathbb {R}\) is defined by Conforti and Cornuéjols [2] as
Here, we adopt the convention that \(\frac{0}{0} := 1\).
By the definition of curvature, it holds that \(\kappa _f \in [0,1]\), and a monotone submodular function f is a modular one if and only if \(\kappa _f = 0\). Thus, the curvature of a monotone submodular function indicates how much it differs from a modular function.
Next, we give a lemma pertaining to monotone submodular functions with curvature \(\kappa _f\) which will be useful in the rest of this paper.
Lemma 1
If \(f :2^\Omega \rightarrow \mathbb {R}\) is a monotone non-decreasing submodular function with curvature \(\kappa _f\), then \(\sum _{e \in A} f(e|\Omega - e) \ge (1 - \kappa _f) [f(A) - f(\varnothing ) ]\) for every \(A \subseteq \Omega \).
Proof
By the definition of curvature, we have \(f(e|\Omega - e) \ge (1 - \kappa _f) f(e|\varnothing )\) for every \(e \in \Omega \). It follows that \(\sum _{e \in A} f(e|\Omega - e) \ge (1 - \kappa _f) \sum _{e \in A} f(e|\varnothing ) \). Since f is submodular, it holds that \(\sum _{e \in A} f(e|\varnothing ) \ge f(A) - f(\varnothing )\).
Thus, we get \(\sum _{e \in A} f(e|\Omega - e) \ge (1 - \kappa _f) [f(A) - f(\varnothing ) ]\) for every \(A \subseteq \Omega \). \(\square \)
2.3 Decomposition of Submodular Functions
We present a lemma which is essential in the rest of our analysis.
Lemma 2
Given an arbitrary submodular function \(f :2^\Omega \rightarrow {\mathbb {R}}_{+}\). It can induce a modular function \(c :2^\Omega \rightarrow \mathbb {R}, A \mapsto \sum _{e \in A} f(e | \Omega - e)\). We define a new set function \(g :2^\Omega \rightarrow \mathbb {R}, A \mapsto f(A)-c(A)\). Then, set function g satisfies the following properties:
-
1)
g is a submodular function;
-
2)
g is monotone non-decreasing;
-
3)
g is non-negative.
Proof
-
1)
For any \(A \subseteq B \subseteq \Omega \) and \(e \in \Omega \setminus B\), we have \(g(e|A) = f(e|A)-f(e|\Omega -e) \ge f(e|B)-f(e|\Omega -e) = g(e|B)\) due to the submodularity of f. Thus, g is a submodular function.
-
2)
Since g is submodular, in order to prove that g is monotone non-decreasing, we only have to show that \(g(e|A) \ge 0\) holds for any \(A \subseteq \Omega \) and \(e \in \Omega \). This is true because of the submodularity of f.
-
3)
Since \(g(\varnothing ) = f(\varnothing ) - c(\varnothing ) = f(\varnothing ) \ge 0\), g is non-negative due to the monotonicity of g.
\(\square \)
3 Algorithm
In this section, we propose a deterministic algorithm based on a new greedy strategy for solving the monotone submodular maximization problem subject to a cardinality constraint.
The key technique we use is designing a so-called distorted objective function, which was introduced by Harshaw et al. [7]. Given an arbitrary non-decreasing submodular function \(f :2^\Omega \rightarrow {\mathbb {R}}_{+}\), we firstly define a modular function \(c :2^\Omega \rightarrow \mathbb {R}_+, A \mapsto \sum _{e \in A} f(e | \Omega - e)\). Then, we introduce two important functions \(\Phi \) and \(\Psi \), which is crucial in our algorithms. Let k be the cardinality constraint, for every \(i = 0,1,\ldots ,k\) and every set \(T \subseteq \Omega \), we define
Furthermore, for every iteration \(i = 0,1,\ldots ,k-1\) of our algorithms, every set \(T \subseteq \Omega \), and every element \(e \in \Omega \), we define
Our algorithm is presented as Algorithm 2. Compared with the traditional greedy algorithm which is presented as Algorithm 1, Algorithm 2 chooses an element \(e_i\) maximizing the marginal gain of the distorted objective functionFootnote 3, instead of choosing an element which maximizes the marginal gain of the original objective function f with respect to the current solution. Specifically, the marginal increase of the distorted objective function is a convex combination of the marginal gain with respect to the current solution and the minimum marginal gain when adding this particular element. Intuitively, in each iteration step, Algorithm 2 doesn’t pay all attention to the marginal gain with respect to the current solution, but ‘looks far’. This slight modification does lead to an improved approximation ratio under certain circumstances.
Before analyzing the performance guarantee of Algorithm 2, we notice that when f is a modular function, the greedy strategy (i.e., \(e_i \leftarrow \mathrm {argmax}_{e\in \Omega \setminus S_i} \{ \Psi _i(e|S_i) \}\)) adopted by Algorithm 2 is exactly the same as the greedy strategy (i.e., \(e_i \leftarrow \mathrm {argmax}_{e\in \Omega \setminus S_i} \{ f(e|S_i) \}\)) used by the traditional greedy algorithm. Thus, under this circumstance, Algorithm 1 and Algorithm 2 produce same solution, which is the optimum solution of the optimization problem according to the results of Conforti and Cornuéjols [2].
The following assumption is crucial in the analysis of the performance guarantee of Algorithm 2. Note that given an arbitrary set function f, one can verify that whether f satisfies Assumption 1 in linear time.
Assumption 1
Set function \(f :2^\Omega \rightarrow {\mathbb {R}}_{+}\) satisfies the following property:
Let \(\tau := \max _{e \in \Omega } f(e | \Omega - e)\). For every \(i = 1,2,\ldots ,k-2\), there exist at least \(i+1\) elements \(e' \in \Omega \), such that \(f(e' | \Omega - e') \ge \tau \cdot \left[ 1 - \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \right] \).
Now, we begin to analyze the performance guarantee of Algorithm 2. Firstly, we consider the marginal gain of the distorted objective function \(\Phi _i\) in each iteration.
Lemma 3
In each iteration (\(i=0,1,\ldots ,k-1\)) of Algorithm 2, it holds that
Proof
By the definition of \(\Phi _i\) and \(\Psi _i\), we have
Since \(e_i \in \Omega \setminus S_i\), it follows that
Then, we obtain
which concludes the proof. \(\square \)
Then, we bound \(\Psi _i(S_i, e_i)\) from below in terms of f(OPT). Before that, we will need the following lemma.
Lemma 4
If function f obeys Assumption 1, then in each iteration (\(i = 0, 1, \ldots , k-1\)) of Algorithm 2, it holds that
Proof
It’s obvious that \(\max \{ \Psi _i(S_i, e) : e \in \Omega \} \ge \max \{ \Psi _i(S_i, e) : e \in \Omega \setminus S_i \}\) holds for every \(i = 0, 1, \ldots , k-1\).
When \(i=0\), since \(S_0 = \varnothing \), we have \(\max \{ \Psi _0(S_0,e) : e \in \Omega \} = \max \{ \Psi _i(S_0,e) : e \in \Omega \setminus S_0 \}\). When \(i = k-1\), since \(\Psi _{k-1}(S_{k-1},e) = f(e | S_{k-1})\), it also holds that \(\max \{ \Psi _{k-1}(S_{k-1},e) : e \in \Omega \} = \max \{ \Psi _{k-1}(S_{k-1},e) : e \in \Omega \setminus S_{k-1} \}\). Thus, we only need to consider the case of \(i = 1,2,\ldots ,k-2\).
Suppose that there exists a \(i_0 \in \{ 1,2,\ldots ,k-2 \}\) such that \(\max \{ \Psi _{i_0}(S_{i_0},e) : e \in \Omega \} > \max \{ \Psi _{i_0}(S_{i_0}, e) : e \in \Omega \setminus S_{i_0} \}\). It implies that there must be an element \(e^\star \in S_{i_0}\), such that \(\Psi _{i_0}(S_{i_0}, e^\star ) > \Psi _{i_0}(S_{i_0}, e)\) for every \(e \in \Omega \setminus S_{i_0}\). Let \(\tau := \max \{ f(e | \Omega - e) : e \in \Omega \}\). By the definition of \(\Psi _i(e,T)\), for every \(e \in \Omega \setminus S_{i_0}\), it holds that
Thus, there exist at most \(i_0\) elements \(e' \in \Omega \) such that \(f(e' | \Omega - e') \ge \tau \cdot \left[ 1 - \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \right] \), which contradicts Assumption 1. The proof is completed. \(\square \)
Now, we give a lower bound of \(\Psi _i(S_i, e_i)\).
Lemma 5
If submodular function f satisfies Assumption 1, then in each iteration (\(i=0,1,\ldots ,k-1\)) of Algorithm 2, it holds that
where \(\kappa _f\) is the curvature of submodular function f and \(OPT \in \mathrm {argmax}\{ f(A) : |A| \le k, A \subseteq \Omega \}\).
Proof
We have
where the second equality follows by Lemma 4, the first inequality follows by \(|OPT| \le k\) and the restricted feasible set, and the second inequality follows by averaging the argument.
We define a new set function \(g :2^\Omega \rightarrow \mathbb {R}, A \mapsto f(A)-c(A)\). According to Lemma 2, g is a non-negative, monotone non-decreasing, submodular function. Thus, it holds that
where the first inequality follows by the submodularity of function g, and the second inequality follows by the monotonicity of function g.
Meanwhile, by Lemma 1, we have
Now, by combining the lower bounds of \(\Psi _i(S_i, e_i)\), \(\sum _{e \in OPT} \left[ f(e|S_i) - f(e|\Omega -e) \right] \) and \(\sum _{e \in OPT} f(e|\Omega -e)\), we can get
where the last inequality holds due to \(\kappa _f \in [0,1]\). \(\square \)
With Lemma 3 and Lemma 5 in hand, we can obtain the approximation ratio of Algorithm 2.
Theorem 2
If function f satisfies Assumption 1, then when Algorithm 2 terminates, it returns a feasible set \(S_k\) with
where \(\kappa _f\) is the curvature of submodular function f and \(OPT \in \mathrm {argmax}\{ f(A) : |A| \le k, A \subseteq \Omega \}\). And, during the iteration, the total value oracle queries are O(kn).
Proof
Using the telescoping technique, we have
where the second equality follows by Lemma 3, and the inequality follows by Lemma 5.
By the definition of \(\Phi _i\), we get
and
Thus, it holds that
As for the number of value oracle queries, we notice that in order to choose a proper element \(e_i\), O(n) value oracle queries are needed in the i-th iteration. Thus, during the k iterations, Algorithm 2 requires O(kn) value oracle queries. \(\square \)
Due to technical difficulties, we cannot prove Theorem 2 when f is an arbitrary monotone submodular function. Meanwhile, we are also unable to design any examples on which the approximation ratio of Algorithm 2 is non-constant. It may require new ideas to prove that Algorithm 2 can achieve the approximation ratio of \(1 - \kappa _f (1 - \frac{1}{k})^k\) for the general case.
4 Instances
In this section, we present a family of instances of Problem (1) where Algorithm 2 outperforms Algorithm 1. A family of worst-case examples have been shown by Conforti and Cornuéjol [2], where the traditional greedy algorithm (i.e., Algorithm 1) can only produce a \( \frac{1}{\kappa _f} \left[ 1 - (1 - \frac{\kappa _f}{k})^k \right] \) approximate solution.
Next, We describe the worst-case examples in detail. Let \(\Omega \) be the ground set \(\{ u_1,u_2,\ldots ,u_{k-1},v_1,v_2,\ldots ,v_k \}\). Suppose \(\alpha \) is an arbitrary real number in the interval (0, 1), we define \(\rho _i := \frac{1}{k} (1 - \frac{\alpha }{k})^{i-1}\) for every \(i = 1,2,\ldots ,k-1\). Then, we consider a set function \(f :2^\Omega \rightarrow {\mathbb {R}}_{+}\) which is defined as
for every subset \(\{ u_{i_1},\ldots ,u_{i_r},v_{j_1},\ldots ,v_{j_s} \}\) of \(\Omega \). Conforti and Cornuéjol [2] proved that f is a normalized (i.e., \(f(\varnothing ) = 0\)), monotone non-decreasing, submodular function with curvature \(\alpha \in (0,1)\). Now, we consider the problem of maximizing f subject to a cardinality constraint, i.e.,
Conforti and Cornuéjol [2] also proved that the solution produced by Algorithm 1 can be \(\{ u_1,u_2,\ldots ,u_{k-1},v_1 \}\), while the optimal solution of this particular problem is \(\{ v_1,v_2,\ldots ,v_k \}\). Since \(f( \{ u_1,u_2,\ldots ,u_{k-1},v_1 \} ) = \frac{1}{\alpha } \left[ 1 - (1 - \frac{\alpha }{k})^k \right] \) and \(f( \{ v_1,v_2,\ldots ,v_k \} ) = 1\), Algorithm 1 outputs a \( \frac{1}{\kappa _f} \left[ 1 - (1 - \frac{\kappa _f}{k})^k \right] \) approximate solution.
We notice that \(f(u_i | \Omega - u_i) = \frac{1 - \alpha }{k} ( 1 - \frac{\alpha }{k} )^{i-1}\) for every \(i = 1,2,\ldots ,k-1\) and \(f(v_j | \Omega - v_j) = \frac{1}{k} ( 1 - \frac{\alpha }{k} )^{k-1}\) for every \(j = 1,2,\ldots ,k\). Since \(1 - \alpha < ( 1 - \frac{\alpha }{k} )^{k-1}\) holds for any \(\alpha \in (0,1)\) and every \(k = 3,4,\ldots \), we have
which implies that f satisfies Assumption 1. Thus, according to Theorem 2, Algorithm 2 can produce a \( 1 - \kappa _f ( 1 - \frac{1}{k} )^k \) approximate solution for this particular problem. Since \( 1 - \kappa _f ( 1 - \frac{1}{k} )^k > \frac{1}{\kappa _f} \left[ 1 - (1 - \frac{\kappa _f}{k})^k \right] \) holds for any \(\kappa _f \in (0,1)\) (see Claim 1), Algorithm 2 indeed outperforms Algorithm 1 on this particular example.
Claim 1
For every \(\alpha \in (0,1)\) and every \(k = 3, 4,\ldots \), it holds that \(1 - \alpha (1 - \frac{1}{k})^k > \frac{1}{\alpha }\left[ 1 - (1 - \frac{\alpha }{k})^k \right] \).
Proof
We define \(g_k(\alpha ) := \alpha - \alpha ^2 (1 - \frac{1}{k})^k - 1 + (1 - \frac{\alpha }{k})^k\). Then, the inequality we want to prove is equivalent to \(g_k(\alpha ) > 0\). It follows that
Since \(g'''_k(\alpha ) < 0\), \(g''_k(\alpha )\) is strictly decreasing in the interval (0,1) for every \(k \ge 3\).
Meanwhile, we have \(g''_k(0) = (1 - \frac{1}{k}) \left[ 1 - 2 (1 - \frac{1}{k})^{k-1} \right] \) and \(g''_k(1) = \frac{2-k}{k} (1 - \frac{1}{k})^{k-1} < 0\). Let \(F(x) := (x-1) \ln (1 - \frac{1}{x})\) for every \(x \in [3, +\infty )\). Because \(F'(x) = \ln (1 - \frac{1}{x}) + \frac{1}{x} < 0\), it holds that \((1 - \frac{1}{k})^{k-1} \le \frac{4}{9}\) for every \(k \ge 3\), which implies \(g''_k(0) > 0\). Thus, for every \(k \ge 3\), there exists a unique \(\alpha _k^\star \in (0,1)\) such that \(g''_k( \alpha _k^\star ) = 0\), i.e., \((1 - \frac{ \alpha _k^\star }{k})^{k-2} = 2 (1 - \frac{1}{k})^{k-1}\). Moreover, we have that given a \(k \ge 3\), \(g'_k(\alpha )\) is strictly increasing in the interval \(( 0, \alpha _k^\star )\) and strictly decreasing in the interval \(( \alpha _k^\star , 1 )\).
Next, we consider the monotonicity of \(g_k(\alpha )\). We have \(g'_k(0) = 0\) and \(g'_k(1) = 1 - ( 3 - \frac{2}{k} )( 1 - \frac{1}{k} )^{k-1}\). Let \(G(x) := (3 - \frac{2}{x}) (1 - \frac{1}{x})^{x-1}\) for every \(x \in [3, +\infty )\). Then, \(G'(x) = (1 - \frac{1}{x})^{x-1} \left[ \frac{3}{x} + ( 3 - \frac{2}{x} ) \ln ( 1 - \frac{1}{x} ) \right] \). Let \(H(x) := \frac{3}{x} + ( 3 - \frac{2}{x} ) \ln ( 1 - \frac{1}{x} )\) for every \(x \in [3, +\infty )\). We have \(H'(x) = \frac{1}{x^2} \left[ 2\ln (1 - \frac{1}{x}) + \frac{1}{x-1} \right] \). Again, let \(L(x) := 2\ln (1 - \frac{1}{x}) + \frac{1}{x-1}\) for every \(x \in [3, +\infty )\). Then, it holds that \(L'(x) = \frac{x-2}{x(x-1)^2} > 0\) for every \(x \in [3, +\infty )\), which indicates that L(x) is strictly increasing in the interval \([3, +\infty )\). Thus, \(L(x) < 0\) holds for every \(x \in [3, +\infty )\) due to \(\lim _{x \rightarrow +\infty } L(x) = 0\). Since \(H'(x) = \frac{1}{x^2} L(x)\), H(x) is strictly decreasing in the interval \([3, +\infty )\). The fact that \(\lim _{x \rightarrow +\infty } H(x) = 0\) implies that \(H(x) > 0\) holds for every \(x \in [3, +\infty )\). It follows that \(G'(x) = (1 - \frac{1}{x})^{x-1} H(x) > 0\) for every \(x \in [3, +\infty )\), which indicates that \(g'_k(1) = 1 - G(k) \le 1 - G(3) = - \frac{1}{27} < 0\). Thus, we have \(\min _{\alpha \in [0,1]} g_k(\alpha ) = \min \{ g_k(0), g_k(1) \} = 0\). It follows that \(g_k(\alpha ) > 0\) for every \(\alpha \in (0,1)\).
As a result, \(1 - \alpha (1 - \frac{1}{k})^k > \frac{1}{\alpha }\left[ 1 - (1 - \frac{\alpha }{k})^k \right] \) holds for every \(\alpha \in (0,1)\) and every \(k \ge 3\). \(\square \)
5 Implementation in practice
Though we can only prove that Algorithm 2 achieves a better approximation ratio than Algorithm 1 when the objective functions satisfy Assumption 1. In practice, we can combine the greedy strategies adopted by Algorithm 1 and Algorithm 2 together to obtain a hybrid greedy algorithm, which is presented as Algorithm 3.
It’s obvious that Algorithm 3 can return a solution at least as good as the solution produced by Algorithm 1. Moreover, as is shown in Sect. 4, we can expect that Algorithm 3 will outperform Algorithm 1 in some cases.
6 Conclusion
In this paper, we have proposed a deterministic algorithm for solving the submodular maximization problem subject to a cardinality constraint. We have showed that our algorithm is quite efficient and achieves the tight approximation ratio when the objective functions satisfy a particular property. Although we are unable to prove that the same approximation ratio can be achieved by our algorithm when the objective function is an arbitrary monotone submodular function, we have showed that our algorithm outperforms the traditional greedy algorithm on certain instances. In practice, due to the simplicity of our algorithm, it can be incorporated into the traditional greedy algorithm. The resulting algorithm will have better performance than the traditional greedy algorithm in some cases. Moreover, it will be an interesting topic for the future research to design an algorithm which achieves the tight approximation ratio and only requires O(kn) value oracle queries.
Notes
Note that \( 1 - \kappa _f e^{-1} > \frac{1}{\kappa _f} (1 - e^{-\kappa _f} )\) holds for any \(\kappa _f \in (0,1)\).
We will explain this assumption in section 3.
To see this, one should refer to Lemma 3, which explains the relation between \(\Psi _i\) and the marginal gain of the distorted objective function \(\Phi _i\).
References
Ageev, A., Hassin, R., Sviridenko, M.: A 0.5-approximation algorithm for max dicut with given sizes of parts. SIAM J. Discret. Math. 14(2), 246–255 (2001)
Conforti, M., Cornuéjols, G.: Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the rado-edmonds theorem. Discret. Appl. Math. 7(3), 251–274 (1984)
Feige, Uriel: A threshold of ln n for approximating set cover. J. ACM (JACM) 45(4), 634–652 (1998)
Feldman, M.: Guess free maximization of submodular and linear sums. Algorithmica 83(3), 853–878 (2021)
Frieze, A., Jerrum, M.: Improved approximation algorithms for maxk-cut and max bisection. Algorithmica 18(1), 67–81 (1997)
Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169–197 (1981)
Harshaw, C., Feldman, M., Ward, J., Karbasi, A.: Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In International Conference on Machine Learning, pages 2634–2643. PMLR, 2019
Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM (JACM) 48(4), 761–777 (2001)
Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137–146, 2003
Khuller, S., Moss, A., Naor, J.S.: The budgeted maximum coverage problem. Information Process. lett. 70(1), 39–45 (1999)
Krause, A., Guestrin, C.: Near-optimal observation selection using submodular functions. In AAAI 7, 1650–1654 (2007)
Krause, A. , Guestrin, C. E.: Near-optimal nonmyopic value of information in graphical models. arXiv preprint arXiv:1207.1394, 2012
Krause, A., Singh, A., Guestrin, C.: Near-optimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235–284 (2008)
Lin, H., Bilmes, J.: Multi-document summarization via budgeted maximization of submodular functions. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 912–920, 2010
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-i. Math. Progr. 14(1), 265–294 (1978)
Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theory Series B 80(2), 346–355 (2000)
Sviridenko, M., Vondrák, J., Ward, J.: Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42(4), 1197–1218 (2017)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This research was supported by the National Natural Science Foundation of China under Grant Numbers 11991022 and 12071459 and the Fundamental Research Funds for the Central Universities under grant number E1E40107.
Rights and permissions
About this article
Cite this article
Lu, C., Yang, W. & Gao, S. A new greedy strategy for maximizing monotone submodular function under a cardinality constraint. J Glob Optim 83, 235–247 (2022). https://doi.org/10.1007/s10898-021-01103-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-021-01103-1