81 citations · 310 across the 59 of their papers we have counts for
7 papers · 2 filters
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…
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…
Optimal Bounds for the -cut Problem
Anupam Gupta, David G. Harris, Euiwoong Lee +1
In the -cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi)graph into connected components. Algorithms of Karger \& Stein can s…