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 :

$$\begin{aligned} \begin{aligned} \max _{A \subseteq \Omega } \quad&f(A) \\ {\mathrm {s.t.}} \quad&|A| \le k , \end{aligned} \end{aligned}$$
(1)

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

$$\begin{aligned} \begin{aligned} \max _{A \subseteq \Omega } \quad&g(A) - c(A) \\ {\mathrm {s.t.}} \quad&|A| \le k , \end{aligned} \end{aligned}$$

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,

$$\begin{aligned} \begin{aligned} \max _{A \subseteq \Omega } \quad&f(A) \\ {\mathrm {s.t.}} \quad&|A| \le k , \end{aligned} \end{aligned}$$

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

$$\begin{aligned} f(S) \ge \left[ 1 - \kappa _f \left( 1 - \frac{1}{k} \right) ^k \right] f(OPT), \end{aligned}$$

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

$$\begin{aligned} \kappa _f := 1 - \min _{e \in \Omega } \frac{ f(e|\Omega - e) }{ f(e|\varnothing ) }. \end{aligned}$$

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. 1)

    g is a submodular function;

  2. 2)

    g is monotone non-decreasing;

  3. 3)

    g is non-negative.

Proof

  1. 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. 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. 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

$$\begin{aligned} \Phi _i(T) := \left( 1- \frac{1}{k} \right) ^{k-i} f(T) + \left[ 1- \left( 1- \frac{1}{k} \right) ^{k-i} \right] c(T). \end{aligned}$$

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

$$\begin{aligned} \Psi _i(T,e) := \left( 1- \frac{1}{k} \right) ^{k-(i+1)} f(e|T) + \left[ 1- \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \right] f(e|\Omega -e). \end{aligned}$$

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.

figure a
figure b

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

$$\begin{aligned} \Phi _{i+1}(S_{i+1}) - \Phi _i(S_i) = \Psi _i(S_i, e_i) + \frac{1}{k} \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \left[ f(S_i) - c(S_i) \right] . \end{aligned}$$

Proof

By the definition of \(\Phi _i\) and \(\Psi _i\), we have

$$\begin{aligned}&\Phi _{i+1}(S_{i+1}) - \Phi _i(S_i) \\ ={}&\left\{ \left( 1- \frac{1}{k} \right) ^{k-(i+1)} f(S_{i+1}) + \left[ 1- \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \right] c(S_{i+1}) \right\} \\&\quad - \left\{ \left( 1- \frac{1}{k} \right) ^{k-i} f(S_{i}) + \left[ 1- \left( 1- \frac{1}{k} \right) ^{k-i} \right] c(S_{i}) \right\} \\ ={}&\left( 1- \frac{1}{k} \right) ^{k-(i+1)} f(e_i | S_i) + \left[ 1 - \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \right] \cdot [c(S_{i+1}) - c(S_i)] \\&\quad + \frac{1}{k} \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \left[ f(S_i) - c(S_i) \right] . \end{aligned}$$

Since \(e_i \in \Omega \setminus S_i\), it follows that

$$\begin{aligned} c(S_{i+1}) - c(S_i) = c(S_i + e_i) - c(S_i) = c_{e_i} = f(e_i | \Omega - e_i). \end{aligned}$$

Then, we obtain

$$\begin{aligned}&\Phi _{i+1}(S_{i+1}) - \Phi _i(S_i) \\ ={}&\left( 1- \frac{1}{k} \right) ^{k-(i+1)} f(e_i | S_i) + \left[ 1 - \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \right] f(e_i | \Omega - e_i) \\&\quad + \frac{1}{k} \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \left[ f(S_i) - c(S_i) \right] \\ ={}&\Psi _i(S_i, e_i) + \frac{1}{k} \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \left[ f(S_i) - c(S_i) \right] , \end{aligned}$$

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

$$\begin{aligned} \max \{ \Psi _i(S_i, e) : e \in \Omega \} = \max \{ \Psi _i(S_i, e) : e \in \Omega \setminus S_i \}. \end{aligned}$$

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

$$\begin{aligned} f(e|\Omega -e) \le \Psi _{i_0}(e,S_{i_0}) < \Psi _{i_0}(e^\star ,S_{i_0}) \le \tau \cdot \left[ 1 - \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \right] . \end{aligned}$$

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

$$\begin{aligned} \Psi _i(S_i, e_i) \ge&\frac{1}{k} \left[ 1 - \kappa _f + \kappa _f \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \right] f(OPT) - \frac{1}{k} \left[ 1 - \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \right] f(\varnothing ) \\&- \frac{1}{k} \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \left[ f(S_i) - c(S_i) \right] , \end{aligned}$$

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

