1 Introduction↩︎

Maximizing submodular and linear functions subject to a \(k\)-matroid intersection constraint is a central topic in combinatorial optimization. When \(k = 1\), Greedy is optimal for maximizing linear functions, and celebrated algorithms by Calinescu, Chekuri, Pál, and Vondrák [1] and Filmus and Ward [2], [3] are optimal for monotone submodular functions. For \(k = 2\), Edmonds’ matroid intersection algorithm outputs an optimal solution for linear objective functions [4]. Such algorithms imply the existence of optimal methods for finding maximum weight spanning tree, matchings, disjoint arborescences, and for maximizing welfare in the allocation of goods to agents since they are special cases of linear and submodular maximization over matroid constraints [1], [5].
In this paper, we consider a \(k\)-Matroid Intersection constraint for \(k \geq 3\). Until recent years, no multiplicative improvement over Greedy’s guarantee was known even for linear objectives beyond cardinality maximization. Greedy achieves a \(k\)-approximation for linear functions, and \((k+1)\)-approximation for monotone submodular functions [6]. A linear dependence on \(k\) is needed. Hazan, Safra, and Schwartz [7] first showed that the problem is \(\NP\)-hard to approximate within a factor of \(\Omega(k/\log(k))\). This was recently strengthened by Lee, Svensson, and Thiery [8], who obtained a \(k/12\)-hardness result, and further by Minzer and Zheng [9] to \(k/8\), assuming \(\P \neq \NP\).
For cardinality maximization, there exists a \(\frac{k}{2} + \e\)-approximation algorithm for any constant \(\e >0\) [10]. The general linear case is in fact more complex since global counting arguments, which are used in the cardinality case, are no longer sufficient. Singer and Thiery recently overcame this barrier and presented the first multiplicative improvement over Greedy [11] for linear objectives. They designed a \(\frac{k}{\ln(4)} + O(1)\)-approximation algorithm improving over the former \((k-1)\)-approximation algorithm by Lee, Sviridenko, and Vondrák [12]. Building on these ideas, Feldman and Ward [13] extended the framework to monotone submodular maximization, obtaining approximation ratios of \(k\ln(2)+O(1)\) and \(\frac{k\ln(4)}{\ln(2)+1}+o(k)\) for linear and monotone submodular objectives, respectively. Despite this progress, these works leave open the question of bridging the gap between the unweighted and the weighted/submodular settings. In this work, we close this gap fully up to additive terms.

Our algorithm is the first to achieve an approximation ratio for monotone submodular functions that asymptotically matches the best unweighted approximation guarantee [10]. We remark that, similarly to [10], [11], [13] our guarantees hold for the more general Matroid \(k\)-Parity constraint. This leads to improved guarantees for Bounded Degree Maximum Independent Set considered recently by Bai, Bérczi, and Siemelink [14] which can be cast as a Matroid \(k\)-Parity constraint for example. Further applications can be found in [15]. This result settles the gap for large values of \(k\) and leaves as exciting open lines of research the question of finding a matching guarantee for low values of \(k\), and of improving over the unweighted guarantees.
Notably, our algorithm is a simple local search-based method. However, we make a crucial observation that the local search performs better when \((1)\) local swaps are processed in decreasing order over the edges’ weight (marginal contribution in the submodular setting), and \((2)\) only swaps that make significant gain, as parametrized by a function in \(k\), are taken. Variants of this greedy processing of the local search order have been employed in [11], [13], [16].
We further leverage our techniques to obtain an improved approximation ratio for \(k\)-Set Packing. This problem is a special case of \(k\)-Matroid Intersection with a long line of research gradually improving on approximation guarantees [16]–[26]. For this special case, better approximation ratios than \(\frac{k}{2}\) were already known in the weighted setting. The best guarantee for weighted \(k\)-Set Packing is a \(\frac{k}{2.00561} + O(1)\)-approximation due to Neuwohner [25]. Her algorithm employs Cygan’s [18] \(\frac{k+1}{3}\)-approximation algorithm for the unweighted problem to overcome the \(\frac{k}{2}\)-barrier. In this work, we combine our asymptotic \(\frac{k+o(k)}{2}\)-approximation algorithm with the algorithm of Singer and Thiery [11] (using the existence of a \(\frac{k+1}{3}\)-approximation for the unweighted problem) to improve upon Neuwohner’s result [25]. We achieve an improved approximation guarantee of \(\frac{k}{2.16404} + o(k)\) for linear objectives, and our method provides an alternative to those based on Berman’s \(w^2\) local search algorithm [21], [23]–[26].

1.1 Overview of our Approach↩︎

Our main algorithm is inspired by the method introduced in [11] and continued in [13]. These advances interpolate between greedy and local search. They randomly partition the instance into almost unweighted weight buckets, process them greedily, and run the state-of-the-art unweighted algorithm on each weight class. Unfortunately, this approach suffers from the inherent tradeoff between the approximation obtained in a single weight bucket and the loss incurred by committing to the greedy order over the buckets.
In contrast, our algorithm avoids bucketing altogether and processes the edges in decreasing order of their weight in a continuous fashion. Concretely, we perform a local-search parametrized by values \(\alpha\), and \(\theta\). The algorithm processes all edges of weight at least \(\theta\) in decreasing order of \(\theta\) and makes all local swaps that increase the value by at least \(\alpha\). An \(\alpha\)-swap adds a set of edges whose weight is at least \(\alpha\) times that of those removed. Thus when no \(\alpha\)-swap can be found, the threshold \(\theta\) is decreased so edges of smaller weight become eligible for local search. When the objective function is submodular, edge weights are defined by an auxiliary weight function akin to [13].

