81 citations · 310 across the 59 of their papers we have counts for
8 papers · 1 filter
Structural Iterative Rounding for Generalized -Median Problems
Anupam Gupta, Benjamin Moseley, Rudy Zhou
This paper considers approximation algorithms for generalized -median problems. This class of problems can be informally described as -median with a constant number of extra…
Fully-Dynamic Submodular Cover with Bounded Recourse
Anupam Gupta, Roie Levin
In submodular covering problems, we are given a monotone, nonnegative submodular function and wish to find the min-cost set such tha…
Online Carpooling using Expander Decompositions
Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar +1
We consider the online carpooling problem: given vertices, a sequence of edges arrive over time. When an edge arrives at time step , the algorithm must or…
Caching with Time Windows and Delays
Anupam Gupta, Amit Kumar, Debmalya Panigrahi
We consider two generalizations of the classical weighted paging problem that incorporate the notion of delayed service of page requests. The first is the (weighted) Paging with Ti…
Neutralizing Self-Selection Bias in Sampling for Sortition
Bailey Flanigan, Paul Gölz, Anupam Gupta +1
Sortition is a political system in which decisions are made by panels of randomly selected citizens. The process for selecting a sortition panel is traditionally thought of as unif…
Dimension-Free Bounds on Chasing Convex Functions
C. J. Argue, Anupam Gupta, Guru Guruganesh
We consider the problem of chasing convex functions, where functions arrive over time. The player takes actions after seeing the function, and the goal is to achieve a small functi…