Diverse Approximations for Monotone Submodular Maximization Problems with a Matroid Constraint

1 Introduction

Optimization research has seen rising interest in diverse solutions problems, where multiple maximally distinct solutions of high quality are sought instead of a single solution [Ingmar et al., 2020; Baste et al., 2022; Hanaka et al., 2021; Fomin et al., 2021; Fomin et al., 2020; Hanaka et al., 2022b; Hanaka et al., 2022a]. This class of problem is motivated by practical issues largely overlooked in traditional optimization. Having diverse solutions gives resilient backups in response to changes in the problems rendering the current solution undesirable. It also gives the users the flexibility to correct for gaps between the problem models and real-world settings, typically caused by estimation errors, or aspects of the problem that cannot be formulated precisely [Schittekat and S¨orensen, 2009]. Furthermore, diverse solution sets contain rich information about the problem instance by virtue of being diverse, which helps augment decision making capabilities. While there are methods to enumerate high quality solutions, having too many overwhelms the decision makers [Glover et al., 2000], and a small, diverse subset can be more useful. It is also known that k-best enumeration tends to yield highly similar solutions, motivating the use of diversification mechanisms [Wang et al., 2013; Yuan et al., 2015; Hao et al., 2020].

The diverse solutions problem have been studied as an extension to many important and difficult problems. Some examples of fundamental problems include constraint satisfaction and optimization problems [Hebrard et al., 2005; Petit and Trapp, 2015; Ruffini et al., 2019], SAT and answer set problem [Nadel, 2011; Eiter et al., 2009], and mixed integer programming paradigms [Glover et al., 2000; Danna et al., 2007; Trapp and Konrad, 2015]. More recently, the first provably fixed-parameter tractable algorithms have been proposed for diverse solutions to a number of graphbased vertex problems [Baste et al., 2022], as motivated by the complexity of finding multiple high performing solutions. This inspired subsequent research on other combinatorial structures such as trees, paths [Hanaka et al., 2021; Hanaka et al., 2022b], matching [Fomin et al., 2020], independent sets [Fomin et al., 2021], and linear orders [Arrighi et al., 2021]. Furthermore, general frameworks have been proposed for diverse solutions to any combinatorial problem [Ingmar et al., 2020; Hanaka et al., 2022a]. To address the need to obtain both quality and diversity, multicriteria optimization has been considered, leading to interesting results [Gao et al., 2022]. These are mostly applied to problems with linear objective functions and specific matroid intersection constraints.

In this work, we are interested in diverse solutions problem in the domain of submodular optimization, which has been enjoying widespread interests. It captures the diminishing returns property that arises in many real-world problems in machine learning, signal processing [Tohidi et al., 2020], sensor placement [Krause and Guestrin, 2005], data summarization [Lin and Bilmes, 2011; Mirzasoleiman et al., 2013], influence maximization [Kempe et al., 2015], to name a few. Moreover, its hardness (as it generalizes many fundamental NP-hard combinatorial problems) and well-structuredness (which facilitates meaningful results [Vondr´ak, 2013]) mean the problem class also sees much attention from theoretical perspectives, leading to interesting insights [Nemhauser et al., 1978; Fisher et al., 1978; Calinescu et al., 2011; Krause and Golovin, 2014; Chekuri et al., 2014]. It is important to distinguish between the diverse solutions extension to submodular optimization and results diversification [Zheng et al., 2017], the latter of which considers diversity as a measure of a solution (i.e. a selection of results) and optimizes it along with a submodular utility function.

Our Contributions We investigate the problem of finding a given number of diverse solutions to maximizing a monotone submodular function over a matroid, with a lower bound on solutions' objective values. Matroids are a type of independence system that can be used to model constraints in many important problems, and have been studied in in submodular optimization literature [Conforti and Cornu´ejols, 1984; Lee et al., 2010; Calinescu et al., 2011; Kashaev and Santiago, 2023; Chekuri et al., 2014], even recently appeared in diverse solutions research [Fomin et al., 2021]. Among them, uniform matroids which characterize cardinality constraints, and their extension, partition matroids, are often considered in budgeted optimization (e.g. [Lin and Bilmes, 2010]). We consider the distance-sum measure of diversity, which is often chosen for diverse solutions problems [Hanaka et al., 2021; Baste et al., 2022; Hanaka et al., 2022b; Hanaka et al., 2022a; Gao et al., 2022]. Its sole reliance on the ground set elements' representation in the solution set implies generalizability to other diversity measures such as entropy. Our contributions are as follows:

