Algorithms, Combinatorics and Optimization Seminar
— 4:00pm
Location:
In Person
-
Wean Hall 8220
Speaker:
SHERRY SARKAR
,
Ph.D. Student, Algorithms, Combinatorics and Optimization, Department of Mathematical Sciences, Carnegie Mellon University
https://sherrysarkar.github.io/
Generalizations of Online Bipartite Matching to Matroids
We study two problems in online matroid intersection. First, we consider the problem of maximizing the size of a common independent set between a general matroid and a partition matroid whose parts arrive online. This captures the classic online bipartite matching problem when both matroids are partition matroids. Our main result is a (1−1/e)-competitive algorithm for the fractional version of this problem. The key new ingredient for this result is the construction of a "water level" vector for poly-matroids, which allows us to generalize the classic water-filling algorithm for online bipartite matching. This construction reveals connections to submodular utility allocation markets and principal partition sequences of matroids.
Our second result concerns the Online Submodular Welfare Maximization (OSWM) problem, in which items arriving online are allocated among a set of agents with the goal of maximizing their overall utility. Kapralov, Post, and Vondrák showed that in this case, no polynomial time algorithm achieves a competitive ratio of 1/2 + ε unless NP = RP (SODA, 2013). We extend the RANKING algorithm of Karp, Vazirani, and Vazirani (STOC, 1990) to achieve an optimal (1−1/e)-competitive algorithm for OSWM in the case that the utility function of each agent is the rank function of a matroid.
This paper is joint work with Daniel Hathcock, Billy Jin, Kalen Patton, and Mik Zlatin.
4:00 pm: Tea and Cookies → Wean 6220 (please bring your own mug when possible)
Event Website:
https://aco.math.cmu.edu/abs-23-24/feb15.html