3 papers
cs.DS2024
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…
cs.DS2023
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…
cs.DS2023
One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree
Costas Busch, Da Qi Chen, Arnold Filtser +3
A spanning tree of graph is a -approximate universal Steiner tree (UST) for root vertex if, for any subset of vertices containing , the cost of the minimal su…