1.2 Techniques↩︎

We now give some intuition as to why the above method achieves a \(\frac{k}{2} + o(k)\)-guarantee and for simplicity assume we work with a \(k\)-set packing instance and a linear function. Typical for local search methods, we will construct a sequence of non-improving local swaps, and aim to aggregate them to derive an approximation guarantee. In particular, we consider \(O_\theta\) to be the edges of \(\opt\) of weight \(\theta\) and consider our algorithm’s solution \(A_\theta\) after processing all edges of weight at least \(\theta\). A typical unweighted analysis shows that the weight of the neighborhood of \(O_\theta\) in \(A_\theta\) is at least a \(\frac{2}{k+\alpha}\) portion of the weight \(O_\theta\). We then consider two sets: (1) the edges \(o \in O_\theta\) whose neighborhood remains in the final output after processing all weights, or (2) the edges \(o \in O_\theta\) whose neighborhood gets discarded in some local search iteration preceding the final output.
Aggregating over edges for which the first case happens, we can intuitively recover the \(\frac{k + \alpha}{2}\)-guarantee. This guarantee is successful for small enough \(\alpha\). In the second case, each discarded neighbor implies the existence of an \(\alpha\)-swap greatly increasing the value of our algorithm’s solution. We prove that the weight of \(O\) for which (2) happens is bounded by \(\frac{k}{\alpha - 1}f(A)\), where \(A\) is the final solution. This fact is reminiscent of the analyses of [16], [27]. This requires \(\alpha\) to be a large parameter to minimize the effect of (2). Combining these two facts proves our main theorem when \(\alpha = \theta(\sqrt{k\log(k)})\).

1.2.0.1 Dealing with Matroid \(k\)-Parity:

There is a technical complication when dealing with a matroid \(k\)-parity constraint. Indeed, while the choice of neighbors is direct for \(k\)-Set Packing as hyperedges that cover the same vertices, our proof proceeds by fractionally assigning neighborhoods via the matroid independence oracle. More precisely, consider some \(o \in O\) such that \(w_o = \theta_0\). Then, we can decompose \(\theta_0 = \sum_{i} (\theta_{i-1} - \theta_i)\) for all thresholds \(\theta_i\) considered by the algorithm. Then, we assign a \(\theta_{i-1} - \theta_i\) portion of \(o\)’s weight to its neighborhood in the round that threshold \(\theta_i\) is introduced. We therefore do not need to explicitly keep track of neighborhoods and can instead naturally integrate over \(\theta\).

1.2.0.2 Dealing with Submodularity:

When \(f\) is a submodular set function, edges no longer have a fixed weight. This is handled by Feldman and Ward [13] by processing edges in order of decreasing marginal contribution with respect to the algorithm’s current solution. They further maintain an ordering \(\prec\) of the ground set to define auxiliary weights of edges in the algorithm’s solution. In the method of [13], the marginal contribution of an edge can only decrease over time since the solution is built greedily. However, our algorithm does not have this property, as edges can enter, exit, and reenter our solution over time. For this reason, we maintain an ordered set \((X, \prec)\) of edges that were taken into the solution at any iteration of our algorithm. We then evaluate the marginal contribution of an edge with respect to \(X\), a superset of all the current solution. A local \(\alpha\)-swap is then defined by comparing the auxiliary weight of the added and discarded edges.

1.2.0.3 Weighted \(k\)-Set Packing.

In the special variant of weighted \(k\)-set packing, we go beyond \(k/2\) and obtain a \(\frac{\ln(4)k}{3}\)-approximation. To obtain this approximation, we combine the algorithm of [11] with our \(\alpha\)-local search as follows: we construct a random partitioning of edges into weight buckets as in [11], then we process the weight buckets in decreasing weight order, applying the state-of-the-art \(k/3\)-approximation algorithm [18]. However, before processing the next weight bucket, we run our \(\alpha\)-local search over the entire instance restricted to the weight buckets processed so far. This additional \(\alpha\)-local search step removes inherent flaws in the greedy processing of weight buckets, wherein higher weight edges can block up to \(k\)-many optimal edges of slightly lower weight. However, the weight bucketing also guarantees that the approximation goes beyond \(k/2\) by interpolating with the \(k/3\)-guarantee of running the unweighted algorithm.

1.3 Paper Organization↩︎

The rest of the paper is organized as follows. In 2 we give necessary notations and definitions regarding matroids and submodular functions. In 3 we define the \((\theta, \alpha)\)-Local Search algorithm and our main submodular maximization algorithm, which iteratively runs \((\theta, \alpha)\)-Local Search over decreasing \(\theta\). In 4 and 5 we give preliminaries for the analysis of our submodular maximization algorithm by constructing the necessary matroid exchanges with respect to \(\opt\). In 6 we complete the algorithm analysis aggregating the matroid exchanges into approximation guarantees with respect to the final output. In 7 we define the extended algorithm for weighted \(k\)-Set Packing and analyze it.

2 Preliminaries↩︎

For any integer \(k \in \NN\), we use the convention \([k] \triangleq \{1, \ldots, k\}\). We assume that the reader is familiar with basic matroid definitions (see [28] for a good survey). We introduce the combinatorial constraints that we study in this paper.

2.0.0.1 Matroid \(k\)-parity:

