Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy

In this paper, we obtain the first result that multiplicatively improves over the approximation guarantee of the greedy algorithm for the problem of maximizing a monotone submodular objective function subject to a general matroid $k$-intersection constraint. Our technique is based on the one of Singer and Thiery [38], and like theirs, works also for the more general family of matroid $k$-parity constraints.

Let us briefly review the algorithm of Thiery and Singer. Given some $\delta >0$,³³3In our algorithm, we fix $\delta =1/2$, but we leave it as a parameter here for consistency with [38]. Thiery and Singer define a sequence of markers (or thresholds), of the form $m_i=W{(1-\delta )}^{-i}$, where $W$ is the maximum weight of any element and $i\in {\mathbb{Z}}_{\ge 0}$. These are used to partition the elements into classes according to their weight: an element $e$ appears in the $i$-th weight class if $w(e)\in [m_i,m_{i-1})$. The algorithm processes weight classes in descending order of weight and maintains a solution $A$, which is initially empty. When processing a weight class $C$, the algorithm applies local search to find a feasible approximately maximum weight extension $X\subseteq C$ to the current solution $A$. The elements of $X$ are then permanently added to $A$, and the algorithm continues to the next weight class. Intuitively, since all elements in $C$ have similar weights, one mainly cares about maximizing the number of elements in $X$. Let $X^{\ast }$ denote the largest possible extension $X$. Guarantees for the local search procedure for the unweighted matroid $k$-parity problem can be leveraged to show that $|X|\gtrsim (2/k)\cdot |X^{\ast }|$. However, the size of $X^{\ast }$ might be smaller than the number of elements of the optimal solution within the class $C$ because some elements of the optimal solution might be “blocked” by elements from heavier weight classes that are already in $A$. In order to bound the weight of the blocked elements, Thiery and Singer note that each selected element $e$ can block at most $k$ elements in total. Thus, if each blocked element has weight of at most $c\cdot w(e)$ for some , then one obtains $c\cdot k$ approximation for blocked elements. Unfortunately, $c$ might be very nearly 1, in which case the guarantee degenerates to $k$. However, this can happen only when the blocking element $e$ falls near the boundary of its weight class. To avoid this, Singer and Thiery multiply all markers by a single uniformly random shift $\tau$. They then show that for each element, the probability some marker $m_i$ lands near its weight is small, and thus the expected approximation for all blocked elements can indeed be bounded by $c\cdot k$ for some .

A major obstacle for adapting the algorithm of Singer and Thiery to submodular functions is that, under such functions, there is no longer a static notion of weight. Previous works [28, 42, 6, 8] have adapted local search algorithms for weighted maximization to submodular objectives by using the marginal or incremental contributions of an element $e$ as a surrogate weight. In other words, if $f$ is the objective function, then the adaptations implicitly define the weight of $e$ to be $w(e)\triangleq f(A\cup \{e\})-f(A)$, where $A$ is the current solution.⁴⁴4In some cases, $A$ is in fact some appropriate subset of the current solution, but this distinction is unimportant for the sake of this high-level discussion. However, applying this idea to the algorithm of Singer and Thiery [38] breaks their solution for the problem of bounding the weight of the blocked elements. Recall that Singer and Thiery obtain this bound by applying a random shift, which guarantees that the probability that the weight of an element $e$ is close to the boundary of its weight class is small. However surrogate weights $w(e)$ defined as above depend on the solution $A$ constructed by the algorithm, and indirectly also on the random shift. This creates correlations between the weights and the shift, which make it difficult to bound the probability that the weight of an element is close to the boundary of its weight class.

Our solution for the above hurdle is to introduce an additional auxiliary weight $u(e)$ for every element $e$ in the optimal solution $O$. Unlike the surrogate weights $w(e)$, the weights $u(e)$ depend only on $O$, and not on the solution set $A$, and thus are independent of the random shift of the algorithm. However, as these weights depend on the unknown set $O$, they are unavailable to the algorithm, which must continue to use the weights $w(e)$. This limitation of the algorithm is not important when $w(e)$ and $u(e)$ roughly agree, and thus, the output of the algorithm is good (in expectation) in this case. In order to obtain a result that holds in general, we further show that whenever the two weights disagree significantly, this discrepancy can be used to obtain an alternative bound on the value of the output of the algorithm.