• We propose two simple greedy algorithms which are suitable to deal with the objective requirement, as greedy algorithms are known to perform well on monotone submodular maximization [Nemhauser et al., 1978; Fisher et al., 1978]. The novelty lies in the additional parameters, which adjust the trade-off between guarantees on objective values and diversity. We position our algorithms as simpler, zeroth-order (in terms of objective and independence oracles) alternatives to general frameworks for diverse solutions in recent literature, which have not been analyzed in submodular optimization context.
• We provide analyses of these algorithms in terms of their objective-diversity guarantees trade-offs. Our results are formulated as functions of their respective parameters, thus giving a general guidance on parameter selection. We also give sharpened bounds for cases with uniform matroids, as motivated by the prevalence of cardinality constraints. From these results, we point out settings that guarantee constant approximation ratios in objective, diversity, or both. Our tightness constructions also indicate certain features of matroids that make them pathological to these algorithms.
• We carry out an experimental investigation with maximum vertex coverage instances subjected to uniform and partition matroid constraints, to observe the algorithms' empirical performances in exhaustive parameter settings. The results indicate that while both algorithms produce nearly optimal solutions with reasonable diversity in many parameter settings, the simpler of the two actually provides better objective-diversity trade-offs across all problem settings. Additionally, these establish an empirical baseline for the diverse solutions problem considered in this work.

2 Preliminaries

In this section, we present the problem and relevant definitions, and give some observations that are helpful in our analyses.

2.1 Problem and Definitions

A multiset is a collection that can contain duplicates (e.g. {1, 1, 2}). For a set A, we denote the collection of multisets of elements in A with A∗ , and Ar ⊆ A∗ contains r-size 1 multisets for some integer r. The problem we investigate is as follows: given integer r ≥ 2, α ∈ [0, 1], a (f, S, d, r, α)- instance asks for a multiset 2 of solutions in

where the objective function, f : 2V → R is non-negative 3 and non-decreasing submodular, S = I for some matroid M = (V, I), and d is a diversity measuring function defined over (2V )∗ . We do not consider non-increasing f due to trivial instances where achieving any positive diversity 4 necessitates degrading solutions beyond the feasibility limit. As per standard practice, we use "monotone" to mean "nondecreasing" in this paper. We call a multiset P feasible to the (f, S, d, r, α)-instance if P ∈ Sr and every solution in P is a α-approximation of f over S, which is a solution x ∈ S such that f(x) ≥ αmaxy∈S f(y). We also briefly give relevant definitions and assumptions.

Definition 1 Function f : 2V → R is monotone if f(x) ≤ f(y) for all x ⊆ y ⊆ V .

Definition 2 Function f : 2V → R is submodular if ∀x, y ⊆ V, f (x) + f (y) ≥ f (x ∪ y) + f (x ∩ y) or equivalently ∀x ⊆ y ⊆ V, v ∈ V \ y, f(x ∪ {v}) - f(x) ≥ f(y ∪ {v}) - f(y).

For problem (1), we assume w.l.o.g. that f(∅) = 0, since a multiset feasible to a (f, S, d, r, α)-instance is also feasible to the (f +f ′ , S, d, r, α)-instance for some constant non-negative function f ′ . We assume for our problem that f is given as a value oracle.

For matroid theory concepts, we adopt terminologies from the well-known text book [Oxley, 2011] on the subject.

Definition 3 A tuple M = (V, I ⊆ 2V ) is a matroid if a) ∅ ∈ I, b) ∀x ⊆ y ⊆ V, y ∈ I =⇒ x ∈ I, c) ∀x, y ∈ I, |x| < |y| =⇒ ∃e ∈ y \ x, x ∪ {e} ∈ I. The set V is the ground set, and I is the independence collection. A base of M is a maximal set in I.

Definition 4 Given a matroid M = (V, I),

• the rank function of M, rM : 2V → N, is defined as rM(x) = max{|y| : y ∈ 2x ∩ I}, and the rank of M is rM = rM(V ),
• the closure function of M, clM : 2V → 2V , is defined as clM(x) = {v ∈ V : rM(x ∪ {v}) = rM(x)},
• a loop of M is a v ∈ V such that {v} /∈ I.

1 In this work, we use "r-size" to mean "containing r elements".

2 Satisfying self-avoiding constraint requires algorithmic treatment

beyond this work's scope.