We are given a hypergraph \(G = (V, E)\) on a set of vertices \(V\) and a matroid \(\cM = (V, \cI)\) defined on \(V\). Each hyperedge \(e \in E\) has contains up to \(k\) vertices. Given a set function \(f\colon 2^E \to \mathbb{R}\), the goal is to find a maximum value collection of disjoint hyperedges \(M \subseteq E\) such that the vertices incident to \(M\) are independent in \(\cI\). For any collection of hyperedges \(S \subseteq E\), we say \(S \in \mathcal{I}\) if \(v(S) \in \mathcal{I}\), i.e. the vertices covered by the hyperedges are independent. As shown by Lee, Sviridenko and Vondrák, we may assume that the hyperedges are disjoint (modifying \(\cM\)) [10].

2.0.0.2 \(k\)-Set Packing and \(k\)-Matroid Intersection:

\(k\)-Set Packing is a special case of Matroid \(k\)-Parity, where \(\cM\) is the free matroid (\(\cI = 2^V\)). Matroid \(k\)-Parity also generalizes \(k\)-Matroid Intersection which consists of finding a maximum value independent set in \(k\) matroids \((E, \cI_1), \ldots, (E, \cI_k)\). The reduction to Matroid \(k\)-parity is standard by creating \(k\) copies \((e, i)_{i \in [k]}\) for each \(e \in E\) with a unique hyperedge incident to these \(k\) copies, and defining a set \(S\) independent in \(\cM\) if \(\{e \in E \colon (e, i) \in S\} \in \cI_i\) for all \(i \in [k]\).

2.0.0.3 Set functions:

We let \(f: 2^E \rightarrow \mathbb{R}\) be a function that assigns a value to every subset of \(E\). Given a set \(S\) and an element \(e\), we define the marginal contribution of \(e\) with respect to \(S\) as \(f(e \mid S) \triangleq f(S \cup \{ e \}) - f(S)\). Similarly, given a set \(T \subseteq E\), we denote by \(f(T \mid S) \triangleq f(S \cup T) - f(S)\) the marginal contribution of \(T\) to \(S\). A set function \(f\) is monotone if \(f(e \mid S) \geq 0\) for every set \(S \subseteq E\) and element \(e \in E\). A set function \(f\) is called submodular if \(f(e \mid S) \geq 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\) w.r.t. \(S\) can diminish when additional elements are added to the set \(S\). A special case of monotone submodular functions is when each element \(e \in E\) is assigned a weight \(w_e \geq 0\) and \(f(S) = \sum_{e \in S} w_e\) for all \(S \subseteq E\), and \(f(\emptyset) = 0\). In this case, we say that \(f\) is linear. Our algorithms optimize a submodular set function \(f\) over a constraint involving matroids. Since both \(f\) and \(\cM\) may have an exponential size description, we make the standard assumption that \(f\) is accessed through a value oracle that given a set \(S \subseteq E\) returns \(f(S)\), and that \(\cM\) is accessed via a independence oracle that given \(S \subseteq E\) returns yes if \(v(S) \in \Ical\).
Other Notations: We denote by \(W \triangleq \max_{e \in E\colon e\in \cI} f(e)\) the maximum weight of any feasible edge and denote an interval by \(I \subseteq [0, W]\). Additionally, given a collection of sets \(\{R_i\}_{i = 1}^{L}\), we will denote \(R_{\leq i} = \bigcup_{j = 1}^{i} R_j\), and \(R_{\geq i} = \bigcup_{j = i}^{L} R_j\).

3 Main Algorithm↩︎

We introduce our main algorithm for maximizing a monotone submodular function subject to a matroid \(k\)-parity constraint, described in 2. It uses as a subroutine a local-search algorithm (1) parametrized by two values \(\alpha\), and \(\theta\). The parameter \(\alpha\) ensures that the ratio of value of edges added to value of edges removed in the solution is at least \(\alpha\). The parameter \(\theta\) restricts the local search to edges whose marginal value is at least \(\theta\). 1 starts by applying this subroutine with threshold \(\theta = W\). The threshold is then decreased continuously while making \(\alpha\)-improving swaps whenever one can be made.

3.1 Defining the \(\alpha\)-Local Search Subroutine↩︎

To define this algorithm, we introduce the incremental value of an edge and an ordering \(\prec\) of the edges of \(E\). This notion has appeared for example in [13], [27], [29] as a way to run local search methods over submodular objectives.

2 maintains an ordering \(\prec\) that is updated over time on a set \(X \subseteq E\) of edges that were inserted by any prior local search swap, including those that were subsequently removed. The ordering over \(E\) is initially empty, and whenever an edge \(e \in E\) is inserted in a local search swap, it is placed into the ordering \(\prec\) at the end of the ordering (at the end of the queue). In particular, even if \(e\) was already ordered by a prior iteration, if \(e\) reenters the solution it is placed at the end of \(\prec\). Edges will be inserted via \((\theta, \alpha)\)-local swaps described below.

This defines a swap where we add a set \(S\) of edges with individual marginal value at least \(\theta\) and where \(f(S \mid X - S)\) is at least \(\alpha\)-times larger than the incremental values of the discarded edges in order to add in \(S\).

3.2 Defining Ordered \(\alpha\)-Local Search↩︎

