Arrow Research search

Author name cluster

Theophile Thiery

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers
1 author row

Possible papers

3

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.

Details