3 The non-negativity assumption is widely used in literature to ensure proper contexts for multiplicative approximation guarantees, which this work includes. This also applies to diversity w.l.o.g.

4 Assuming the diversity measure returns 0 on duplicate-only multisets.

To give examples, a K-rank uniform matroid over V admits the independence collection I = {x ⊂ V : |x| ≤ K} which we denote with UV,K. A partition matroid admits the independence collection I = {x ⊂ V : ∀i = 1, . . . , k, |x∩Bi| ≤ di} for some partitioning {Bi}ki=1 of V and their corresponding thresholds {di}ki=1 . In graph theory, a graphic matroid M = (E, I) defined over a undirected graph G = (V, E) is such that I contains all edge sets x where G′ = (V, x) has no cycle. A base of a graphic matroid is a spanning forest in the underlying graph, which itself is an object of much interest. Dual to the graphic matroid, the bond matroid M ∗ = (E, I ∗ ) is such that I ∗ contains all edge sets x where G∗ = (V, E \ x) has the same number of connected components as G.

For the problem (1), we assume that M is loop-free and |V | ≥ 1, implying rM > 0. It is known that rank functions are monotone submodular, and closure functions are monotone, i.e. x ⊆ y =⇒ clM(x) ⊆ clM(y) [Oxley, 2011]. We also assume that for a matroid, we are given an independence oracle answering whether a set is independent.

Finally, we consider the distance-sum diversity function, which is the usual choice in literature on diverse solutions problems [Hanaka et al., 2021; Baste et al., 2022; Hanaka et al., 2022b; Hanaka et al., 2022a; Gao et al., 2022]. The function is defined over multisets of solutions as ss(P) = ∑x,y∈P |x∆y| where ∆ is the symmetric difference between two sets, and its size is the Hamming distance. To be precise, each pairwise distance is counted once in an evaluation of ss.

Under this setting, the problem (1) is equivalent to the dispersion problem over the ground set that is the collection of all α-approximations of f over I. The dispersion problem is known to be NP-hard in the ground set's size, even with known ground sets and metric distance functions [Wang and Kuo, 1988; Erkut, 1990; Ravi et al., 1994; Chandra and Halld´orsson, 1996]; for our problem, the collection is neither known nor necessarily small. On the other hand, [Hanaka et al., 2022a] showed that this problem admits a polytime max{1 - 2/r, 1/2}-approximation scheme, predicated on a poly-time top-r enumeration scheme over this collection maximizing ss. We are not aware of such a scheme for αapproximations to submodular maximization over a matroid, and we recognize this as an interesting problem in its own right. That said, it is likely that algorithms resulted from this line of ideas will have significantly larger asymptotic run-times than those of the algorithms we present in this work.

2.2 Some Useful Properties

First, we observe that the value of ss is related to the occurrences of each elements of V in the multiset. Let P be a r-size multiset of subsets of V , and for i = 1, . . . , |V |, ni(P) = |{x ∈ P : i ∈ x}|, we have

This means the function can be decomposed into disjoint subsets of V : given a partitioning {Vi}ki=1 of V , we have ss(P) = ∑ki=1 ss({x ∩ Vi : x ∈ P}). This property can significantly simplify analyses.

We would also like to bound the maximum achievable diversity in various settings. While without the constraint on the values of f, this bound can be computed (over a matroid) exactly and efficiently, e.g. by using the method in [Hanaka et al., 2021], estimating it with a formula can be useful. To this end, we define a function g : N3 → N with

where h = min{b, a/2}, and m ∈ [0, a), q are integers such that ⌈c/2⌉⌈h⌉ + ⌊c/2⌋⌊h⌋ = qa +m. This function returns the maximum ss values of a c-size multisets of at most bsize subsets of a a-size ground set (Theorem 1). Also, we let g(0, ·, ·) = g(·, 0, ·) = g(·, ·, 1) = 0. For convenience, let δ : N2 → N be defined with δ(a, b) = a - 2b - 1, we have

This expression exposes the connection between g and the process of adding elements into solutions in P , which is relevant to the algorithms we consider in this work. That is, we can rewrite g using δ: g(a, b, c) = a ∑q-1 i=0 δ(c, i)+mδ(c, q); this simplifies the proof of its monotonicity (see Appendix). Here, we include an inequality which gives an intuitive bound of a result in Section 3.

Lemma 1 Given integers a, b, c ≥ 1 and k ≥ 0, g(⌈ka/b⌉, k, c) ≥ kg(a, b, c)/y.

