81 citations · 310 across the 59 of their papers we have counts for
4 papers · 1 filter
Online Packing and Covering Framework with Convex Objectives
Niv Buchbinder, Shahar Chen, Anupam Gupta +3
We consider online fractional covering problems with a convex objective, where the covering constraints arrive over time. Formally, we want to solve $\min\,\{f(x) \mid Ax\ge \mathb…
Greedy Algorithms for Steiner Forest
Anupam Gupta, Amit Kumar
In the Steiner Forest problem, we are given terminal pairs , and need to find the cheapest subgraph which connects each of the terminal pairs together. In 1991, Agraw…
How the Experts Algorithm Can Help Solve LPs Online
Anupam Gupta, Marco Molinaro
We consider the problem of solving packing/covering LPs online, when the columns of the constraint matrix are presented in random order. This problem has received much attention an…
Changing Bases: Multistage Optimization for Matroids and Matchings
Anupam Gupta, Kunal Talwar, Udi Wieder
This paper is motivated by the fact that many systems need to be maintained continually while the underlying costs change over time. The challenge is to continually maintain near-o…