The conceptual idea behind our main algorithm, \(\mathrm{\small Ordered \alpha-Local }\mathrm{\small Search}\) is to run \((\theta, \alpha)\)-\(\LS\) in order of decreasing \(\theta\). The local-search algorithm runs continuously while the threshold \(\theta\) is decreased over time, thereby allowing lower-value edges to become eligible. Formally, \(\mathrm{\small Ordered \alpha-Local }\mathrm{\small Search}\) (2) uses \((\theta, \alpha)\)-\(\LS\) to find all \((\theta, \alpha)\)-improving swaps. When none can be found, the threshold \(\theta\) is decreased to include the next eligible edge. We decrease the threshold by looking at the lowest marginal of any edge in an ordered \(k\)-tuple. If \((A, X)\) is the state of the algorithm, this is defined for \(S \subseteq E \setminus A\) as \(\Delta_{S} \triangleq \min_{\sigma \in \mathbb{S}_{|S|}} \min_{j \in [|S|]} f(s_{\sigma(j)} \mid X - \{s_{\sigma(j)}\} + \{s_{\sigma(1)}, \ldots, s_{\sigma(j-1)}\})\), where \(\mathbb{S}_{\ell}\) is the set of all permutations of size \(\ell\). We truncate the algorithm by running only until \(\theta \geq \bar\theta\triangleq \delta W/|E|\) such that it halts in polynomial time. A standard polynomial run time analysis is shown in Appendix 10.

4 Preliminaries for the Analysis of 2↩︎

To analyze 2, we will let \(O\) be an optimal matroid \(k\)-parity solution. Let \(\bar\theta\triangleq \delta \cdot \frac{W}{|E|}\) be the termination threshold. Let \(W = \theta_1 > \ldots > \theta_L > 0\) be the finitely many \(\theta \in [0, W]\) such that \((\theta, \alpha)\)-\(\LS\) is called by 2. For every \(i \in [1, L]\) and any \(\tau \in [\theta_{i+1}, \theta_i]\), we let \((A_\tau, X_\tau) = (A_{\theta_i}, X_{\theta_i})\) where \(\theta_{L+1} = 0\).

Let the final output of 2 be denoted by \(A \triangleq A_0 = A_{\theta_L}\). We want to compare the value of \(f(A)\) to \(f(O)\). To do this, we define a set \(O_\theta\) containing the edges of \(O\) of value at least \(\theta\). The value of an element of \(O\) is defined by an auxiliary weight \({\bar{w}}\).

4.1 Partitioning the Edges of \(O\) by Value↩︎

Similarly to [13], we let \(O \triangleq \{o_1, \ldots, o_{|O|}\}\) be an arbitrary ordering of \(O\). The set of optimal edges that appeared prior to \(o_\ell\) in the ordering is denoted by \(O^{-}_{o_\ell}\). This ordering can be different from the one computed by 2. For every \(\theta \in [0, W]\), we define an auxiliary weight at time \(\theta\) for each \(o \in O\). This auxiliary weight is only useful for the analysis and is not computed by the algorithm. For any \(o \in O\), we define \[\begin{align} {\bar{w}}_\theta(o) \triangleq f(o \mid X_\theta - \{o\} \cup O^{-}_o). \end{align}\] This is the marginal contribution of \(o\) with respect to the set of accepted edges up until marginal \(\theta\) in the algorithm, as well as the optimal edges prior to \(o\) in the ordering. Using submodularity, it is easy to see that \({\bar{w}}_\theta(o)\) is increasing in \(\theta\) for any fixed \(o \in O\). This is since \(X_{\theta} \subseteq X_{\gamma}\) for any \(\theta \geq \gamma\).