To establish an upper bound on diversity, we use the following straightforward observation from the fact that uniform matroid constraints are the least restrictive.

Observation 1 Given a set V , function f over 2V , matroids M = (V, I) and M ′ = (V, I ′ ) where M is uniform and rM ≥ rM′ , then the optimal value for the (f, I ′ , d, r, 0)- instance cannot exceed that for the (f, I, d, r, 0)-instance with any r ≥ 1, and real function d over (2V )∗ .

With this, we can use uniform matroids to formulate a simple upper bound, which is also tight for some non-uniform matroids and, surprisingly, any value of the threshold ratio α.

Theorem 1 The optimal value for a (f, I, ss, r, α)-instance for some matroid M = (V, I), function f over 2V , integer r ≥ 1, and α ∈ [0, 1] is at most g(|V |, rM, r). Moreover, this bound is tight for any |V | ≥ 1, r ≥ 1, α ∈ [0, 1], and matroid rank rM ∈ [1, |V |], even if the matroid is non-uniform.

In augment-type algorithms like greedy, how the feasible selection pool for a partial solution (i.e. set of elements that can be added without violating constraints) changes over the course of the algorithm influences the guaranteed quality of the final output. This insight was made evident in seminal works on greedy algorithms [Fisher et al., 1978; Nemhauser et al., 1978], and is replicated in subsequent works on submodular optimization under more complex constraints. This is especially important in diverse solutions, as high diversity can be seen as additional restrictions on the selection pool. In the context of matroid constraint, this pool is determined by the partial solution's closure, thus we include an observation connecting closures to the upper bound on diversity.

Lemma 2 Let M = (V, I) be a matroid (may contain loops), and x ∈ I, then for all y ∈ I, |y ∩ clM(x)| ≤ |x|. By extension, |y ∩ z| ≤ rM(z) for all z ⊆ V .

Lemma 2 lets us sharpen the upper bound on ss values for highly non-uniform matroids.

Lemma 3 Given a matroid M = (V, I) (may contain loops) and integer r ≥ 1, then for any P ∈ I r ,

where nx = min{rM|clM(x)|/|V |, |x|}. There exists a matroid where equality holds.

3 Greedy Algorithms for Diverse Solutions

We describe two different greedy algorithms to obtain an approximation to the problem (1), by incrementally building solutions. They are greedy in the sense that they select, in each step, the "best" choice out of a selection pool. Here, choice refers to a solution-element pair where the element is added into the solution. The differences between the two algorithms lie in how this pool is defined, and the selection criteria. In both algorithms, the pool is controlled by a parameter, which determines a trade-off between objective values and diversity.

In the following, we claim several worst-case bounds, i.e. for all settings I (each including a problem instance and an algorithm parameter value) in a universe clear from the context, p(I) ≥ q(I) for some quantities p and q of the setting (e.g. optimal value, worst-case diversity, etc.) A bound is tight if there is a setting I ′ where p(I ′ ) = q(I ′ ). It is nearly tight if instead we have p(I ′ ) = q(I ′ ) + ϵ for an arbitrary small ϵ > 0 independent from other factors.

3.1 Diversifying GreedyWith Common Elements

The first approach, outlined in Algorithm 1, is a deterministic version of a heuristic for a special case of problem (1), proposed in [Neumann et al., 2021]. The idea is to first have all solutions share common elements selected by the classical greedy algorithm, so as to efficiently obtain some objective value guarantee. Then, in the second phase (starting from line 5), each solution is finalized with added elements that maximize ss, which are precisely those least represented. To be specific, in each iteration, the algorithm looks at all solutionelement pairs which maintain independence, and selects a pair based on criteria, the first of which maximizes diversity (line 7). This approach is simple and efficient, but prevents the common elements from contributing to diversity. Here, we formulate the algorithm to take the number of common elements as an input (b), which cannot exceed the rank of the matroid constraint.

We observe that since the image of ss is polynomially bounded in size, there are frequently many equivalent choices in each iteration in the second phase, motivating the use of tie-breaking rules, which are formulated as lexicographical argmin at Line 7. Of note is the second rule, which prioritizes solutions with the fewest remaining choices. The idea is to minimize the shrinkage of the pool among under-represented elements (the inclusion of which incurs large marginal gains in diversity) with a simple heuristic. We show that this tiebreaking rule helps guarantee a non-trivial lower bound of ss