Along the way, we observe that since the weight classes are defined using exponentially decreasing thresholds, it is natural to draw the random shift used by the algorithm to set these thresholds from an exponential distribution. Using this distribution for the shift instead of the uniform distribution employed by [38] leads to some improvement also for linear objective functions compared to the approximation ratio of roughly $0.722k+O(1)$ obtained by [38]. More formally, we prove the following theorem.

We note that the algorithm of [38] considers exchanges of size proportional to $k$ in its local search, which leads to a time complexity that is polynomial only when $k$ is constant. In contrast, the algorithm of Theorem 1.1 considers only exchanges of constant size, and therefore, runs in polynomial time regardless of the value of $k$.

We also consider the maximization of a non-monotone submodular function subject to a matroid $k$-parity constraint. Algorithms for maximizing monotone submodular functions usually still produce for a non-monotone submodular function $f$ a guarantee of the form $f(A)\ge \alpha \cdot f(A\cup O)$, where $A$ is the output set of the algorithm, $O$ is the optimal solution and $\alpha$ is positive number. Gupta, Roth, Schoenebeck and Talwar [18] described a general framework for translating such a guarantee into a real approximation ratio, and their framework was improved by subsequent works [33, 13]. Unfortunately, because of the use of our novel auxiliary weights, when our algorithm from Theorem 1.1 is analyzed in the context of a non-monotone submodular function $f$, it yields a guarantee of the more involved form $f(A)\ge \alpha \cdot f(A\cup O)-\beta \cdot f(O)$ for some . Nevertheless, we are able to adapt the version of the framework used by [13] to transform guarantees of our more involved form into standard approximation ratios, which yields the following theorem.

When $k=2$, one can exactly optimize a linear function over a matroid $k$-intersection constraint via the classical algorithms of Edmonds [12] or Cunningham [10]. Similarly, a $2$-set packing constraint is simply a standard matching constraint, and one can exactly optimize linear functions over it in polynomial time. Lawler [26] introduced the family of matroid parity constraints as a common generalization of both these families of constraints. Here, we are given a set $E$ of disjoint pairs of elements from $V$ and a matroid $ℳ$ on $V$, and the goal is to find a collection of pairs from $E$ whose union is independent for $ℳ$. In contrast to 2-set packing and matroid 2-intersection, it is impossible to maximize even a cardinality objective under a matroid parity constraint in polynomial time when the matroid is given as an independence oracle [31, 23]. The problem is also known to be NP-hard (see, e.g., [37, §43.9]), but Lee, Sviridenko and Vondrák [29] showed that it admits a PTAS.

When $k\ge 3$, optimizing over both matroid $k$-intersection and $k$-set packing constraints is NP-hard as both these constraint families generalize $k$-dimensional matching constraints, and optimizing over the last family of constraints is NP-hard even for cardinality objectives [24]. All these types of constraints are generalized by the family of matroid $k$-parity constraints, and this family also generalizes the above-mentioned family of matroid parity constraints in the sense that matroid parity constraints are equivalent to matroid $2$-parity constraints. The formal definition of matroid $k$-parity constraints can be found in Section 2, and we refer the reader to [29] for a more detailed discussion of the relationship between these and other families of constraints.

Finally, we note that improved results are known in several special cases. For matroid $2$-intersection constraints, Huang and Sellier [20] give a $\frac{3}{2}$-approximation in the special case that the objective is a vertex cover function. For matroid $k$-parity constraints, there are several results for the special case that the matroid is linear and a representation is given. In this setting, when $k=2$ an exact polynomial time algorithm for cardinality objectives was given by Lovász [30], and Iwata and Kobayashi [21] later gave an exact polynomial time algorithm for maximizing linear objectives. For larger $k$ values, in the same setting, exact FPT algorithms are known for both cardinality and linear objectives, with exponential dependence on $k$ and the rank of the matroid or the number of blocks in the solution [2, 32]. In contrast, in this paper, we give approximation algorithms that require no assumptions on the structure of the underlying matroid and have a running time that is independent of $k$.

