Anupam Gupta

Most-cited papers

Better Algorithms for Stochastic Bandits with Adversarial Corruptions
Anupam Gupta, Tomer Koren, Kunal Talwar
2019Annual Conference Computational Learning Theory181 citations
Semantic Scholar
Fair algorithms for selecting citizens’ assemblies
Bailey Flanigan, Paul Gölz, Anupam Gupta, Brett Hennig +1 more
2021Nature148 citations Open access
Semantic Scholar
Online and dynamic algorithms for set cover
Anupam Gupta, R. Krishnaswamy, Amit Kumar, Debmalya Panigrahi
2016Symposium on the Theory of Computing95 citations Open access
Semantic Scholar
Tight FPT Approximations for $k$-Median and k-Means
Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee +1 more
2019International Colloquium on Automata, Languages and Programming86 citations Open access
Semantic Scholar
Clustering under approximation stability
Maria-Florina Balcan, Avrim Blum, Anupam Gupta
2013JACM86 citations Open access
Semantic Scholar
Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
Anupam Gupta, V. Nagarajan, Sahil Singla
2016ACM-SIAM Symposium on Discrete Algorithms84 citations
Semantic Scholar
A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs
N. Bansal, Anupam Gupta, R. Krishnaswamy, K. Pruhs +2 more
2015International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques77 citations
Semantic Scholar
Online Algorithms for Covering and Packing Problems with Convex Objectives
Y. Azar, Niv Buchbinder, T.-H. Hubert Chan, Shahar Chen +7 more
2016IEEE Annual Symposium on Foundations of Computer Science75 citations
Semantic Scholar
Maintaining Assignments Online: Matching, Scheduling, and Flows
Anupam Gupta, Amit Kumar, Cliff Stein
2014ACM-SIAM Symposium on Discrete Algorithms74 citations
Semantic Scholar
Algorithms and Adaptivity Gaps for Stochastic Probing
Anupam Gupta, V. Nagarajan, Sahil Singla
2016ACM-SIAM Symposium on Discrete Algorithms72 citations
Semantic Scholar
Potential-Function Proofs for Gradient Methods
N. Bansal, Anupam Gupta
2019Theory of Computing67 citations Open access
Semantic Scholar
Chasing Convex Bodies with Linear Competitive Ratio
C. Argue, Anupam Gupta, Ziye Tang, Guru Guruganesh
2019ACM-SIAM Symposium on Discrete Algorithms63 citations Open access
Semantic Scholar
How the Experts Algorithm Can Help Solve LPs Online
Anupam Gupta, M. Molinaro
2014Mathematics of Operations Research61 citations Open access
Semantic Scholar
Pure Exploration of Multi-armed Bandit Under Matroid Constraints
Lijie Chen, Anupam Gupta, Jian Li
2016Annual Conference Computational Learning Theory55 citations
Semantic Scholar
Random-Order Models
Anupam Gupta, Sahil Singla
2020Beyond the Worst-Case Analysis of Algorithms53 citations Open access
Semantic Scholar
Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
Lijie Chen, Anupam Gupta, J. Li, Ming-Da Qiao +1 more
2017Annual Conference Computational Learning Theory53 citations
Semantic Scholar
Changing Bases: Multistage Optimization for Matroids and Matchings
Anupam Gupta, Kunal Talwar, Udi Wieder
2014International Colloquium on Automata, Languages and Programming50 citations Open access
Semantic Scholar
Towards (1 + ∊)-Approximate Flow Sparsifiers
Alexandr Andoni, Anupam Gupta, Robert Krauthgamer
2013ACM-SIAM Symposium on Discrete Algorithms46 citations
Semantic Scholar
Neutralizing Self-Selection Bias in Sampling for Sortition
Bailey Flanigan, Paul Gölz, Anupam Gupta, Ariel D. Procaccia
2020Neural Information Processing Systems45 citations
Semantic Scholar
A Randomized O(log2k)-Competitive Algorithm for Metric Bipartite Matching
N. Bansal, Niv Buchbinder, Anupam Gupta, J. Naor
2014Algorithmica43 citations
Semantic Scholar
Faster Exact and Approximate Algorithms for k-Cut
Anupam Gupta, Euiwoong Lee, Jason Li
2018IEEE Annual Symposium on Foundations of Computer Science40 citations Open access
Semantic Scholar
A Nearly-Linear Bound for Chasing Nested Convex Bodies
C. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta +1 more
2018ACM-SIAM Symposium on Discrete Algorithms37 citations Open access
Semantic Scholar
Stochastic Online Metric Matching
Anupam Gupta, Guru Guruganesh, Binghui Peng, David Wajc
2019International Colloquium on Automata, Languages and Programming36 citations
Semantic Scholar
An FPT Algorithm Beating 2-Approximation for k-Cut
Anupam Gupta, Euiwoong Lee, Jason Li
2017ACM-SIAM Symposium on Discrete Algorithms36 citations
Semantic Scholar
Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
Anupam Gupta, R. Krishnaswamy, V. Nagarajan, R. Ravi
2015Mathematics of Operations Research36 citations Open access
Semantic Scholar
On the Lovász Theta function for Independent Sets in Sparse Graphs
N. Bansal, Anupam Gupta, Guru Guruganesh
2015Symposium on the Theory of Computing35 citations Open access
Semantic Scholar
An Improved Local Search Algorithm for k-Median
Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh +1 more
2021ACM-SIAM Symposium on Discrete Algorithms33 citations Open access
Semantic Scholar
Fully-Dynamic Bin Packing with Little Repacking
Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh +3 more
2018International Colloquium on Automata, Languages and Programming33 citations
Semantic Scholar
The Online Submodular Cover Problem
Anupam Gupta, Roie Levin
2020ACM-SIAM Symposium on Discrete Algorithms32 citations Open access
Semantic Scholar
Losing Treewidth by Separating Subsets
Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi +1 more
2018ACM-SIAM Symposium on Discrete Algorithms31 citations Open access
Semantic Scholar
k-Servers with a Smile: Online Algorithms via Projections
Niv Buchbinder, Anupam Gupta, M. Molinaro, Joseph +1 more
2018ACM-SIAM Symposium on Discrete Algorithms30 citations
Semantic Scholar
Potential-Function Proofs for First-Order Methods
N. Bansal, Anupam Gupta
2017arXiv.org30 citations
Semantic Scholar
The Markovian Price of Information
Anupam Gupta, Haotian Jiang, Ziv Scully, Sahil Singla
2019Conference on Integer Programming and Combinatorial Optimization29 citations
Semantic Scholar
Robust Algorithms for the Secretary Problem
Domagoj Bradač, Anupam Gupta, Sahil Singla, Goran Zuzic
2019Information Technology Convergence and Services28 citations
Semantic Scholar
Greedy Algorithms for Steiner Forest
Anupam Gupta, Amit Kumar
2014Symposium on the Theory of Computing28 citations
Semantic Scholar
Stochastic Load Balancing on Unrelated Machines
Anupam Gupta, Amit Kumar, V. Nagarajan, Xiangkun Shen
2018ACM-SIAM Symposium on Discrete Algorithms27 citations Open access
Semantic Scholar
How Experts Can Solve LPs Online
Anupam Gupta, M. Molinaro
2014Embedded Systems and Applications26 citations
Semantic Scholar
Metric embedding via shortest path decompositions
Ittai Abraham, Arnold Filtser, Anupam Gupta, O. Neiman
2017Symposium on the Theory of Computing24 citations Open access
Semantic Scholar
Fully-Dynamic Submodular Cover with Bounded Recourse
Anupam Gupta, Roie Levin
2020IEEE Annual Symposium on Foundations of Computer Science22 citations Open access
Semantic Scholar
Random Order Online Set Cover is as Easy as Offline
Anupam Gupta, Gregory Kehne, Roie Levin
2022IEEE Annual Symposium on Foundations of Computer Science21 citations
Semantic Scholar
The number of minimum k-cuts: improving the Karger-Stein bound
Anupam Gupta, Euiwoong Lee, Jason Li
2019Symposium on the Theory of Computing20 citations Open access
Semantic Scholar
Optimal Bounds for the k-cut Problem
Anupam Gupta, David G. Harris, Euiwoong Lee, Jason Li
2020Journal of the ACM18 citations Open access
Semantic Scholar
Caching with time windows
Anupam Gupta, Amit Kumar, Debmalya Panigrahi
2020Symposium on the Theory of Computing18 citations Open access
Semantic Scholar
Elastic Caching
Anupam Gupta, R. Krishnaswamy, Amit Kumar, Debmalya Panigrahi
2019ACM-SIAM Symposium on Discrete Algorithms18 citations Open access
Semantic Scholar
Augmenting Online Algorithms with ε -Accurate Predictions
Anupam Gupta, Debmalya Panigrahi, Bernardo Subercaseaux, Kevin Sun
202217 citations
Semantic Scholar
Structural iterative rounding for generalized k-median problems
Anupam Gupta, Benjamin Moseley, Rudy Zhou
2020Mathematical programming17 citations Open access
Semantic Scholar
Online Packing and Covering Framework with Convex Objectives
Niv Buchbinder, Shahar Chen, Anupam Gupta, V. Nagarajan +1 more
2014arXiv.org17 citations
Semantic Scholar
Learning from a Sample in Online Algorithms
C. Argue, A. Frieze, Anupam Gupta, Christopher Seiler
2022Neural Information Processing Systems16 citations
Semantic Scholar
A Local Search-Based Approach for Set Covering
Anupam Gupta, Euiwoong Lee, Jason Li
2022SIAM Symposium on Simplicity in Algorithms16 citations Open access
Semantic Scholar
Dimension-Free Bounds on Chasing Convex Functions
C. Argue, Anupam Gupta, Guru Guruganesh
2020Annual Conference Computational Learning Theory16 citations
Semantic Scholar