Algorithm 1: Greedy with common elements

• Input: f, S, b, r // Assuming b ≤ maxz∈S |z| Output: P ∈ Sr 1 x ← ∅, κ(·) ← {u ∈ (V \ ·) : (· ∪ {u}) ∈ S}; 2 while |x| < b and κ(x) ̸= ∅ do 3 v ← argmaxu∈κ(x) f(x ∪ {u}), x ← x ∪ {v}; 4 P ← {x}r ; //P contains r duplicates of x 5 R ← {(z, v) : z ∈ P, v ∈ κ(z), f(z ∪ {v}) ≥ f (z) ∧ nv(P ) < ⌈r/2⌉}; 6 while R ̸= ∅ do // below argmin over vectors is done in left-to-right lexicographical order 7 (y, v) ← argmin(z,u)∈R(nu(P), |κ(z)| , f(z), f(z) - f (z ∪ {u})); 8 P ←P \ {y} ∪ {y ∪ {v}}; 9 Update R as in Line 5;

value under a general matroid, whereas it makes no difference under a uniform matroid. The other tie-breaking rules aim to improve the minimum objective value whenever possible.

The time complexity of Algorithm 1 is O(b|V | + r(rM - b)(|V | - b)) in both value oracle model and independence oracle model. The algorithm may not return r bases if rrM is sufficiently large relative to |V |. Additionally, having all solutions sharing elements can be undesirable in some applications. Note the condition nv(P) < ⌈r/2⌉ at line 5 ensures ss(P) never decreases during the second phase.

Let A(f, S, b, r) be the collection of possible outputs from Algorithm 1 when run with inputs f , S, b, r. We first show that in uniform constraint case, the algorithm returns a constant diversity for each input configuration.

Theorem 2 For any monotone submodular f over 2V , integers K ≥ 1, r ≥ 2, b ∈ [0,K), and let α = 1 - e-b/K , ∀P ∈ A(f, UV,K, b, r), ss(P) = g(|V | - b,K - b, r), thus Algorithm 1 is g(|V | - b, K - b, r)/g(|V |, K, r)-approximate for the (f, UV,K, ss, r, α)-instance. Moreover, this ratio bound is tight for any |V | ≥ 1, r ≥ 2, K ∈ [1, |V |], and b ∈ [0,K).

Due to the monotonicity of g, the diversity guarantee in Theorem 2 decreases with b. Specifically, Lemma 1 implies this ratio bound is at least 1 - b/K, which is tight in many cases. We also observe this linear relationship frequently in our experimental results (Section 4). This also means by setting b such that b/K is constant, the algorithm guarantees simultaneously constant approximation ratios in both objective values and diversity, independent of |V | and r. Additionally, with α = 1 - e-b/K , we have 1 - b/K = 1 + ln(1 - α), giving a direct objective-diversity trade-off curve (in terms of ratios) within α ∈ [0, 1 - 1/e].

For general matroids, we can infer the objective approximation guarantee from Algorithm 1 as a function of parameter b, by using an important result in [Fisher et al., 1978].

Lemma 4 Algorithm 1 under a matroid M = (V, I) outputs [1 - (1 - 1/rM)min{b,k} ]-approximations of f over I where k =min {|z| : z ∈ 2V \ I } -1. Additionally, these solutions are b/(2rM)-approximations.

Algorithm 2: Greedy with representation limits

Input: f, S, r, l // Assuming l ∈ [1, r] Output: P ∈ Sr 1 v∗ ← argmaxv∈S f({v}), P ← {{v∗ }}r ; 2 κ(·) ← {u ∈ (V \ ·) : (· ∪ {u}) ∈ S ∧ nu(P) < l}; 3 R ← {(z, v) : z ∈ P, v ∈ κ(z), f(z ∪ {v}) ≥ f(z)}; 4 while R ̸= ∅ do // below argmin over vectors is done in left-to-right lexicographical order 5 (y, v) ← argmin (z,u)∈R (|z|, f (z) - f (z ∪ {u}), f (z), nu(P )); 6 P ←P \ {y} ∪ {y ∪ {v}}; 7 Update R as in Line 3;

