5 citations · 6 across the 6 of their papers we have counts for
6 papers
Submodular Maximization over Many Matroids via Ordered Local Search
Neta Singer, Theophile Thiery
Given a monotone submodular function, we consider the problem of finding a maximum-valued set in the intersection of matroids. Our main result is a polynomial time local search…
Better Approximation for Weighted -Matroid Intersection
Neta Singer, Theophile Thiery
We consider the problem of finding an independent set of maximum weight simultaneously contained in matroids over a common ground set. This -matroid intersection problem app…
Asymptotically Optimal Hardness for -Set Packing and -Matroid Intersection
Euiwoong Lee, Ola Svensson, Theophile Thiery
For any , we prove that -Dimensional Matching is hard to approximate within a factor of for large unless $\textsf{NP} \subseteq \text…
An Improved Approximation for Maximum Weighted -Set Packing
Theophile Thiery, Justin Ward
We consider the weighted -set packing problem, in which we are given a collection of weighted sets, each with at most elements and must return a collection of pairwise disjo…
Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints
Chien-Chung Huang, Theophile Thiery, Justin Ward
We give improved multi-pass streaming algorithms for the problem of maximizing a monotone or arbitrary non-negative submodular function subject to a general -matchoid constraint…
Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression
Theophile Thiery, Justin Ward
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 relevant variables obeying a matroid…