Theophile Thiery

STOC Conference 2025 Conference Paper

Asymptotically Optimal Hardness for k-Set Packing and k-Matroid Intersection

• Euiwoong Lee
• Ola Svensson
• Theophile Thiery

STOC Conference 2025 Conference Paper

Better Approximation for Weighted k-Matroid Intersection

• Neta Singer
• Theophile Thiery

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.

SODA Conference 2023 Conference Paper

An Improved Approximation for Maximum Weighted k -Set Packing

• Theophile Thiery
• Justin Ward

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. Our algorithm is based on the local search procedure of Berman that attempts to improve the sum of squared weights rather than the problem's objective. When using exchanges of size at most k, this algorithm attains an approximation factor of. Using exchanges of size k 2 ( k -1) + k, we provide a relatively simple analysis to obtain an approximation factor of 1. 811 when k = 3. We then show that the tools we develop can be adapted to larger exchanges of size 2 k 2 ( k — 1) + k to give an approximation factor of 1. 786. Although our primary focus is on the case k = 3, our approach in fact gives slightly stronger improvements on the factor for all k > 3. As in previous works, our guarantees hold also for the more general problem of finding a maximum weight independent set in a ( k + 1)-claw free graph.