Theorem 3 For any monotone f over 2V , matroid M = (V, I), and integers r ≥ 2, b ∈ [0, rM), ∀P ∈ A (f, UV,K, b, r), ss(P ) ≥ g(rM - b - 1, rM - b - 1, r) + g(m, 1, r), where m = |V \ clM(x)| - rM + b + 1 and x is the solution obtained in the first phase of the algorithm. Moreover, this bound is tight for any |V | ≥ 1, r ≥ 2, matroid rank rM ∈ [1, |V |], b ∈ [0, s) and m ∈ [1, |V | - rM + b + 1].

It is important to note that while the bound in Theorem 3 can be small for any positive choice of b if the closure of the common elements set x is large, sufficiently large ones (e.g. |clM(x)|/|x| > |V |/rM) also lower the upper bound on maximum diversity, according to Lemma 3.

3.2 Simultaneous GreedyWith Representation Limits

The second approach, outlined in Algorithm 2, is inspired by the SIMULTANEOUSGREEDYS algorithm proposed in [Feldman et al., 2020], which obtains a set of disjoint solutions, in which the best one provides an approximation guarantee. Since for our problem, all solutions need to be sufficiently good, we make crucial changes to adapt the algorithm to the task. Firstly, each element can appear in multiple solutions, the maximum number of which is given as an input (l). This simultaneously expands the selection pool for each solution in each iteration, which helps with quality, and controls the amount of representation in the output each element enjoys, which guarantees some diversity. Secondly, a single element (v∗ ) is allowed to be included in all solutions, so a non-trivial quality guarantee is possible, as there are instances where excluding an element ensures that the solution is arbitrarily bad. Finally, the selection criteria, especially the first one, enforce building solutions evenly, so the worst one does not fall too far behind. This allows us to derive a non-trivial lower bound on the objective value of every solution in the output.

Compared to Algorithm 1, this algorithm does not maximize diversity directly, but guarantees it indirectly by imposing additional constraints. Since these constraints are on elements' representation, it can be applied to the problem (1) with any diversity measure that can be formulated by elements' representation, such as entropy [Neumann et al., 2021].

The time complexity of Algorithm 2 is O(rrM|V |) in both value oracle model and independence oracle model. Like Algorithm 1, it may not return r bases if rrM is sufficiently large and l is sufficiently small. We remark that the inclusion of the initial element v∗ in all solutions is meant to deal with pathological instances; this might be avoided with a more complex heuristic. With a view to simplicity, we choose not to pursue this further in this work.

We observe that if l = r, Algorithm 2 must return solutions obtainable by the classical greedy algorithm since if there is a v ∈ V that cannot be added to a solution x due to the new constraint, then v ∈ x. However, one can construct instances where it is guaranteed to achieve ss value of 0, even when restricted to uniform matroids and linear objective functions. Therefore, we only consider cases where l < r. We show the extent to which diversity is guaranteed, simply from limiting elements' representations.

Similarly, we use B(f, S, r, l) to denote the collection of possible outputs from Algorithm 2 when run with inputs f, S, r, l. Given a matroid M = (V, I), for any P ∈ B(f, I, r, l) and x ∈ P, let Pt be P at iteration t (P0 = {{v∗ }}r ), tx,i be the iteration in which the i-th element is added to x (counting v∗ ), x(i) be x right after that iteration, Vi = {v ∈ V : nv(Ptx,i-1) ≥ l}, Wi = clM (x(i-1) ) and Ui = Vi ∪Wi \ x(i-1) . Intuitively, Ui contains elements that cannot be added to x at step i; inspecting this set gives the following guarantee.

We show the lower bound on the ss value as the algorithm progresses.

With Lemma 5 and 6, the following objective-diversity trade-off guarantees can be inferred.

Theorem 4 Given monotone submodular f over 2V , integers r ≥ 2, l ∈ [1, r) and K ∈ [1, |V |], then for all P ∈ B (f, UV,K, r, l) and k ∈ [1, (r - 1)K/l],

where h = min{r(K - 1), l(|V | - 1)} and c ∈ [0, l) such that c ≡ h mod l. 5 Moreover, the former bound is nearly tight when K ≥ r + l - 1, and the latter bound is tight for any |V | ≥ 1, r ≥ 2, K ∈ [1, |V |], and l ∈ [1, r].

Theorem 5 Given monotone submodular f over 2V , matroid M = (V, I), integers r ≥ 2 and l ∈ [1, r), then for all P ∈ B (f, I, r, l)

Moreover, the former bound is nearly tight, and the latter bound is tight for any |V | ≥ 1, r ≥ 2, matroid rank rM ∈ [1, |V |], and l ∈ [1, r].

5 The latter bound holds trivially at l = r.

