9 papers
Dynamic Contention Resolution Schemes
Moran Feldman, Gregory Kehne, Roie Levin +1
We introduce a low-recourse rounding paradigm for packing problems in fully dynamic settings, which we name Dynamic Contention Resolution Schemes (DCRSs). These are dynamic analogs…
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 Secretary Problem with Predicted Additive Gap
Alexander Braun, Sherry Sarkar
The secretary problem is one of the fundamental problems in online decision making; a tight competitive ratio for this problem of has been known since…
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…
Maintaining Matroid Intersections Online
Niv Buchbinder, Anupam Gupta, Daniel Hathcock +2
Maintaining a maximum bipartite matching online while minimizing recourse/augmentations is a well studied problem, motivated by content delivery, job scheduling, and hashing. A bre…