81 citations · 310 across the 59 of their papers we have counts for
6 papers · 1 filter
-Servers with a Smile: Online Algorithms via Projections
Niv Buchbinder, Anupam Gupta, Marco Molinaro +2
We consider the -server problem on trees and HSTs. We give an algorithm based on Bregman projections. This algorithm has a competitive ratios that match some of the recent resul…
Faster Exact and Approximate Algorithms for -Cut
Anupam Gupta, Euiwoong Lee, Jason Li
In the -cut problem, we are given an edge-weighted graph and an integer , and have to remove a set of edges with minimum total weight so that has at least connect…
A Nearly-Linear Bound for Chasing Nested Convex Bodies
C. J. Argue, Sébastien Bubeck, Michael B. Cohen +2
Friedman and Linial introduced the convex body chasing problem to explore the interplay between geometry and competitive ratio in metrical task systems. In convex body chasing, at…
Non-Preemptive Flow-Time Minimization via Rejections
Anupam Gupta, Amit Kumar, Jason Li
We consider the online problem of minimizing weighted flow-time on unrelated machines. Although much is known about this problem in the resource-augmentation setting, these results…
Maximizing Profit with Convex Costs in the Random-order Model
Anupam Gupta, Ruta Mehta, Marco Molinaro
Suppose a set of requests arrives online: each request gives some value if accepted, but requires using some amount of each of resources. Our cost is a convex function of…
Losing Treewidth by Separating Subsets
Anupam Gupta, Euiwoong Lee, Jason Li +2
We study the problem of deleting the smallest set of vertices (resp. edges) from a given graph such that the induced subgraph (resp. subgraph) belongs to so…