We remark that the tightness cases in the proof of Theorem 5 prevent Algorithm 2 from exercising the last tie-breaking rule, which is the component that lets it improve diversity beyond the lower bound. We suspect that this bound might be overly pessimistic for instances where the image under f of the feasible set is small.

The result suggests that for uniform constraints, setting l = max{⌊r(rM - 1)/(|V | - 1)⌋, 1} leads to Algorithm 2 guaranteeing (1 - 1/|V |)(1 - O(1/rM)) approximation ratio in diversity, whereas l = ⌊r/2⌋ guarantees (rM - 1)/|V | approximation ratio for pathological matroid constraint. Additionally, if l/r is constant, then every output solution guarantees a constant approximation ratio in objective value.

Above results only consider extreme values (e.g. optimal f value). On the other hand, by comparing the algorithm's output against an arbitrary solution set, a more nuanced picture emerges which suggests the algorithm can exploit a certain feature in the global structure of f to lessen compromise on diversity (i.e. by lowering parameter l) while maintaining objective guarantees.

Theorem 6 Given monotone submodular f over 2V , integers r ≥ 2, l ∈ [1, r), K ∈ [1, |V |] and Y ∈ (2V )∗ such that m = maxv∈V nv(Y ), then for all P ∈ B (f, UV,K, r, l)

where h = max {l ∑y∈Y |y|/[Km(r - 1)], 1}. This bound is nearly tight for all r ≥ 2, l ∈ [1, r), size of Y and m ∈ [1, |Y |].

Corollary 1 If there is Y ∈ (2V )k for some k ≥ 1 where maxv∈V nv(Y ) < l ∑y∈Y |y|/[K(r - 1)] and ∑y∈Y f(y)/k ≥ αmax|y|≤K f(y), then Algorithm 2 under K-rank uniform constraint returns α/2-approximations with parameter l. If there is a set of k disjoint α-approximations, then Algorithm 2 returns α/2-approximations at any l ∈ [(r - 1)/k, r).

Theorem 7 Given monotone submodular f over 2V , integers r ≥ 2, l ∈ [1, r), matroid M = (V, I) and Y ∈ I ∗ such that m = maxv∈V nv(Y ), then for all P ∈ B (f, I, r, l)

This bound is nearly tight for all r ≥ 2, l ∈ [1, r), size of Y and m ∈ [1, |Y |].

Corollary 2 Given a matroid M = (V, I), if there is Y ∈ I k for some k ≥ 1 where maxv∈V nv(Y ) ≤ lk/(r - 1) and ∑y∈Y f(y)/k ≥ αmaxy∈I f(y), then Algorithm 2 under matroid constraint M returns α/3-approximations with parameter l. If there is a set of k disjoint α-approximations, then Algorithm 2 returns α/3-approximations at any l ∈ [(r - 1)/k, r) and α/(2 + 1/k)-approximations at l = r - 1.

Going further, these bounds can be strictly improved when the number of disjoint optimal solutions exceeds certain thresholds. In particular, we show that in such cases, Algorithm 2 guarantees objective values identical to those from the classical greedy when maximizing monotone submodular functions under the same constraints [Nemhauser et al., 1978; Fisher et al., 1978]. For a function f and a solution set S let D(f, S, α) be the largest number of disjoint non-empty α-approximations of f over S, and for a solution x, let ix be its size before it stops being improved by the algorithm.

Theorem 8 Given monotone submodular f over 2V , integers r ≥ 2, l ∈ [1, r), and matroid M = (V, I), then for all P ∈ B (f, I, r, l), given x ∈ P where |x| > 1 and D(f, I, α) > ⌊η(r - 1)/l⌋ for some α, then

• f(x) ≥ αmaxy∈I f(y)/2 if M is non-uniform and η = ix. If D(f, I, α) = ⌊η(r - 1)/l⌋, the bound does not necessarily hold in either case.

We include a simple observation relating maximum diversity and the number of disjoint approximations.

Observation 2 Let k = D(f, S, α) for some function f, solution set S ⊆ 2V , threshold α, then the maximum ss value to a (f, S, r, α)-instance is at most g(h, s, r) where h = min{r(s - 1) + k, |V |} and s = maxx∈S |x|.

4 Experimental Investigation