$$\begin{aligned}&k \cdot \Psi _i(S_i, e_i) \\&\quad ={} k \cdot \max _{e \in \Omega \setminus S_i} \{ \Psi _i(S_i, e) \} \\&\quad ={} k \cdot \max _{e \in \Omega } \{ \Psi _i(S_i, e) \} \\&\quad ={} k\cdot \max _{e\in \Omega } \left\{ \left( 1- \frac{1}{k} \right) ^{k-(i+1)} f(e|S_i) + \left[ 1- \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \right] f(e|\Omega -e) \right\} \\&\quad \ge {} |OPT| \cdot \max _{e\in OPT} \left\{ \left( 1- \frac{1}{k} \right) ^{k-(i+1)} f(e|S_i) + \left[ 1- \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \right] f(e|\Omega -e) \right\} \\&\quad \ge {} \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \sum _{e \in OPT} \left[ f(e|S_i) - f(e|\Omega -e) \right] + \sum _{e \in OPT} f(e|\Omega -e), \end{aligned}$$

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

$$\begin{aligned} \sum _{e \in OPT} \left[ f(e|S_i) - f(e|\Omega -e) \right]&= \sum _{e \in OPT} g(e|S_i) \\&\ge g(OPT \cup S_i) - g(S_i) \\&\ge g(OPT) - g(S_i) \\&= f(OPT) - [f(S_i) - c(S_i)] - \sum _{e \in OPT} f(e|\Omega -e), \end{aligned}$$

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

$$\begin{aligned} \sum _{e \in OPT} f(e|\Omega -e) \ge (1-\kappa _f) \left[ f(OPT) - f(\varnothing ) \right] . \end{aligned}$$

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

$$\begin{aligned}&\Psi _i(S_i, e_i) \\&\quad \ge {} \frac{1}{k} \left[ 1 - \kappa _f + \kappa _f \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \right] f(OPT) - \frac{1}{k} \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \left[ f(S_i) - c(S_i) \right] \\&\quad \quad - \frac{1-\kappa _f}{k} \left[ 1 - \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \right] f(\varnothing ) \\&\quad \ge {} \frac{1}{k} \left[ 1 - \kappa _f + \kappa _f \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \right] f(OPT) - \frac{1}{k} \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \left[ f(S_i) - c(S_i) \right] \\&\quad \quad - \frac{1}{k} \left[ 1 - \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \right] f(\varnothing ), \end{aligned}$$

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

$$\begin{aligned} f(S_k) \ge \left[ 1 - \kappa _f \left( 1 - \frac{1}{k} \right) ^k \right] f(OPT), \end{aligned}$$

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

$$\begin{aligned} \Phi _k(S_k) - \Phi _0(S_0)&= \sum _{i=0}^{k-1} \left[ \Phi _{i+1}(S_{i+1}) - \Phi _i(S_i) \right] \\&= \sum _{i=0}^{k-1} \left\{ \Psi _i(S_i,e_i) + \frac{1}{k} \left( 1- \frac{1}{k} \right) ^{k-(i+1)} \left[ f(S_i) - c(S_i) \right] \right\} \\&\ge \left[ 1 - \kappa _f \left( 1 - \frac{1}{k} \right) ^k \right] f(OPT) - \left( 1 - \frac{1}{k} \right) ^k f(\varnothing ), \end{aligned}$$

where the second equality follows by Lemma 3, and the inequality follows by Lemma 5.

By the definition of \(\Phi _i\), we get

$$\begin{aligned} \Phi _k(S_k) = f(S_k) , \end{aligned}$$

and

$$\begin{aligned} \Phi _0(S_0) = \left( 1 - \frac{1}{k} \right) ^k f(\varnothing ) + \left[ 1 - \left( 1 - \frac{1}{k} \right) ^k \right] c(\varnothing ) = \left( 1 - \frac{1}{k} \right) ^k f(\varnothing ) . \end{aligned}$$

Thus, it holds that

$$\begin{aligned} f(S_k)&= \left[ \Phi _k(S_k) - \Phi _0(S_0) \right] + \Phi _0(S_0) \\&\ge \left[ 1 - \kappa _f \left( 1 - \frac{1}{k} \right) ^k \right] f(OPT). \end{aligned}$$

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

$$\begin{aligned} f( \{ u_{i_1},\ldots ,u_{i_r},v_{j_1},\ldots ,v_{j_s} \} ) := \left( 1 - \alpha \frac{s}{k} \right) \sum _{t=1}^{r} \rho _{i_t} + \frac{s}{k} , \end{aligned}$$

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.,

$$\begin{aligned} \begin{aligned} \max _{A \subseteq \Omega } \quad&f(A) \\ {\mathrm {s.t.}} \quad&|A| \le k. \end{aligned} \end{aligned}$$

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

$$\begin{aligned} \mathrm {argmax}\{ f(e | \Omega - e) : e \in \Omega \} = \{ v_1,v_2,\ldots ,v_k \}, \end{aligned}$$

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

$$\begin{aligned}&g'_k(\alpha ) = 1 - 2\alpha \left( 1 - \frac{1}{k} \right) ^k - \left( 1 - \frac{\alpha }{k} \right) ^{k-1} \\&\quad \Longrightarrow {} g''_k(\alpha ) = -2 \left( 1 - \frac{1}{k} \right) ^k + \frac{k-1}{k} \left( 1 - \frac{\alpha }{k} \right) ^{k-2} \\&\quad \Longrightarrow {} g'''_k(\alpha ) = -\frac{(k-1)(k-2)}{k^2} \left( 1 - \frac{\alpha }{k} \right) ^{k-3}. \end{aligned}$$

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.

figure c

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.