For any 𝜀 > 0, we prove that 𝑘-Dimensional Matching is hard to approximate within a factor of 𝑘/(12+𝜀) for large 𝑘 unless NP ⊆ BPP. Listed in Karp’s 21 NP-complete problems, 𝑘-Dimensional Matching is a benchmark computational complexity problem which we find as a special case of many constrained optimization problems over independence systems including: 𝑘-Set Packing, 𝑘-Matroid Intersection, and Matroid 𝑘-Parity. For all the aforementioned problems, the best-known lower bound was a Ω(𝑘/log(𝑘))-hardness by Hazan, Safra, and Schwartz. In contrast, state-of-the-art algorithms achieve an approximation of 𝑂(𝑘). Our result narrows down this gap to a constant and thus provides a rationale for the observed algorithmic difficulties. The crux of our result hinges on a novel approximation preserving gadget from 𝑅-degree bounded 𝑘-CSPs over alphabet size 𝑅 to 𝑘𝑅-Dimensional Matching. Along the way, we prove that 𝑅-degree bounded 𝑘-CSPs over alphabet size 𝑅 are hard to approximate within a factor Ω𝑘 (𝑅) using known randomised sparsification methods for CSPs.

We consider the problem of finding an independent set of maximum weight simultaneously contained in k matroids over a common ground set. This k-matroid intersection problem appears naturally in many contexts, for example in generalizing graph and hypergraph matching problems. In this paper, we provide a (k+1)/(2 ln2)-approximation algorithm for the weighted k-matroid intersection problem. This is the first improvement over the longstanding (k−1)-guarantee of Lee, Sviridenko and Vondrák (2009). Along the way, we also give the first improvement over greedy for the more general weighted matroid k-parity problem. Our key innovation lies in a randomized reduction in which we solve almost unweighted instances iteratively. This perspective allows us to use insights from the unweighted problem for which Lee, Sviridenko, and Vondrák have designed a k/2-approximation algorithm. We analyze this procedure by constructing refined matroid exchanges and leveraging randomness to avoid bad local minima.

We consider the weighted k-set packing problem, in which we are given a collection of weighted sets, each with at most k elements and must return a collection of pairwise disjoint sets with maximum total weight. For k = 3, this problem generalizes the classical 3-dimensional matching problem listed as one of the Karp's original 21 NP-complete problems. We give an algorithm attaining an approximation factor of 1.786 for 3-set packing, improving on the recent best result of due to Neuwohner.

We study the following problem: Given a variable of interest, we would like to find a best linear predictor for it by choosing a subset of k relevant variables obeying a matroid constraint. This problem is a natural generalization of subset selection problems where it is necessary to spread observations amongst multiple different classes. We derive new, strengthened guarantees for this problem by improving the analysis of the residual random greedy algorithm and by developing a novel distorted local-search algorithm. To quantify our approximation guarantees, we refine the definition of weak submodularity by Das and Kempe (2011) and introduce the notion of an upper submodularity ratio, which we connect to the minimum k-sparse eigenvalue of the covariance matrix. More generally, we look at the problem of maximizing a set function f with lower and upper submodularity ratio $\gamma$ and $\beta$ under a matroid constraint. For this problem, our algorithms have asymptotic approximation guarantee 1/2 and (1 - 1/e) as the function is closer to being submodular. As a second application, we show that the Bayesian A-optimal design objective falls into our framework, leading to new guarantees for this problem as well.

We give improved multi-pass streaming algorithms for the problem of maximizing a monotone or arbitrary non-negative submodular function subject to a general p-matchoid constraint in the model in which elements of the ground set arrive one at a time in a stream. The family of constraints we consider generalizes both the intersection of p arbitrary matroid constraints and p-uniform hypergraph matching. For monotone submodular functions, our algorithm attains a guarantee of p+1+ε using O(p/ε)-passes and requires storing only O(k) elements, where k is the maximum size of feasible solution. This immediately gives an O(1/ε)-pass (2+ε)-approximation for monotone submodular maximization in a matroid and (3+ε)-approximation for monotone submodular matching. Our algorithm is oblivious to the choice ε and can be stopped after any number of passes, delivering the appropriate guarantee. We extend our techniques to obtain the first multi-pass streaming algorithms for general, non-negative submodular functions subject to a p-matchoid constraint. We show that a randomized O(p/ε)-pass algorithm storing O(p³klog(k)/ε³) elements gives a (p+1+γ+O(ε))-approximation, where γ is the guarantee of the best-known offline algorithm for the same problem.