81 citations · 310 across the 59 of their papers we have counts for
80 papers · 1 filter
Efficient Algorithms and Hardness Results for the Weighted -Server Problem
Anupam Gupta, Amit Kumar, Debmalya Panigrahi
In this paper, we study the weighted -server problem on the uniform metric in both the offline and online settings. We start with the offline setting. In contrast to the (unweig…
The Price of Explainability for Clustering
Anupam Gupta, Madhusudhan Reddy Pittu, Ola Svensson +1
Given a set of points in -dimensional space, an explainable clustering is one where the clusters are specified by a tree of axis-aligned threshold cuts. Dasgupta et al. (ICML 20…
Set Covering with Our Eyes Wide Shut
Anupam Gupta, Gregory Kehne, Roie Levin
In the stochastic set cover problem (Grandoni et al., FOCS '08), we are given a collection of sets over a universe of size , and a distribution $…
A Local Search-Based Approach for Set Covering
Anupam Gupta, Euiwoong Lee, Jason Li
In the Set Cover problem, we are given a set system with each set having a weight, and we want to find a collection of sets that cover the universe, whilst having low total weight.…
Configuration Balancing for Stochastic Requests
Franziska Eberle, Anupam Gupta, Nicole Megow +2
The configuration balancing problem with stochastic requests generalizes many well-studied resource allocation problems such as load balancing and virtual circuit routing. In it, w…
Minimizing Completion Times for Stochastic Jobs via Batched Free Times
Anupam Gupta, Benjamin Moseley, Rudy Zhou
We study the classic problem of minimizing the expected total completion time of jobs on identical machines in the setting where the sizes of the jobs are stochastic. Specifica…