To observe how these algorithms perform on concrete instances, we experiment with the maximum vertex coverage problem: given a graph G = (V, E), find a set x ∈ I for some matroid M = (V, I) that maximizes |x ∪ {v ∈ V : ∃u ∈ x, {u, v} ∈ E}|, which is monotone submodular. For the benchmark instance, we use the complement of frb30-15-1, frb30-15-2, frb35-17-1, frb40-19-1 from the standard benchmark suite BHOSLIB created using the Model RB [Xu and Li, 2006], containing 450, 450, 595, 760 vertices respectively, and 17827, 17874, 27856, 41314 edges respectively; these are available at [Rossi and Ahmed, 2015].

We use four matroid constraints in the experiments, including 2 uniform matroids and 2 partition matroids. As mentioned, partition matroids admit a independence collections of the form I = {x ⊆ V : ∀i = 1, . . . , k, |x∩Vi| ≤ bi} for some partitioning {Vi}ki=1 of V and integers {bi}ki=1 . These are useful in modeling group-based budget constraints [Cornuejols et al., 1977; Nemhauser et al., 1978; Chekuri and Kumar, 2004; Chekuri and P´al, 2005; Fleischer et al., 2006]. For uniformmatroids, we set the ranks to {10, 15}, and denote them with U10 and U15, respectively (the numbers represent the ranks). For partition matroids, we group consecutive vertices sorted by degrees into 10 partitions, i.e. Vi contains from |V |(i-1)/10+1th to |V |i/10-th smallest degree vertices. This is to force the solutions to include a limited number of high-degree vertices, creating scenarios where the greedy algorithm would obtain very different solutions from the ones it would return under uniform constraints. In case 10 does not divide |V |, we set |Vi| = ⌊|V |/10⌋ for i = 2, . . . , 10. For the first partition matroid (denoted P10), we set bi to 1 for all i, while for the second (denoted P15), we assign 6 to b1 and 1 to the rest.

For each of the 16 instances, we run with r ∈ {20, 100}, Algorithm 1 with all parameter values b ∈ [0, rM], and Algorithm 2 with all parameter values l ∈ [1, r]. For both algorithms, the last tie-breaking is done by selecting the first choice (in increasing order of vertex labels). Therefore, there is no randomization, so each algorithm is run once on each instance with each parameter value.

To contextualize the results, we obtain a best known coverage for each instance using the built-in integer linear programming solver in MATLAB. Furthermore, the upper bounds on ss values are given by ∑i g(|Vi|, bi, r) since ss can be decomposed by disjoint subsets (in case of uniform matroid, Vi ← V and bi ← rM). Note that this bound applies to all threshold ratio α ∈ [0, 1], the actual optimal value might very well be much smaller, especially for α close to 1. We choose not to normalize our results against actual optimal values because a) solving exactly the problem (1) is prohibitively costly, and b) this is exacerbated by the large number of α values for each of which an optimal value needs to be obtained (i.e. the number of distinct minimum objective values from the algorithms on each instance).

The results are shown in Figure 1 and 2, which visualize, for each graph-constraint-parameter combination, the mean and minimum objective values in the output, and the ss value.

We see that the objective values in the outputs are high (within 5% gap of the optimal) for r = 20, and predictably degrade for r = 100 (about 30%), although the mean values stay within 10% in most settings. Notably, Algorithm 2 produces higher minimum objective values than Algorithm 1 does in most settings, and smaller gaps between mean values and minimum values. More importantly, Algorithm 2 achieves significantly higher ss values in most settings, thus yielding better objective-diversity trade-offs than Algorithm 1. This indicates benefits of limiting common elements by controlling their representation in the output, as they do not contribute to diversity.

Interestingly, increasing the output size r only seems to affect the objective values, as the relative diversity values are virtually the same across all settings. We suspect that this might change for more complex matroids. Incidentally, the impacts of r on objective values from Algorithm 2 seem minimal outside of edge cases (i.e. l = 1).

5 Conclusion

The diverse solutions problem is a challenging extension to optimization problems that is of practical and theoretical interests. In this work, we considered the problem of finding diverse solutions to maximizing monotone submodular functions over a matroid. To address the difficulty in finding multiple highquality solutions, we exploited submodularity with two simple greedy algorithms, equipped with objective-diversity trade-off adjusting parameters. Theoretical guarantees by these algorithms were given in both objective values and diversity, as functions of their respective parameters. Our experimental investigation with maximum vertex coverage instances demonstrates strong empirical performances from these algorithms despite their simplicity.

Acknowledgements

This work was supported by the Australian Research Council through grants DP190103894 and FT200100536.