4 papers
Submodular Maximization over Bipartite Perfect Matchings and Matroid Intersection Bases
Chandra Chekuri, Lars Rohwedder, Neta Singer +2
Motivated by applications in fairness and foundational questions, we consider the problem of maximizing a monotone submodular function over m…
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…
Second Price Matching with Complete Allocation and Degree Constraints
Rom Pinchasi, Neta Singer, Lukas Vogl +1
We study the Second Price Matching problem, introduced by Azar, Birnbaum, Karlin, and Nguyen in 2009. In this problem, a bipartite graph (bidders and goods) is given, and the profi…
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…