81 citations · 310 across the 59 of their papers we have counts for
12 papers · 2 filters
Robust Secretary and Prophet Algorithms for Packing Integer Programs
C. J. Argue, Anupam Gupta, Marco Molinaro +1
We study the problem of solving Packing Integer Programs (PIPs) in the online setting, where columns in of the constraint matrix are revealed sequentially, and the goal i…
A Hitting Set Relaxation for -Server and an Extension to Time-Windows
Anupam Gupta, Amit Kumar, Debmalya Panigrahi
We study the -server problem with time-windows. In this problem, each request arrives at some point of an -point metric space at time and comes with a deadlin…
Online Discrepancy with Recourse for Vectors and Graphs
Anupam Gupta, Vijaykrishna Gurunathan, Ravishankar Krishnaswamy +2
The vector-balancing problem is a fundamental problem in discrepancy theory: given T vectors in , find a signing of each vector to minimize the d…
An Improved Local Search Algorithm for k-Median
Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu +2
We present a new local-search algorithm for the -median clustering problem. We show that local optima for this algorithm give a -approximation; our result improves up…
Probing to Minimize
Weina Wang, Anupam Gupta, Jalani Williams
We develop approximation algorithms for set-selection problems with deterministic constraints, but random objective values, i.e., stochastic probing problems. When the goal is to m…
Matroid-Based TSP Rounding for Half-Integral Solutions
Anupam Gupta, Euiwoong Lee, Jason Li +3
We show how to round any half-integral solution to the subtour-elimination relaxation for the TSP, while losing a less-than-1.5 factor. Such a rounding algorithm was recently given…