We partition \(O\) according to these auxiliary weights. Starting at \(\theta = W\) and then decreasing \(\theta\) to \(0\), we define recursively: \[\begin{align} O_\theta & \triangleq \lc o \in O \mathbin{\big\backslash} \lb\bigcup_{\theta' >\theta} O_{\theta'}\rb \colon {\bar{w}}_\beta(o) \geq \betafor all\beta \in [0, \theta] \rc. \label{eq:definition-Oi} \end{align}\tag{1}\] In particular, the auxiliary weight of any \(o \in O_\theta\) satisfies \({\bar{w}}_{\theta'}(o) \geq \theta'\) for all \(\theta' \leq \theta\). For simplicity, we define \(O_{\geq \theta} \triangleq \bigcup_{\theta' \geq \theta} O_{\theta'}\).

4.2 Properties of Incremental Values↩︎

We first show using submodularity that the \(\prec\)-incremental value satisfies certain nice behaviors, which will help analyze 2.

The following statement is then a simple consequence of [lem:properties-incremental]

5 Building Matroid Exchanges↩︎

We analyze the quality of the algorithm’s solution by constructing non-improving local swaps between the intermediary solution \(A_\tau\) for any \(\tau \in [\bar\theta, W]\) and the optimal solution \(O\). The information carried by the local swaps is represented by a conflict graph between \(O\) and \(A_\tau\). This graph has the following properties.

[thm:decomposition-ith-round-2] partitions the optimal solution \(O\) and \(v(A_\tau)\) into a collection of valid matroid swaps ([item:decomp-swap-2]). It also gives further properties for the swaps involving edges of \(O_{\geq \tau}\) using the absence of \((\tau, \alpha)\)-improving swaps with respect to \(A_\tau\). In particular, it bounds the auxiliary weight of edges \(o \in O_{\geq \tau}\) incident to a fixed edge of \(A_\tau\) ([item:decomp-single-2]). These swaps will be defined by repeatedly applying matroid basis exchanges ([thm:Rota-setminus], [thm:Rota-non-basis-2] in the appendix). The proof of this theorem follows that of [11] but adapts it to find larger exchanges up to size \(k\) instead of size \(2\). The proof is in 9.

6 Approximation Guarantee of 2↩︎

We are now ready to compute the approximation guarantee of our algorithm restated here.

The proof follows a standard strategy by bounding the marginal contribution of edges of \(O\) with respect to their conflicting neighbors in \(A\), and aggregating the bounds together. Observe that \(X_0 = X_{\bar\theta}\) are the edges that were ever inserted by a swap in 2. The analysis will consider separately the edges of \(X_0\setminus A\) that appear throughout the algorithm but get removed in favor of improving swaps, and the remaining edges \(A\).

6.1 Decomposition of the value of \(O\) into cardinality bounds↩︎

In this section, we express the value of \(O\) by decomposing it according to the number of edges with the same auxiliary weight for each weight \(\tau \in [0, W]\). To do this, for any \(o \in O\), let \(\tau \in [0, W]\) be the unique value such that \(o \in O_\tau\) ([claim:marg-O95i]). In particular, we have \({\bar{w}}_\tau(o) = \tau\) for any \(o \in O\) by [claim:marg-O95i]. Then, \({\bar{w}}_\tau(o) = \int_{0}^\tau 1 dy\).

We then use the bipartite conflict-graph from [thm:decomposition-ith-round-2] to bound the size of \(|O_{\geq \tau}|\) with respect to \(|A_\tau|\) for any \(\tau \in [\bar\theta, W]\).

This statement follows a simple counting argument. Each \(o \in O_{\geq \tau}\) has degree at least \(1\) in the bipartite graph \(G\) given in [thm:decomposition-ith-round-2] (i.e. at least one matroid-conflict). We obtain the result by splitting \(O_{\geq \tau}\) into vertices with degree \(1\) or more than \(2\), using that every \(a \in A_\tau\) has degree at most \(k\), and that there are not too many vertices of degree \(1\).

6.2 Contribution of Appearances↩︎

We would now like to integrate the inequality of [lem:size-O95i] over \(\tau \in [\bar\theta, W]\) to obtain a guarantee in terms of the value of the final solution. We will split the analysis into the edges of \(A_\tau\) which appear in the final solution \(A\) and all occurrences of edges that get removed throughout the process. For this purpose, we need to define appearances for every edge in \(X_0\). Recall that \(X_0\) is the set of all edges that ever entered the solution throughout the execution of 2.

Informally, an appearance is a continuous interval during which an edge stays within the solution. An edge may have multiple appearances.

Note that every evicted appearance of some \(a \in X_0\) must be part of some \((\theta, \alpha)\)-swap \((S, N)\) where \(a \in N\) removes \(a\) from the solution. We will aggregate over all such swaps to bound the contribution of the evictions. Towards this end, let \(T\) be the total number of \((\theta, \alpha)\)-swaps performed by 2 (over all \(\theta\)). Let \(A^{(1)} = \emptyset\) be the initial solution and \(A^{(t)}\) be the solution just prior to performing the \(\nth{t}\) exchange for \(t \in [T]\), where \(N_t\) is discarded and \(S_t\) is added. Let \(\prec_{t}\) be the order over edges \(A^{(t)}\) in the solution prior to the \(\nth{t}\) swap. Let \(A^{(T+1)} = A\) be the final output of 2 after the \(\nth{T}\) swap.

The following lemma bounds the effect of evicted appearances compared to the value of the final solution. In particular, we prove that the value of evicted edges is small compared to the weight of the final solution.

It remains to show that we can integrate the right hand side of [lem:size-O95i] and express the value as a function of evicted appearances.

6.3 Contribution of Singles↩︎

Recall that the second term on the right-hand side of [lem:size-O95i] comes from summing over the single conflict edges \(O_s\). We proceed similarly to bound the total value by integrating this term over all \(\tau\) and we show that this term contributes an \(o(k)\) value of \(f(A)\).

6.4 Putting Guarantees Together to Prove [thm:main-approximation-guarantee]↩︎

As a corollary of the previous computations, we directly obtain a bound on the marginal contribution of \(O\) with respect to \(X_0\) by combining [lem:decomp-opt-value] together with [lem:size-O95i], [lem:doubles-occurences], and [lem:single-occurences].

Observe that [cor:marg-OPT-wrt-X0] only bounds \(f(O \mid X_0)\) and not \(f(O \mid A)\). The next lemma shows that \(f(X_0)\) is close to \(f(A)\).

We can now state the guarantees of 2 precisely.

Setting \(\alpha\) appropriately, we obtain the claimed asymptotic guarantee.

The calculations that conclude [cor:approx-num] are given in Appendix 11.

7 An improved approximation for set packing via hybrid \(\alpha\)-local search and unweighted local search↩︎

The weighted \(k\)-set packing problem is a subproblem of weighted matroid \(k\)-parity, in which the underlying matroid is free, i.e., \(\cM = 2^V\). In particular, the goal is simply to find a maximum weight collection of disjoint edges, each of which contains up to \(k\) vertices. We denote by \(w:E \rightarrow \mathbb{R}_{\geq 0}\) the weight function. For any two sets of edges \(A, O \subseteq E\), we define the neighborhood of \(O\) in \(A\) as \(N(O, A) \triangleq \{ a \in A \colon a \cap O \neq \emptyset\}\) as the set of edges in \(A\) with common vertices with \(O\). The set of vertices covered by both hyperedges of \(A\) and \(O\) in is denoted by \(N_v(O,A) \triangleq \{v(O) \cap v(A)\}\). We also define a weight function over the vertices of the set packing instance.

7.1 Main Algorithm↩︎

We obtain a \(\frac{\ln(4) k}{3} + o(k)\)-approximation algorithm for weighted \(k\)-Set Packing by combining the \(\alpha\)-local search algorithm and the algorithm of Singer and Thiery [11]. The algorithm of [11] creates a random partitioning of the instance into weight classes defined by a random parameter \(\tau\). The algorithm processes the weight classes greedily and runs the state-of-the-art unweighted algorithm on each weight class. Further details can be found in [11], [13]. Our algorithm repeats this strategy, but after processing the \(\nth{i}\) weight class, it continues to search for improving \(\alpha\)-swaps over all the edges up to the \(\nth{i}\) weight class. In particular, in contrast to the method outlined in [11], [13], we do not contract the instance at each iteration but rather continue to search for \(\alpha\) improvements over the increasingly larger instance. It is worth noting that to apply the state-of-the-art unweighted algorithm [18], we treat each weight class as completely unweighted (3).

7.1.0.1 Interval Local Search:

Given a feasible solution \(A\), 3 applies Cygan’s algorithm [18] on an interval \(I\). It does so by defining a subinstance over all edges with \(w_e \in I\) which are unblocked by the current solution \(A\). The algorithm of [18] runs with a precision parameter \(\e\) which also affects the run time. We will choose \(\e\) to be an arbitrarily small constant.

7.1.0.2 Hybrid Local Search:

4 is our main algorithm which uses 3 and 1 as subroutines. For clarity, we restate the definition of \((\theta, \alpha)\)-improving swaps for the weighted setting where these swaps are modified for to run over elements of weight strictly greater than \(\theta\).

To see that 4 runs in polynomial time in \(|E|, \e\), we note that we only process the intervals that contain at least one element of the ground set, so that there are at most \(|E|\) many intervals and therefore iterations of \(\mathrm{\small Interval } \LS\) and \((m_{i+1}, \alpha)\)-\(\LS\). In Appendix 10 we argue that \((m_{i+1}, \alpha)\)-\(\LS\) runs in polynomial time in \(|E|\) for constant \(k\). \(\mathrm{\small Interval } \LS\) runs the algorithm of [18] on precision \(\e\) which runs in polynomial time in \(|E|\) for any choice of constant \(\e\).

7.2 Analysis of 4↩︎

Our main theorem states that 4 gives an improved approximation for \(k\)-Set Packing.

This improves over Neuwohner’s \(\frac{k}{2.00561} + O(1)\)-approximation algorithm without relying on the use of the \(w^2\)-algorithm of Berman [21].
To prove the above theorem, we define a partition of the elements of \(O \cap (m_{i+1}, m_i]\) right after the termination of \(A_i \leftarrow \mathrm{\small Interval} \LS((m_{i+1}, m_i])\). It indicates whether the neighborhood of an optimal edge contains 1, 2, or more than 3 vertices in \(A_i\) (i.e. single, double or triple conflicts). The proof splits the analysis into neighbors present in final output and those removed. The idea is that, on each interval, Cygan’s analysis of \(\mathrm{\small Interval } \LS\) [18] proves that the majority of \(O\), except an \(o(k)\)-fraction, have \(3\) vertex conflict. They behave roughly as a \(k/3\) approximation. The neighbors that get removed account for a \(\alpha\) factor weight increase of the current solution. Putting all of these influences together yields the improved approximation guarantee.

7.2.1 Partitioning of the optimal solution↩︎

For each \(i \in \mathcal{J}\), let \(I_i = (m_{i+1}, m_i]\) denote the \(\nth{i}\) weight bucket. Throughout the rest of proof, we denote by \(A_i\) the algorithm’s solution right after \(\mathrm{\small Interval } \LS(A, (m_{i+1}, m_{i}])\). Similarly, we let \(A'_i\) be the algorithm’s solution right after \((m_{i+1}, \alpha)\)-\(\LS(A)\). Let \(L\) be the last index in \(\mathcal{J}\). The final output of 4 is equivalently denoted by \(A_{L+1}\) and \(A'_L\). Finally, let \(O_i \triangleq O \cap I_i\) be the optimal edges in the \(\nth{i}\) weight bucket. Next, we define the edges of \(O^{\textrm{rem}}\subseteq O\) whose neighborhood gets removed. We say an edge \(e\) is evicted in round \(j\) if we have that \(e \in N\) for some \((m_j, \alpha)\)-swap \((S,N)\). We denote by \(R\) the set of all evicted elements. Then, we define

• Let \(O^{\textrm{rem}}_i \triangleq \{ o \in O_i : \exists a \in N(o, A_i)\cup N(o, A'_i) \text{ that is evicted at some round }j \geq i\}.\)

• Let \(O^{\textrm{rem}}\triangleq \displaystyle\bigcup_{i \in \mathcal{J}} O^{\textrm{rem}}_i\).

We are then left with the edges of \(O\) whose neighborhood is contained in all iterations up to the final solution \(A_{L+1}\). Notice that for \(o \in O_i\setminus O^{\textrm{rem}}_i\), \(N(o, A_i) \subseteq N(o, A'_i)\) as we assume the neighborhood is not evicted in round \(i\) itself. For these edges, we will split the analysis into singles, doubles, and triples. For each \(i \in \mathcal{J}\), these sets are defined as:

• \(S_i\triangleq \{ o \in O_i\setminus O^{\textrm{rem}}_i \colon \card{N_v(o, A_i)} = 1, c(N_v(o, A_i)) \leq 3 w_o\}\) be the set of singles in \(O_i\) w.r.t \(A_i\) whose neighbor is of similar weight.

• \(D_i \triangleq \{ o \in O_i\setminus O^{\textrm{rem}}_i \colon \card{N_v(o, A_i)} = 2 , c(N_v(o, A_i)) \leq 3 w_o\}\) be the set of doubles in \(O_i\) w.r.t \(A_i\) whose neighbors are of similar weight.

• \(T_i \triangleq \{ o \in O_i\setminus O^{\textrm{rem}}_i \colon \card{N_v(o, A_i)} \geq 3 \} \cup \{ o \in O_i \setminus O^{\textrm{rem}}_i \colon \card{N_v(o, A_i)} \leq 2, c(N_v(o, A_i)) > 3 w_o\}\) be the set of triples in \(O_i\) w.r.t \(A_i\) as well as items with very large weighted neighbors.

The same set names without the subscript \(i\) correspond to the union over all intervals \(i \in \mathcal{J}\), i.e. \(T =\bigcup_{i \in \mathcal{J}} T_i\). In the next part of the proof, we show that \(O^{\textrm{rem}}\) is only \(o(k)\)-larger than our final solution \(A_{L+1}\) for a large choice of \(\alpha\).

7.2.2 Negligible contribution of the edges with removed neighborhoods↩︎

Let \(R\) be the set of all evicted edges in \(\bigcup_{i}A_i \cup \bigcup_i A'_i\), i.e. \(R = \{a \in \bigcup_{i}A_i \cup \bigcup_i A'_i: a \notin A_{L+1}\}\).. Observe that edges can only exit the solution when calling \((m_{i}, \alpha)\)-\(\LS\) for some \(i\). Indeed, in any round \(i \in \mathcal{J}\), we execute Interval \((A, (m_{i+1}, m_i])\) and the interval \((m_{i+1}, m_i]\) is a new, unprocessed interval such that Interval \((A, (m_{i+1}, m_i])\) only adds elements into the current solution. Thus \(A'_{i-1} \subseteq A_i\) where we denote by \(A'_{i-1}\) as the solution just prior to processing index \(i \in \Jcal\). Similarly to the analysis for matroid \(k\)-parity, we bound the contribution of edges that are evicted throughout the algorithm in favor of improving swaps. We use the following lemma over the weight of the evicted edges.

The next lemma shows that, assuming \(\alpha = \Omega({1})\), the weight of \(O^{\textrm{rem}}\) is negligible (an \(o(k)\)-factor) compared to the weight of the final solution.

It is worth noting that [lem:removed-setpack] distinctly works for a \(k\)-set packing instance as opposed to a general matroid \(k\)-parity. This is because any \(o \in O^{\textrm{rem}}\) can only conflict with distinct vertices over all time steps, whereas matroid exchanges per time step do not guarantee this property.

7.2.3 Negligible contribution of singles↩︎

The next lemma shows that \(A_{L+1}\) is a good approximation for the subset of the singles \(S\) that are still singles after \(\alpha\)-\(\LS\) is performed. To show this, we further partition the sets \(S_i\) for each \(i \in \mathcal{J}\) as follows:

1. \(S^{\textrm{near}}_i \triangleq \{ o \in S_i: N(o, A_i) \subseteq (m_{i+1}, m_i]\}\).

2. \(S^{\textrm{far-stable}}_i \triangleq \{ o \in S_i: N(o, A_i) \not\subseteq (m_{i+1}, m_i], N(o, A_i) = N(o, A'_i)\}\).

3. \(S^{\textrm{far-unstable}}_i \triangleq \{ o \in S_i: N(o, A_i) \not\subseteq (m_{i+1}, m_i], N(o, A_i) \neq N(o, A'_i)\}\).

We first show that \(A_{L+1}\) is a \(o(k)\) approximation relative to \(S^{\textrm{near}}\cup S^{\textrm{far-stable}}\). We will then defer the analysis over \(S^{\textrm{far-unstable}}\) to Section 7.2.5.

7.2.4 Analyzing the contribution of doubles↩︎

We show that \(A_{L+1}\) has a good approximation guarantee relative to the set of doubles \(D\). As in the previous part, we separate the analysis into opt-edges whose neighborhood is within their own weight class and those that contain a neighbor in a prior class. The key is that the former case can be analyzed via an unweighted analysis akin to [18], while the latter can be analyzed according to the random weight bucketing argument from [11]. We therefore split \(D_i\) into two different sets as follows:

1. Let \(D^{\textrm{near}}_i \triangleq \{o \in D_i : N(o, A_i) \subseteq (m_{i+1}, m_i]\}\).

2. Let \(D^{\textrm{far}}_i \triangleq \{o \in D_i: N(o, A_i) \not\subseteq (m_{i+1}, m_i]\}\).

We first show that \(A_{L+1}\) is an \(O(1)\) approximation relative to \(D^{\textrm{near}}\).

7.2.5 Approximation guarantee of \(T\), \(D^{\textrm{far}}\), and \(S^{\textrm{far-unstable}}\)↩︎

Finally, it remains to analyze the triples \(T\), the doubles in \(D^{\textrm{far}}\) that contain a neighbor in a prior interval, and the singles in \(S^{\textrm{far-unstable}}\) whose neighborhood changes during \(\alpha\)-\(\LS\). For each \(o \in T \cup D^{\textrm{far}}\cup S^{\textrm{far-unstable}}\), we denote by \(m_o\) the closest marker to \(w_o\) such that \(m_o \geq w_o\). The contribution of these edges depends on the distance between \(w_o\) and \(m_o\) which can be computed directly from the distribution \(\tau\). Towards this end, for every \(o \in O\) we define the ratio of the item’s weight to its nearest marker as \(r_o \triangleq \frac{m_o}{w_o}\). Intuitively, the larger the ratio is, the better the approximation. As shown in the next lemma, the guarantees directly depend on \(r_o\).

Note that for every \(o \in O\), \(r_o\) is a random value as it depends on the outcome \(\tau\) which determines the markers \(m_0, \ldots, m_{L+1}\). We would like most elements to have a large ratio \(r_o\) as this guarantees that the factor difference in weight to its neighborhood accounts for a large multiplicative improvement. This fact directly follows from Feldman and Ward [13].

Combining [lem:32prob32of32Rj] and [lem:improved-gap-triples], we bound the value of \(D^{\textrm{near}}\cup T \cup S^{\textrm{far-unstable}}\) relative to \(A_{L+1}\).

7.2.6 Putting the pieces together↩︎

We are now able to conclude our main theorem which shows that for a choice of \(\alpha\) an arbitrarily large constant, 4 improves over Neuwohner’s \(\frac{k}{2.0056} + O(1)\)-approximation algorithm.

8 Conclusion and Open Questions↩︎

The main contribution of this paper is a new, arguably simple algorithm for monotone submodular maximization over a matroid \(k\)-parity constraint. It applies a local-search procedure to edges of weights above some threshold, which is decreased continuously, so that smaller value edges are taken in favor of large value edges only if they improve the solution greatly. The guarantee of our algorithm asymptotically matches that of the state-of-the-art algorithm in the unweighted setting. We obtain a \(\frac{k}{2} + o(k)\)-approximation for monotone submodular maximization subject to a matroid \(k\)-parity constraint. This improves over the \(\frac{\ln(4)k}{1 + \ln(2)} + o(k)\)-approximation by Feldman and Ward in the same setting, and approaches, albeit an additive \(o(k)\)-loss, the \(\frac{k}{2} + \e\)-approximation guarantee by Lee, Sviridenko, and Vondrák in the unweighted setting. We use this algorithm in the special case of weighted \(k\)-Set Packing. We show that a combination of our algorithm and that of Singer and Thiery [11] allows us to obtain a \(\frac{\ln(4)k}{3}+o(k)\)-approximation. This improves over the prior state of the art \(\frac{k}{2.00561}+O(1)\)-approximation algorithm [25].
Our work leaves some interesting open questions to explore. Our results demonstrate that it might be easier to obtain improved guarantees for large values of \(k\). Can one also obtain a \(k/3 + o(k)\)-approximation for weighted \(k\)-Set Packing to match the unweighted guarantee? Another natural promising avenue is to understand low values of \(k\). For (weighted) \(3\)-matroid intersection, the state-of-the-art approximation guarantee is \(2\) (due to a \(k-1\) approximation for all \(k\)) by Lee et al. [12]. For \(3\)-Set Packing, this bound can be surpassed [23], [30], [30] but is still far from the \(3/2\) approximation in the unweighted setting, which is a natural barrier. Improving on either of these results would be very interesting. Finally, we ask whether there are black-box reductions from the weighted to unweighted setting as done recently in other computational models over matching and matroid intersection (see e.g. [31]–[33]).

Acknowledgements↩︎

We thank Neil Olver who participated in many of the discussions and progress that led up to and inspired the present algorithm.

Tool and Computational Resource Disclosure↩︎

All the core ideas in this paper, including the algorithms and the proof strategies, were developed without the use of Large Language Models. Chat-GPT was used to obtain a simplification of a complex case-by-case analysis that the authors originally employed. This simplification was adapted into [lem:single-occurences], which was independently extended and verified by the authors. All writing was done by the authors.

9 Matroid Exchanges↩︎

We analyze the quality of the algorithm’s solution by constructing non-improving local swaps between the intermediary solution \(A_\tau\) for any \(\tau \in [\bar\theta, W]\) and the optimal solution \(O\). It will be helpful to define matroid exchanges over the vertices covered by solutions \(A_\tau\) and \(O\), before constructing feasible swaps between hyperedges of \(A_\tau\) and \(O\).

The set \(B\) should be thought of as the set of vertices in \(v(O)\) that are conflicting with \(A_\tau\).

We also restate known results about matroid-basis exchanges

9.1 Constructing a Conflict Graph↩︎

We use the above matroid exchanges to construct a bipartite conflict graph between \(O_{\geq \tau}\) to \(A_\tau\). The conflict graph is comprised of feasible hyperedge swaps between \(O_{\geq \tau}\) to \(A_\tau\) and therefore satisfies local swap guarantees. We restate the lemma here.

10 Polynomial Runtime↩︎

We prove that 2 runs in polynomial time. Each iteration of our algorithm requires finding a \((\theta_i, \alpha)\)-improvement, where \(\alpha > 1\).

11 Approximation Guarantee Calculations↩︎

We prove the calculations that give final approximation guarantee restated here.

References↩︎

---

1. Ecole Polytechnique Fédérale de Lausanne (Email: neta.singer@epfl.ch)↩︎

2. Department of Computer Science, ETH Zurich, Zurich, (Email: theophile.thiery@inf.ethz.ch)↩︎