A set function $f:2^E\to ℝ$ is a function that assigns a value to every subset of a given ground set $E$. Given a set $S$ and an element $e$, we denote by $f(e\mid S)\triangleq f(S+e)-f(S)$ the marginal contribution of $e$ to $S$. Similarly, given an additional set $T$, we denote by $f(T\mid S)\triangleq f(S\cup T)-f(S)$ the marginal contribution of $T$ to $S$. The set function $f$ is called monotone if $f(e\mid S)\ge 0$ for every set $S\subseteq E$ and element $e\in E$. The set function $f$ is called submodular if $f(e\mid S)\ge f(e\mid T)$ for every two sets $S\subseteq T$ and element $e\in E\setminus T$. In other words, $f$ is submodular if the marginal contribution of an element $e$ to a set $S$ can only diminish when additional elements are added to the set $S$. An alternative, equivalent, characterization of submodularity states that $f$ is submodular if and only if $f(S)+f(T)\ge f(S\cup T)+f(S\cap T)$ for every two sets $S,T\subseteq E$.

In the case that $f(S)+f(T)=f(S\cup T)+f(S\cap T)$ for all $S,T\subseteq E$, we say that $f$ is modular. Equivalently, a modular set function can be defined as a function of the form $f(S)=w_0+{\sum }_{e\in S}{w}_e$, where $w_0$ and $\{w_e\mid e\in E\}$ are arbitrary real values. In the special case that $w_0=0$ (and thus, $f(\mathrm{\varnothing })=0$), we say that $f$ is linear.

Our algorithms optimize a submodular set function $f$. However, as in the case of combinatorial constraints, it often does not make sense to assume that the algorithm has an explicit description of $f$ because this description can be exponential in the size of the ground set $E$. Instead, our algorithms implicitly make the standard assumption that $f$ is accessed through a value oracle that given a set $S\subseteq E$ returns $f(S)$.

This section describes a partition of $O$ into disjoint sets $O_1,O_2,\mathrm{\dots },O_L$. Analogously to the sets $A_{\le i}$, for every integer $0\le i\le L$, we use $O_{\le i}$ to denote the union ${\cup }_{j=1}^i{O}_j$. Intuitively, each set $O_i$ represents elements from $O$ whose values can be bounded in terms of the elements selected as $A_i$ in iteration $i$ of Algorithm 1 and thus need not be considered when later iterations of this algorithm are analyzed. In line with this intuition, we prove below that the elements of $O\setminus O_{\le i}$, whose values need to be bounded in terms of elements selected by later iterations, can all be feasibly added to the solution $A_{\le i}$ that Algorithm 1 has after iteration $i$.

We can now formally define the partition of $O$. Recall that $O_{\le 0}=\mathrm{\varnothing }$ by definition. For every $i\in [L]$, the set $O_i$ is given by the recursive formula $O_i\triangleq \{o\in O\setminus O_{\le i-1}\mid N_o^{(i)}\ne \mathrm{\varnothing }\}$, where $\{N_o^{(i)}\subseteq A_{\le i}\mid o\in A_{\le i-1}\cup (O\setminus O_{\le i-1})\}$ is the collection of sets obtained by applying Lemma 2.1 with the sets $A_{\le i}$ and $A_{\le i-1}\cup (O\setminus O_{\le i-1})$ as the sets $A$ and $B$ of the lemma, respectively. Recall that applying Lemma 2.1 with these sets requires them to be feasible. The feasibility of $A_{\le i}$ is clear. The feasibility of $A_{\le i-1}\cup (O\setminus O_{\le i-1})$ follows from the next observation, which can be proven by induction on $i$ using claims 1 and 2 of Lemma 2.1.

We now define the weights we use to quantify the values of elements in $O$ and $A_{\le L}$. An element’s weight is based on the incremental value it adds to a given set, and in the linear case it corresponds exactly to the weight of this element in the definition the objective function $f$ (as long as this weight is non-negative). In order to define the incremental values, we order the elements of $A_{\le L}$ as $a_1,a_2,\mathrm{\dots },a_{|A_{\le L}|}$, in the order in which they were last added by Algorithm 1 to any of the sets $A_1,A_2,\mathrm{\dots },A_L$. Applying $(\theta ,\epsilon )$-improvements of the third kind involves adding $2$ elements to $A_i$ at the same time, which creates an ambiguity. To resolve the ambiguity, recall that in such improvements, Definition 3.1 specifies that there must be a way to assign the two added elements the labels $x_1$ and $x_2$ so that $f(x_1\mid A)\ge \theta$ and $f(x_2\mid A+x_1)\ge \theta$, where $A$ is the set improved by the $(\theta ,\epsilon )$-improvement. In our ordering of $A_{\le L}$, we suppose that the element corresponding to $x_1$ is added to $A_i$ immediately before the element corresponding to $x_2$.⁵⁵5If both ways to label the added elements obey the above inequalities, then we arbitrary select one of them. Given our ordering $a_1,\mathrm{\dots },a_{|A_{\le L}|}$, we define the weight of each element $a_j\in A_{\le L}$ as $w(a_j)\triangleq f(a_j\mid \{a_1,a_2,\mathrm{\dots },a_{j-1}\})$.

