


Остановите войну!
for scientists:


default search action
Anupam Gupta 0001
Person information

- affiliation: Carnegie Mellon University, Department of Computer Science, Pittsburgh, PA, USA
- affiliation: Lucent Bell Labs, Murray Hill, NJ, USA
- affiliation (PhD 2000): University of California, Berkeley, Computer Science Division, CA, USA
Other persons with the same name
- Anupam Gupta — disambiguation page
- Anupam Gupta 0002 — BlockApps AI, Bangalore Urban, India (and 2 more)
Refine list

refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
- [c168]Anupam Gupta, Amit Kumar, Debmalya Panigrahi:
Efficient Algorithms and Hardness Results for the Weighted k-Server Problem. APPROX/RANDOM 2023: 12:1-12:19 - [c167]Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, Zhouzi Li:
Graph Searching with Predictions. ITCS 2023: 12:1-12:24 - [c166]Franziska Eberle, Anupam Gupta, Nicole Megow, Benjamin Moseley, Rudy Zhou:
Configuration Balancing for Stochastic Requests. IPCO 2023: 127-141 - [c165]Anupam Gupta, Benjamin Moseley, Rudy Zhou:
Minimizing Completion Times for Stochastic Jobs via Batched Free Times. SODA 2023: 1905-1930 - [c164]Anupam Gupta, Euiwoong Lee, Jason Li:
A Local Search-Based Approach for Set Covering. SOSA 2023: 1-11 - [i90]Anupam Gupta, Gregory Kehne, Roie Levin:
Set Covering with Our Eyes Wide Shut. CoRR abs/2304.02063 (2023) - [i89]Anupam Gupta, Amit Kumar, Debmalya Panigrahi:
Efficient Algorithms and Hardness Results for the Weighted k-Server Problem. CoRR abs/2307.11913 (2023) - [i88]Niv Buchbinder, Anupam Gupta, Daniel Hathcock, Anna R. Karlin, Sherry Sarkar:
Maintaining Matroid Intersections Online. CoRR abs/2309.10214 (2023) - 2022
- [j62]Anupam Gupta, David G. Harris, Euiwoong Lee, Jason Li:
Optimal Bounds for the k-cut Problem. J. ACM 69(1): 2:1-2:18 (2022) - [j61]Anupam Gupta, Amit Kumar, Viswanath Nagarajan
, Xiangkun Shen:
Stochastic makespan minimization in structured set systems. Math. Program. 192(1): 597-630 (2022) - [j60]Ittai Abraham, Arnold Filtser
, Anupam Gupta, Ofer Neiman:
Metric Embedding via Shortest Path Decompositions. SIAM J. Comput. 51(2): 290-314 (2022) - [j59]Anupam Gupta, Amit Kumar, Debmalya Panigrahi:
Caching with Time Windows and Delays. SIAM J. Comput. 51(4): 975-1017 (2022) - [c163]Anupam Gupta:
Algorithms for Uncertain Environments: Going Beyond the Worst-Case (Invited Talk). FSTTCS 2022: 1:1-1:1 - [c162]Weina Wang, Anupam Gupta, Jalani Williams:
Probing to Minimize. ITCS 2022: 120:1-120:23 - [c161]Rohan Ghuge, Anupam Gupta, Viswanath Nagarajan:
Non-adaptive Stochastic Score Classification and Explainable Halfspace Evaluation. IPCO 2022: 277-290 - [c160]Anupam Gupta, Euiwoong Lee, Jason Li, Marcin Mucha, Heather Newman, Sherry Sarkar:
Matroid-Based TSP Rounding for Half-Integral Solutions. IPCO 2022: 305-318 - [c159]Anupam Gupta, Debmalya Panigrahi, Bernardo Subercaseaux, Kevin Sun:
Augmenting Online Algorithms with $\varepsilon$-Accurate Predictions. NeurIPS 2022 - [c158]C. J. Argue, Alan M. Frieze, Anupam Gupta, Christopher Seiler:
Learning from a Sample in Online Algorithms. NeurIPS 2022 - [c157]C. J. Argue, Anupam Gupta, Marco Molinaro, Sahil Singla:
Robust Secretary and Prophet Algorithms for Packing Integer Programs. SODA 2022: 1273-1297 - [c156]Anupam Gupta, Vijaykrishna Gurunathan, Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla:
Online Discrepancy with Recourse for Vectors and Graphs. SODA 2022: 1356-1383 - [c155]Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, David Saulpic:
An Improved Local Search Algorithm for k-Median. SODA 2022: 1556-1612 - [e3]Stefano Leonardi, Anupam Gupta:
STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022. ACM 2022, ISBN 978-1-4503-9264-8 [contents] - [i87]Anupam Gupta, Benjamin Moseley, Rudy Zhou:
Minimizing Completion Times for Stochastic Jobs via Batched Free Times. CoRR abs/2208.13696 (2022) - [i86]Franziska Eberle, Anupam Gupta, Nicole Megow, Benjamin Moseley, Rudy Zhou:
Configuration Balancing for Stochastic Requests. CoRR abs/2208.13702 (2022) - [i85]Anupam Gupta, Euiwoong Lee, Jason Li:
A Local Search-Based Approach for Set Covering. CoRR abs/2211.04444 (2022) - [i84]Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, Zhouzi Li:
Graph Searching with Predictions. CoRR abs/2212.14220 (2022) - 2021
- [j58]C. J. Argue, Anupam Gupta, Ziye Tang, Guru Guruganesh:
Chasing Convex Bodies with Linear Competitive Ratio. J. ACM 68(5): 32:1-32:10 (2021) - [j57]Anupam Gupta, Amit Kumar, Viswanath Nagarajan
, Xiangkun Shen:
Stochastic Load Balancing on Unrelated Machines. Math. Oper. Res. 46(1): 115-133 (2021) - [j56]Bailey Flanigan, Paul Gölz
, Anupam Gupta, Brett Hennig
, Ariel D. Procaccia
:
Fair algorithms for selecting citizens' assemblies. Nat. 596(7873): 548-552 (2021) - [c154]Anupam Gupta, Amit Kumar, Sahil Singla:
Bag-Of-Tasks Scheduling on Related Machines. APPROX-RANDOM 2021: 3:1-3:16 - [c153]Anupam Gupta, Amit Kumar, Debmalya Panigrahi:
A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows. FOCS 2021: 504-515 - [c152]Anupam Gupta, Gregory Kehne, Roie Levin:
Random Order Online Set Cover is as Easy as Offline. FOCS 2021: 1253-1264 - [c151]Anupam Gupta, Benjamin Moseley, Rudy Zhou:
Structural Iterative Rounding for Generalized k-Median Problems. ICALP 2021: 77:1-77:18 - [c150]Rohan Ghuge, Anupam Gupta, Viswanath Nagarajan:
The Power of Adaptivity for Stochastic Submodular Cover. ICML 2021: 3702-3712 - [c149]Anupam Gupta, Euiwoong Lee, Jason Li:
The Connectivity Threshold for Dense Graphs. SODA 2021: 89-105 - [c148]C. J. Argue, Anupam Gupta, Guru Guruganesh, Ziye Tang:
Chasing convex bodies with linear competitive ratio (invited paper). STOC 2021: 5 - [c147]Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li:
A quasipolynomial (2 + ε)-approximation for planar sparsest cut. STOC 2021: 1056-1069 - [i83]C. J. Argue, Anupam Gupta, Marco Molinaro:
Lipschitz Selectors may not Yield Competitive Algorithms for Convex Body Chasing. CoRR abs/2104.07487 (2021) - [i82]Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li:
A Quasipolynomial (2+ε)-Approximation for Planar Sparsest Cut. CoRR abs/2105.15187 (2021) - [i81]Rohan Ghuge, Anupam Gupta, Viswanath Nagarajan:
The Power of Adaptivity for Stochastic Submodular Cover. CoRR abs/2106.16115 (2021) - [i80]Anupam Gupta, Amit Kumar, Sahil Singla:
Bag-of-Tasks Scheduling on Related Machines. CoRR abs/2107.06216 (2021) - [i79]Weina Wang, Anupam Gupta, Jalani Williams:
Probing to Minimize. CoRR abs/2111.01955 (2021) - [i78]Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, David Saulpic:
An Improved Local Search Algorithm for k-Median. CoRR abs/2111.04589 (2021) - [i77]Rohan Ghuge, Anupam Gupta, Viswanath Nagarajan:
Non-Adaptive Stochastic Score Classification and Explainable Halfspace Evaluation. CoRR abs/2111.05687 (2021) - [i76]Anupam Gupta, Vijaykrishna Gurunathan, Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla:
Online Discrepancy with Recourse for Vectors and Graphs. CoRR abs/2111.06308 (2021) - [i75]Anupam Gupta, Gregory Kehne, Roie Levin:
Random Order Set Cover is as Easy as Offline. CoRR abs/2111.06842 (2021) - [i74]Anupam Gupta, Amit Kumar, Debmalya Panigrahi:
A Hitting Set Relaxation for k-Server and an Extension to Time-Windows. CoRR abs/2111.09255 (2021) - [i73]Anupam Gupta, Euiwoong Lee, Jason Li, Marcin Mucha, Heather Newman, Sherry Sarkar:
Matroid-Based TSP Rounding for Half-Integral Solutions. CoRR abs/2111.09290 (2021) - [i72]C. J. Argue, Anupam Gupta, Marco Molinaro, Sahil Singla:
Robust Secretary and Prophet Algorithms for Packing Integer Programs. CoRR abs/2112.12920 (2021) - 2020
- [c146]C. J. Argue, Anupam Gupta, Guru Guruganesh:
Dimension-Free Bounds for Chasing Convex Functions. COLT 2020: 219-241 - [c145]Anupam Gupta, Roie Levin:
Fully-Dynamic Submodular Cover with Bounded Recourse. FOCS 2020: 1147-1157 - [c144]Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla:
Online Carpooling Using Expander Decompositions. FSTTCS 2020: 23:1-23:14 - [c143]Domagoj Bradac
, Anupam Gupta, Sahil Singla
, Goran Zuzic
:
Robust Algorithms for the Secretary Problem. ITCS 2020: 32:1-32:26 - [c142]Anupam Gupta, Amit Kumar, Viswanath Nagarajan, Xiangkun Shen:
Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract). IPCO 2020: 158-170 - [c141]Bailey Flanigan, Paul Gölz
, Anupam Gupta, Ariel D. Procaccia:
Neutralizing Self-Selection Bias in Sampling for Sortition. NeurIPS 2020 - [c140]C. J. Argue, Anupam Gupta, Guru Guruganesh, Ziye Tang:
Chasing Convex Bodies with Linear Competitive Ratio. SODA 2020: 1519-1524 - [c139]Anupam Gupta, Roie Levin:
The Online Submodular Cover Problem. SODA 2020: 1525-1537 - [c138]Anupam Gupta, Euiwoong Lee, Jason Li:
The Karger-Stein algorithm is optimal for k-cut. STOC 2020: 473-484 - [c137]Anupam Gupta, Amit Kumar, Debmalya Panigrahi:
Caching with time windows. STOC 2020: 1125-1138 - [p1]Anupam Gupta, Sahil Singla:
Random-Order Models. Beyond the Worst-Case Analysis of Algorithms 2020: 234-258 - [i71]Anupam Gupta, Amit Kumar, Viswanath Nagarajan, Xiangkun Shen:
Stochastic Makespan Minimization in Structured Set Systems. CoRR abs/2002.11153 (2020) - [i70]Anupam Gupta, Sahil Singla:
Random-Order Models. CoRR abs/2002.12159 (2020) - [i69]Anupam Gupta, David G. Harris, Euiwoong Lee, Jason Li:
Optimal Bounds for the k-cut Problem. CoRR abs/2005.08301 (2020) - [i68]C. J. Argue, Anupam Gupta, Guru Guruganesh:
Dimension-Free Bounds on Chasing Convex Functions. CoRR abs/2005.14058 (2020) - [i67]Anupam Gupta, Amit Kumar, Debmalya Panigrahi:
Caching with Time Windows and Delays. CoRR abs/2006.09665 (2020) - [i66]Bailey Flanigan, Paul Gölz, Anupam Gupta, Ariel D. Procaccia:
Neutralizing Self-Selection Bias in Sampling for Sortition. CoRR abs/2006.10498 (2020) - [i65]Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla:
Online Carpooling using Expander Decompositions. CoRR abs/2007.10545 (2020) - [i64]Anupam Gupta, Roie Levin:
Fully-Dynamic Submodular Cover with Bounded Recourse. CoRR abs/2009.00800 (2020) - [i63]Anupam Gupta, Benjamin Moseley, Rudy Zhou:
Structural Iterative Rounding for Generalized k-Median Problems. CoRR abs/2009.00808 (2020)
2010 – 2019
- 2019
- [j55]Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, Kunal Talwar:
Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs. SIAM J. Comput. 48(3): 1120-1145 (2019) - [j54]Anastasios Sidiropoulos, Mihai Badoiu, Kedar Dhamdhere, Anupam Gupta, Piotr Indyk, Yuri Rabinovich, Harald Räcke, R. Ravi:
Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces. SIAM J. Discret. Math. 33(1): 454-473 (2019) - [j53]Nikhil Bansal, Anupam Gupta:
Potential-Function Proofs for Gradient Methods. Theory Comput. 15: 1-32 (2019) - [c136]Anupam Gupta, Tomer Koren, Kunal Talwar:
Better Algorithms for Stochastic Bandits with Adversarial Corruptions. COLT 2019: 1562-1578 - [c135]Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, Jason Li:
Tight FPT Approximations for k-Median and k-Means. ICALP 2019: 42:1-42:14 - [c134]Naveen Garg
, Anupam Gupta, Amit Kumar, Sahil Singla:
Non-Clairvoyant Precedence Constrained Scheduling. ICALP 2019: 63:1-63:14 - [c133]Anupam Gupta, Guru Guruganesh, Binghui Peng, David Wajc:
Stochastic Online Metric Matching. ICALP 2019: 67:1-67:14 - [c132]Anupam Gupta, Haotian Jiang, Ziv Scully
, Sahil Singla:
The Markovian Price of Information. IPCO 2019: 233-246 - [c131]Niv Buchbinder, Anupam Gupta, Marco Molinaro, Joseph (Seffi) Naor:
k-Servers with a Smile: Online Algorithms via Projections. SODA 2019: 98-116 - [c130]C. J. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta, Yin Tat Lee:
A Nearly-Linear Bound for Chasing Nested Convex Bodies. SODA 2019: 117-122 - [c129]Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi:
Elastic Caching. SODA 2019: 143-156 - [c128]Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, Michal Wlodarczyk:
Losing Treewidth by Separating Subsets. SODA 2019: 1731-1749 - [c127]Anupam Gupta, Euiwoong Lee, Jason Li:
The number of minimum k-cuts: improving the Karger-Stein bound. STOC 2019: 229-240 - [i62]Anupam Gupta, Haotian Jiang, Ziv Scully, Sahil Singla:
The Markovian Price of Information. CoRR abs/1902.07856 (2019) - [i61]Anupam Gupta, Tomer Koren, Kunal Talwar:
Better Algorithms for Stochastic Bandits with Adversarial Corruptions. CoRR abs/1902.08647 (2019) - [i60]Anupam Gupta, Amit Kumar, Viswanath Nagarajan, Xiangkun Shen:
Stochastic Load Balancing on Unrelated Machines. CoRR abs/1904.07271 (2019) - [i59]Anupam Gupta, Guru Guruganesh, Binghui Peng, David Wajc:
Stochastic Online Metric Matching. CoRR abs/1904.09284 (2019) - [i58]Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, Jason Li:
Tight FPT Approximations for $k$-Median and k-Means. CoRR abs/1904.12334 (2019) - [i57]Naveen Garg, Anupam Gupta, Amit Kumar, Sahil Singla:
Non-clairvoyant Precedence Constrained Scheduling. CoRR abs/1905.02133 (2019) - [i56]C. J. Argue, Anupam Gupta, Guru Guruganesh, Ziye Tang:
Chasing Convex Bodies with Linear Competitive Ratio. CoRR abs/1905.11877 (2019) - [i55]Anupam Gupta, Euiwoong Lee, Jason Li:
The Number of Minimum k-Cuts: Improving the Karger-Stein Bound. CoRR abs/1906.00417 (2019) - [i54]Domagoj Bradac, Anupam Gupta, Sahil Singla, Goran Zuzic:
Robust Algorithms for the Secretary Problem. CoRR abs/1911.07352 (2019) - [i53]Anupam Gupta, Euiwoong Lee, Jason Li:
The Karger-Stein Algorithm is Optimal for k-cut. CoRR abs/1911.09165 (2019) - 2018
- [j52]Nikhil Bansal, Anupam Gupta, Guru Guruganesh:
On the Lovász Theta Function for Independent Sets in Sparse Graphs. SIAM J. Comput. 47(3): 1039-1055 (2018) - [c126]Anupam Gupta, Euiwoong Lee, Jason Li:
Faster Exact and Approximate Algorithms for k-Cut. FOCS 2018: 113-123 - [c125]Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar, Sören Riechers, David Wajc:
Fully-Dynamic Bin Packing with Little Repacking. ICALP 2018: 51:1-51:24 - [c124]Anupam Gupta, Amit Kumar, Jason Li:
Non-Preemptive Flow-Time Minimization via Rejections. ICALP 2018: 70:1-70:13 - [c123]Anupam Gupta, Ruta Mehta, Marco Molinaro:
Maximizing Profit with Convex Costs in the Random-order Model. ICALP 2018: 71:1-71:14 - [c122]Martin Groß, Anupam Gupta, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt
, José Verschae:
A Local-Search Algorithm for Steiner Forest. ITCS 2018: 31:1-31:17 - [c121]Anupam Gupta, Amit Kumar, Viswanath Nagarajan, Xiangkun Shen:
Stochastic Load Balancing on Unrelated Machines. SODA 2018: 1274-1285 - [c120]Anupam Gupta, Euiwoong Lee, Jason Li:
An FPT Algorithm Beating 2-Approximation for k-Cut. SODA 2018: 2821-2837 - [c119]Ittai Abraham, Arnold Filtser, Anupam Gupta, Ofer Neiman:
Metric embedding via shortest path decompositions. STOC 2018: 952-963 - [i52]Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, Michal Wlodarczyk:
Losing Treewidth by Separating Subsets. CoRR abs/1804.01366 (2018) - [i51]Anupam Gupta, Ruta Mehta, Marco Molinaro:
Maximizing Profit with Convex Costs in the Random-order Model. CoRR abs/1804.08172 (2018) - [i50]Anupam Gupta, Amit Kumar, Jason Li:
Non-Preemptive Flow-Time Minimization via Rejections. CoRR abs/1805.09602 (2018) - [i49]C. J. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta, Yin Tat Lee:
A Nearly-Linear Bound for Chasing Nested Convex Bodies. CoRR abs/1806.08865 (2018) - [i48]Anupam Gupta, Euiwoong Lee, Jason Li:
Faster Exact and Approximate Algorithms for k-Cut. CoRR abs/1807.08144 (2018) - [i47]Niv Buchbinder, Anupam Gupta, Marco Molinaro, Joseph Naor:
k-Servers with a Smile: Online Algorithms via Projections. CoRR abs/1810.07508 (2018) - 2017
- [j51]Anupam Gupta, Viswanath Nagarajan, R. Ravi:
Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems. Math. Oper. Res. 42(3): 876-896 (2017) - [c118]Anupam Gupta, Archit Karandikar:
Stochastic Unsplittable Flows. APPROX-RANDOM 2017: 7:1-7:19 - [c117]Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao, Ruosong Wang:
Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration. COLT 2017: 482-534 - [c116]Anupam Gupta, R. Ravi, Kunal Talwar, Seeun William Umboh
:
LAST but not Least: Online Spanners for Buy-at-Bulk. SODA 2017: 589-599 - [c115]Anupam Gupta, Viswanath Nagarajan, Sahil Singla:
Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions. SODA 2017: 1688-1702 - [c114]Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi:
Online and dynamic algorithms for set cover. STOC 2017: 537-550 - [i46]Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao, Ruosong Wang:
Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration. CoRR abs/1706.01081 (2017) - [i45]Martin Groß, Anupam Gupta, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt, José Verschae:
A Local-Search Algorithm for Steiner Forest. CoRR abs/1707.02753 (2017) - [i44]Ittai Abraham, Arnold Filtser, Anupam Gupta, Ofer Neiman:
Metric Embedding via Shortest Path Decompositions. CoRR abs/1708.04073 (2017) - [i43]Anupam Gupta, Euiwoong Lee, Jason Li:
An FPT Algorithm Beating 2-Approximation for k-Cut. CoRR abs/1710.08488 (2017) - [i42]Anupam Gupta, Guru Guruganesh, Amit Kumar, David Wajc:
Fully-Dynamic Bin Packing with Limited Repacking. CoRR abs/1711.02078 (2017) - [i41]Nikhil Bansal, Anupam Gupta:
Potential-Function Proofs for First-Order Methods. CoRR abs/1712.04581 (2017) - 2016
- [j50]Zachary Friggstad, Anupam Gupta, Mohit Singh:
An Improved Integrality Gap for Asymmetric TSP Paths. Math. Oper. Res. 41(3): 745-757 (2016) - [j49]Anupam Gupta, Marco Molinaro:
How the Experts Algorithm Can Help Solve LPs Online. Math. Oper. Res. 41(4): 1404-1431 (2016) - [j48]Albert Gu, Anupam Gupta, Amit Kumar:
The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online. SIAM J. Comput. 45(1): 1-28 (2016) - [j47]Anupam Gupta, Viswanath Nagarajan, R. Ravi:
Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets. ACM Trans. Algorithms 12(1): 10:1-10:21 (2016) - [j46]T.-H. Hubert Chan, Anupam Gupta, Bruce M. Maggs, Shuheng Zhou:
On Hierarchical Routing in Doubling Metrics. ACM Trans. Algorithms 12(4): 55:1-55:22 (2016) - [j45]