4 papers · 1 filter
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…