We proceed similarly for elements in $O$. Let us denote the elements of $O$ by $o_1,o_2\mathrm{\dots },o_{|O|}$ in an arbitrary order.⁶⁶6While the order $o_1,o_2\mathrm{\dots },o_{|O|}$ is arbitrary, it is essential that this order is not chosen in a way that depends on the random bits of Algorithm 1. Then, for any $o_j\in O$, we define

Note that we ensure that the $\overline{w}$ weights are always non-negative. Let us briefly provide some intuition for the second expression in the maximum. For any $o_j\in O\setminus A_{\le L}$, this term is equal to $f(o_j\mid A_{\le L}\cup \{o_1,\mathrm{\dots },o_{j-1}\})$, and thus the weights $\overline{w}$ capture the incremental values obtained when adding all such elements sequentially to the set $A_{\le L}$. For any element $o_j\in O\cap A_{\le L}$, we could define $\overline{w}(o_j)=0$, since it provides no such incremental value. However, it is useful in the linear case to ensure that all the weights we are defining are equal to the natural notion of an element’s weight (i.e., $f(\{x\})$) whenever this weight is non-negative. The chosen expression ensures that this is the case even for $x\in O\cap A_{\le L}$.

It is convenient to extend the above-defined weights to sets. We do this in the natural way, i.e., for any set $T\subseteq A_{\le L}$, we define $w(T)\triangleq {\sum }_{e\in T}w(e)$, and for any set $T\subseteq O$, we define $\overline{w}(T)\triangleq {\sum }_{e\in T}\overline{w}(e)$. The following lemma proves some basic properties of the weights $w$ and $\overline{w}$. The first three claims of the lemma show that an element’s weight must fall into a particular range defined by the values $m_i$, depending on which (if any) set $A_i$ or $O_i$ this element appears in. The final claim relates the two weights $w$ and $\overline{w}$ given to elements that appear in both $A_{\le L}$ and $O$.

In our charging scheme, we consider three different types of elements of $O$. The first is the elements that belong to some $O_i$, have weights approximately equal to the weights of the elements in $A_i$ (up to a factor of $m_{i-1}/m_i=2$) and can charge to only a single element of $A_i$. We denote below by $O^{(s)}$ the set of these elements. Intuitively, our analysis uses an argument borrowed from the $(k/2+\epsilon )$-approximation algorithm for the unweighted matroid $k$-parity problem [29] to show that the elements of $O^{(s)}$ only contribute an additive constant to the approximation guarantee. The next type is the elements of $O\setminus O_{\le L}$, which are “left over” at the end of Algorithm 1. The contributions of these elements are small, and can be essentially ignored. The final type is all remaining elements, i.e., $O_{\le L}\setminus O^{(s)}$.

To formally define the set $O^{(s)}$ of the first type of elements of $O$, we define a set $N_o$ for every element $o\in O_{\le L}$ as follows. For any $o\in O_{\le L}$, let $i$ be the single integer in $[L]$ for which $o\in O_i$, and define $N_o\triangleq N_o^{(i)}$ (recall that $N_o^{(i)}$ is defined in Section 4.1). Intuitively, one can think of $N_o$ as the set of elements of $A_{\le L}$ that are responsible for the inclusion of $o$ in $O_i$. We then define for every $i\in [L]$ a subset $O_i^{(s)}\subseteq O_i$ given by $O_i^{(s)}\triangleq \{o\in O_i\mid \overline{w}(o)>m_i\text{ and }|N_o|=1\}$. Then, we can define $O^{(s)}\triangleq {\bigcup }_{i=1}^L{O}_i^{(s)}$. Notice that this definition is consistent with the above intuition in the following senses. First, each element $o\in O^{(s)}$ has indeed only a single element in $N_o$ to “blame” for its inclusion in $O_i$ and thus only a single element to charge to. Second, the weight of $o$ is comparable to the weight of this single element because $N_o\subseteq A_i$ (see Observation 4.4 below), which implies by claim 1 of Lemma 4.3 that the weight of every element in $N_o$ is in the range $[m_i,m_{i-1}]$.