6 papers
Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
Niv Buchbinder, Moran Feldman, Siyue Liu +1
We study random order semi-streaming algorithms for submodular maximization under a wide range of combinatorial constraint classes, including matroids, matroid -parity, -exch…
Online Steiner Forest with Recourse
Yaowei Long, Sepideh Mahabadi, Sherry Sarkar +1
In the online Steiner forest problem we are given a graph , and a sequence of terminal pairs which arrive in an online fashion. We are asked to maintain a low-cost s…
Improved Algorithms for Fair Matroid Submodular Maximization
Sepideh Mahabadi, Sherry Sarkar, Jakub Tarnawski
Submodular maximization subject to matroid constraints is a central problem with many applications in machine learning. As algorithms are increasingly used in decision-making over…
Sum-Of-Squares To Approximate Knapsack
Pravesh K. Kothari, Sherry Sarkar
These notes give a self-contained exposition of Karlin, Mathieu and Nguyen's tight estimate of the integrality gap of the sum-of-squares semidefinite program for solving the knapsa…
The Online Submodular Assignment Problem
Daniel Hathcock, Billy Jin, Kalen Patton +2
Online resource allocation is a rich and varied field. One of the most well-known problems in this area is online bipartite matching, introduced in 1990 by Karp, Vazirani, and Vazi…
The Online Submodular Assignment Problem
Daniel Hathcock, Billy Jin, Kalen Patton +2
Online resource allocation is a rich and varied field. One of the most well-known problems in this area is online bipartite matching, introduced in 1990 by Karp, Vazirani, and Vazi…