>> Publications

DBLP | ACM DL | Google Scholar | BibTeX

2026

Online Convex Optimization with Sublinear Noisy Probes

COLT, 2026

(with Simone DiGregorio, Stefano Leonardi and Matteo Russo)
A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling

CoRR, abs/2603.17542, 2026
[
url doi
]
(with Haim Kaplan, Alexander Lindermayr, Jens Schl{\"{o}}ter and Sorrachai Yingchareonthawornchai)
Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems

SoCG, 2026

CoRR, abs/2603.14293, 2026
[
url doi
]
(with Sujoy Bhore and Amit Kumar)
Combinatorial Optimization using Comparison Oracles

STOC, 2026

CoRR, abs/2511.15142, 2025
[
url
]
(with Vincent Cohen-Addad, Tommaso d'Orsi, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Reddy Pittu, Jon Schneider and David P. Woodruff)
Steiner Forest: A Simplified Better-Than-2 Approximation

STOC, 2026

CoRR, abs/2511.18460, 2025
[
url
]
(with Vera Traub)
Complexity of Local Search for CSPs Parameterized by Constraint Difference

CoRR, abs/2512.03275, 2025
[
url
]
(with Aditya Anand, Vincent Cohen-Addad, Tommaso d'Orsi, Euiwoong Lee, Debmalya Panigrahi and Sijin Peng)
Learning Packing and Covering from Samples

SODA, 2026
[
url
]
(with Marco Molinaro)
A Learning Perspective on Random-Order Covering Problems

SOSA, 2026
[
url
]

CoRR, abs/2511.07283, 2025
[
url
]
(with Marco Molinaro and Matteo Russo)
An Optimal Online Algorithm for Robust Flow Time Scheduling

SODA, 2026
[
url
]
(with Amit Kumar, Debmalya Panigrahi and Zhaozi Wang)

2025

Parsimonious Predictions for Strategyproof Scheduling

NeurIPS, 2025
[
url
]
(with Richard Cole and Pranav Jangir)
Robust Contextual Pricing

NeurIPS, 2025
[
url
]
(with Guru Guruganesh, Renato Paes Leme and Jon Schneider)
Length Generalization via Auxiliary Tasks

NeurIPS, 2025
[
url
]
(with Pranjal Awasthi and Ravi Kumar)
A Little Clairvoyance Is All You Need

FOCS, 2025

CoRR, abs/2508.17759, 2025
[
url
]
(with Haim Kaplan, Alexander Lindermayr, Jens Schloeter and Sorrachai Yingchareonthawornchai)
Why is My Route Different Today? An Algorithm for Explaining Route Selection

SIAM Applied and Computational Discrete Algorithms (ACDA), 2025
[
url doi
]

CoRR, abs/2506.05604, 2025
[
url
]
(with Aaron Schild, Sreenivas Gollapudi, Kostas Kollias and Ali Kemal Sinop)
Tight Results for Online Convex Paging

STOC, 2025
[
url
]
(with Amit Kumar and Debmalya Panigrahi)
Multi-Platform Autobidding with and without Predictions

WWW, 2025
[
url
]

CoRR, abs/2502.19317, 2025
[
url
]
(with Gagan Aggarwal, Xizhi Tan and Mingfei Zhao)

2024

MAC Advice for facility location mechanism design

NeurIPS, 2024
[
url
]

CoRR, abs/2403.12181, 2024
[
url
]
(with Zohar Barak and Inbal Talgam{-}Cohen)
The Average-Value Allocation Problem

APPROX, 317, 2024
[
url
]

CoRR, abs/2407.10401, 2024
[
url
]
(with Kshipra Bhawalkar, Zhe Feng, Aranyak Mehta, David Wajc and Di Wang)
Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structure

NeurIPS, 2024
[
url
]

CoRR, abs/2405.20671, 2024
[
url
]
(with Hanseul Cho, Jaeyoung Cha, Pranjal Awasthi, Srinadh Bhojanapalli and Chulhee Yun)
Randomized Truthful Auctions with Learning Agents

NeurIPS, 2024
[
url
]

CoRR, abs/2411.09517, 2024
[
url
]
(with Gagan Aggarwal, Andr{\'{e}}s Perlroth and Grigoris Velegkas)
Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems

NeurIPS, 2024
[
url
]

CoRR, abs/2402.18263, 2024
[
url
]
(with Vincent Cohen-Addad, Tommaso d'Orsi, Euiwoong Lee and Debmalya Panigrahi)
Pairwise-Independent Contention Resolution

IPCO, 2024
[
url
]

Math. Program., 216, 2026
[
url doi
]

CoRR, abs/2406.15876, 2024
[
url
]
(with Jinqiao Hu, Gregory Kehne and Roie Levin)
Poly-logarithmic Competitiveness for the k-Taxi Problem

SODA, 2024
[
url
]
(with Amit Kumar and Debmalya Panigrahi)
Set Covering with Our Eyes Wide Shut

SODA, 2024
[
url
]

CoRR, abs/2304.02063, 2023
[
url
]
(with Gregory Kehne and Roie Levin)
Maintaining Matroid Intersections Online

SODA, 2024
[
url
]

CoRR, abs/2309.10214, 2023
[
url
]
(with Niv Buchbinder, Daniel Hathcock, Anna R. Karlin and Sherry Sarkar)

2023

Improving Length-Generalization in Transformers via Task Hinting

CoRR, abs/2310.00726, 2023
[
url
]
(with Pranjal Awasthi)
Efficient Algorithms and Hardness Results for the Weighted k-Server Problem

APPROX, 2023
[
url
]

CoRR, abs/2307.11913, 2023
[
url
]
(with Amit Kumar and Debmalya Panigrahi)
The Price of Explainability for Clustering

FOCS, 2023
[
url
]

CoRR, abs/2304.09743, 2023
[
url
]
(with Madhusudhan Reddy Pittu, Ola Svensson and Rachel Yuan)
Graph Searching with Predictions

ITCS, 2023

CoRR, abs/2212.14220, 2022
[
url
]
(with Siddhartha Banerjee, Vincent Cohen-Addad and Zhouzi Li)
Configuration Balancing for Stochastic Requests

IPCO, 2023
[
url
]

Math. Program., 210, 2025
[
url
]

CoRR, abs/2208.13702, 2022
[
url
]
(with Franziska Eberle, Nicole Megow, Benjamin Moseley and Rudy Zhou)
Minimizing Completion Times for Stochastic Jobs via Batched Free Times

SODA, 2023
[
doi
]

CoRR, abs/2208.13696, 2022
[
url
]
(with Benjamin Moseley and Rudy Zhou)
A Local Search-Based Approach for Set Covering

SOSA, 2023
[
doi
]

CoRR, abs/2211.04444, 2022
[
url
]
(with Euiwoong Lee and Jason Li)

2022

Learning from a Sample in Online Algorithms

NeurIPS, 2022
[
url
]
(with C.J. Argue, Alan Frieze and Christopher Seiler)
Augmenting Online Algorithms with $\varepsilon$-Accurate Predictions

NeurIPS, 2022
[
url
]
(with Debmalya Panigrahi, Bernardo Subercaseaux and Kevin Sun)
Probing to Minimize

ITCS, 2022
[
url
]

CoRR, abs/2111.01955, 2021
[
url
]
(with Weina Wang and Jalani Williams)
Non-adaptive Stochastic Score Classification and Explainable Halfspace Evaluation

IPCO, 2022
[
url
]

Oper. Res., 73, 2025
[
url
]

CoRR, abs/2111.05687, 2021
[
url
]
(with Rohan Ghuge and Viswanath Nagarajan)
Matroid-Based TSP Rounding for Half-Integral Solutions

IPCO, 2022
[
url
]

Math. Program., 206, 2024
[
url
]

CoRR, abs/2111.09290, 2021
[
url
]
(with Euiwoong Lee, Jason Li, Marcin Mucha, Heather Newman and Sherry Sarkar)
Online Discrepancy with Recourse for Vectors and Graphs

SODA, 2022
[
url
]

CoRR, abs/2111.06308, 2021
[
url
]
(with Vijaykrishna Gurunathan, Ravishankar Krishnaswamy, Amit Kumar and Sahil Singla)
Robust Secretary and Prophet Algorithms for Packing Integer Programs

SODA, 2022
[
url
]

CoRR, abs/2112.12920, 2021
[
url
]
(with C. J. Argue, Marco Molinaro and Sahil Singla)
An Improved Local Search Algorithm for k-Median

SODA, 2022
[
url
]

CoRR, abs/2111.04589, 2021
[
url
]
(with Vincent Cohen{-}Addad, Lunjia Hu, Hoon Oh and David Saulpic)

2021

Bag-Of-Tasks Scheduling on Related Machines

APPROX, 207, 2021
[
url
]
(with Amit Kumar and Sahil Singla)
A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows

FOCS, 2021

CoRR, abs/2111.09255, 2021
[
url
]
(with Amit Kumar and Debmalya Panigrahi)
Random Order Online Set Cover is as Easy as Offline

FOCS, 2021

CoRR, abs/2111.06842, 2021
[
url
]
(with Gregory Kehne and Roie Levin)
Fair algorithms for selecting citizens' assemblies

Nature, 596, 2021
[
url
]
(with Bailey Flanigan, Paul {G\"{o}lz, Brett Hennig and Ariel Procaccia)
Structural Iterative Rounding for Generalized k-Median Problems

ICALP, 198, 2021
[
url
]

Math. Program., 212, 2025
[
url doi
]
(with Benjamin Moseley and Rudy Zhou)
The Power of Adaptivity for Stochastic Submodular Cover

ICML, 139, 2021
[
url
]

Oper. Res., 72, 2024
[
url
]

CoRR, abs/2106.16115, 2021
[
url
]
(with Rohan Ghuge and Viswanath Nagarajan)
A Quasipolynomial (2 + $\varepsilon$)-Approximation for Planar Sparsest Cut

STOC, 2021
[
url
]

CoRR, abs/2105.15187, 2021
[
url
]
(with Vincent Cohen{-}Addad, Philip N. Klein and Jason Li)
The Connectivity Threshold for Dense Graphs

SODA, 2021
[
url
]
(with Euiwoong Lee and Jason Li)
Lipschitz Selectors may not Yield Competitive Algorithms for Convex Body Chasing

CoRR, abs/2104.07487, 2021
[
url
]

Discret. Comput. Geom., 70, 2023
[
url
]
(with C. J. Argue and Marco Molinaro)

2020

Optimal Bounds for the $k$-cut Problem

J. {ACM}, 69, 2022
[
url
]

CoRR, abs/2005.08301, 2020
[
url
]
(with David G. Harris, Euiwoong Lee and Jason Li)
Dimension-Free Bounds for Chasing Convex Functions

COLT, 2020
[
url
]

CoRR, abs/2005.14058, 2020
[
url
]
(with C. J. Argue and Guru Guruganesh)
Neutralizing Self-Selection Bias in Sampling for Sortition

NeurIPS, 2020
[
url
]

CoRR, abs/2006.10498, 2020
[
url
]
(with Bailey Flanigan, Paul Goelz and Ariel D. Procaccia)
Fully-Dynamic Submodular Cover with Bounded Recourse

FOCS, 2020

CoRR, abs/2009.00800, 2020
[
url
]
(with Roie Levin)
Online Carpooling Using Expander Decompositions

FSTTCS, 2020
[
url doi
]

CoRR, abs/2007.10545, 2020
[
url
]
(with Ravishankar Krishnaswamy, Amit Kumar and Sahil Singla)
Caching with Time-Windows

STOC, 2020
[
url doi
]

{SIAM} J. Comput., 51, 2022
[
url
]

CoRR, abs/2006.09665, 2020
[
url
]
(with Amit Kumar and Debmalya Panigrahi)
The Karger-Stein Algorithm is Optimal for $k$-Cut

STOC, 2020
[
url doi
]

CoRR, abs/1911.09165, 2019
[
url
]
(with Euiwoong Lee and Jason Li)
Robust Algorithms for the Secretary Problem

ITCS, 2020
[
url doi
]

CoRR, abs/1911.07352, 2019
[
url
]
(with Domagoj Bradac, Sahil Singla and Goran Zuzic)
Random-Order Models

Beyond the Worst-Case Analysis of Algorithms, 2020
[
url
]

CoRR, abs/2002.12159, 2020
[
url
]
(with Sahil Singla)
Stochastic Makespan Minimization in Structured Set Systems

IPCO, 2020
[
url doi
]

Math. Program., 192, 2022
[
url
]

CoRR, abs/2002.11153, 2020
[
url
]
(with Amit Kumar, Viswanath Nagarajan and Xiangkun Shen)
Chasing Convex Bodies with Linear Competitive Ratio

SODA, 2020
[
url doi
]

J. {ACM}, 68, 2021
[
url
]

CoRR, abs/1905.11877, 2019
[
url
]
(with C. J. Argue, Guru Guruganesh and Ziye Tang)
The Online Submodular Cover Problem

SODA, 2020
[
url doi
]
(with Roie Levin)

2019

Potential-Function Proofs for Gradient Methods

Theory of Computing, 15, 2019
[
url doi
]

CoRR, abs/1712.04581, 2017
[
url
]
(with Bansal, Nikhil and Gupta, Anupam)
A Nearly-Linear Bound for Chasing Nested Convex Bodies

SODA, 2019
[
url doi
]

CoRR, abs/1806.08865, 2018
[
url
]
(with C. J. Argue, S{\'{e}}bastien Bubeck, Michael B. Cohen and Yin Tat Lee)
k-Servers with a Smile: Online Algorithms via Projections

SODA, 2019
[
url doi
]

CoRR, abs/1810.07508, 2018
[
url
]
(with Niv Buchbinder, Marco Molinaro and Joseph (Seffi) Naor)
Tight FPT Approximations for k-Median and k-Means

ICALP, 2019
[
url doi
]

CoRR, abs/1904.12334, 2019
[
url
]
(with Vincent Cohen{-}Addad, Amit Kumar, Euiwoong Lee and Jason Li)
Non-Clairvoyant Precedence Constrained Scheduling

ICALP, 2019
[
url doi
]

CoRR, abs/1905.02133, 2019
[
url
]
(with Naveen Garg, Amit Kumar and Sahil Singla)
Stochastic Online Metric Matching

ICALP, 2019
[
url doi
]

CoRR, abs/1904.09284, 2019
[
url
]
(with Guru Guruganesh, Binghui Peng and David Wajc)
The Markovian Price of Information

IPCO, 2019
[
url doi
]

CoRR, abs/1902.07856, 2019
[
url
]
(with Haotian Jiang, Ziv Scully and Sahil Singla)
Better Algorithms for Stochastic Bandits with Adversarial Corruptions

COLT, 2019
[
url
]

CoRR, abs/1902.08647, 2019
[
url
]
(with Tomer Koren and Kunal Talwar)
Elastic Caching

SODA, 2019
[
url doi
]
(with Ravishankar Krishnaswamy, Amit Kumar and Debmalya Panigrahi)
The number of minimum k-cuts: improving the Karger-Stein bound

STOC, 2019
[
url
]

CoRR, abs/1906.00417, 2019
[
url
]
(with Euiwoong Lee and Jason Li)
Losing Treewidth by Separating Subsets

SODA, 2019
[
url doi
]

CoRR, abs/1804.01366, 2018
[
url
]
(with Euiwoong Lee, Jason Li, Pasin Manurangsi and Michal Wlodarczyk)

2018

Faster Exact and Approximate Algorithms for k-Cut

FOCS, 2018
[
url doi
]

CoRR, abs/1807.08144, 2018
[
url
]
(with Euiwoong Lee and Jason Li)
Metric Embedding via Shortest Path Decompositions

ACM Symposium on the Theory of Computing (STOC), 2018
[
url
]

{SIAM} J. Comput., 51, 2022
[
url
]

CoRR, abs/1708.04073, 2017
[
url
]
(with Ittai Abraham, Arnold Filtser and Ofer Neiman)
Fully-Dynamic Bin Packing with Little Repacking

ICALP, 2018
[
url
]

CoRR, abs/1711.02078, 2017
[
url
]
(with Bj{\"{o}}rn Feldkord, Matthias Feldotto, Guru Guruganesh, Amit Kumar, S{\"{o}}ren Riechers and David Wajc)
A Local-Search Algorithm for Steiner Forest

ITCS, 2018
[
url doi
]

CoRR, abs/1707.02753, 2017
[
url
]
(with Martin Gro{\ss, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt and Jos{\'{e}} Verschae)
Non-Preemptive Flow-Time Minimization via Rejections

ICALP, 2018
[
url
]

CoRR, abs/1805.09602, 2018
[
url
]
(with Amit Kumar and Jason Li)
Stochastic Load Balancing on Unrelated Machines

SODA, 2018
[
url doi
]

Math. Oper. Res., 46, 2021
[
url doi
]

CoRR, abs/1904.07271, 2019
[
url
]
(with Amit Kumar, Viswanath Nagarajan and Xiangkun Shen)
An FPT Algorithm Beating 2-Approximation for $k$-Cut

SODA, 2018
[
url doi
]

CoRR, abs/1710.08488, 2017
[
url
]
(with Euiwoong Lee and Jason Li)
Maximizing Profit with Convex Costs in the Random-order Model

ICALP, 2018
[
url
]

CoRR, abs/1804.08172, 2018
[
url
]
(with Ruta Mehta and Marco Molinaro)

2017

Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration

COLT, 2017
[
url
]

CoRR, abs/1706.01081, 2017
[
url
]
(with Lijie Chen, Jian Li, Mingda Qiao and Ruosong Wang)
Stochastic Unsplittable Flows

APPROX, 2017
[
url doi
]
(with Archit Karandikar)
Online and Dynamic Algorithms for Set Cover

ACM Symposium on the Theory of Computing (STOC), 2017
[
url
]

CoRR, abs/1611.05646, 2016
[
url
]
(with Amit Kumar, Ravishankar Krishnaswamy and Debmalya Panigrahi)
Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions

SODA, 2017
[
url doi
]
(with Viswanath Nagarajan and Sahil Singla)
LAST but not Least: Online Spanners for Buy-at-Bulk

SODA, 2017
[
url doi
]

CoRR, abs/1611.00052, 2016
[
url
]
(with R. Ravi, Kunal Talwar and Seeun William Umboh)

2016

Online Algorithms for Covering and Packing Problems with Convex Objectives

FOCS, 2016
[
url doi
]
(with Yossi Azar, Niv Buchbinder, T.{-}H. Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor and Debmalya Panigrahi)
Online Packing and Covering Framework with Convex Objectives

CoRR, abs/1412.8347, 2014
[
url
]
(with Niv Buchbinder, Shahar Chen, Viswanath Nagarajan and Joseph (Seffi) Naor)
Pure Exploration of Multi-armed Bandit Under Matroid Constraints

COLT, 2016
[
url
]

CoRR, abs/1605.07162, 2016
[
url
]
(with Lijie Chen and Jian Li)
Approximation algorithms for aversion $k$-clustering via local $k$-median

ICALP, 2016
[
url doi
]
(with Guru Guruganesh and Melanie Schmidt)
Algorithms and Adaptivity Gaps for Stochastic Probing

SODA, 2016
[
url doi
]
(with Viswanath Nagarajan and Sahil Singla)

2015

On the Lov\'asz Theta function for Independent Sets in Sparse Graphs

ACM Symposium on the Theory of Computing (STOC), 2015
[
url doi
]

{SIAM} J. Comput., 47, 2018
[
url
]

CoRR, abs/1504.04767, 2015
[
url
]
(with Nikhil Bansal and Guru Guruganesh)
A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs

APPROX-RANDOM, 2015
[
url doi
]
(with Nikhil Bansal, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior and Clifford Stein)
Greedy Algorithms for Steiner Forest

ACM Symposium on the Theory of Computing (STOC), 2015
[
url doi
]

CoRR, abs/1412.7693, 2015
[
url
]
(with Amit Kumar)

2014

Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs

ACM Symposium on the Theory of Computing (STOC), 2014
[
url doi
]

{SIAM} J. Comput., 48, 2019
[
url doi
]

CoRR, abs/1311.3048, 2013
[
url
]
(with Ittai Abraham, Cyril Gavoille, Ofer Neiman and Kunal Talwar)
Towards $(1+\epsilon)$-Approximate Flow Sparsifiers

SODA, 2014
[
doi
]

CoRR, 1310.3252, 2013
[
url
]
(with Alexandr Andoni and Robert Krauthgamer)
Online Steiner Tree with Deletions

SODA, 2014
[
doi
]

CoRR, 1312.7296, 2014
[
url
]
(with Amit Kumar)
Maintaining Assignments Online: Matching, Scheduling, and Flows

SODA, 2014
[
doi
]
(with Amit Kumar and Cliff Stein)
How the Experts Algorithm Can Solve LPs Online

ESA, 2014
[
url doi
]

Math. Oper. Res., 41, 2016
[
url doi
]

CoRR, abs/1407.5298, 2014
[
url
]
(with Marco Molinaro)
Minimum d-dimensional arrangement with fixed points

SODA, 2014
[
doi
]

CoRR, 1307.6627, 2013
[
url
]
(with Anastasios Sidiropoulos)
Changing Bases: Multistage Optimization for Matroids and Matchings

ICALP, 2014
[
url doi
]

CoRR, 1404.3768, 2014
[
url
]
(with Kunal Talwar and Udi Wieder)

2013

Algorithms for Hub Label Optimization

ICALP, 7965, 2013
[
doi
]

{ACM} Trans. Algorithms, 13, 2016
[
url doi
]
(with Babenko, Maxim, Goldberg, Andrew V., Gupta, Anupam and Nagarajan, Viswanath)
Harnessing the Power of Two Crossmatches

14th ACM Conference on Electronic Commerce, 2013
[
doi
]
(with Avrim Blum, Ariel Procaccia and Ankit Sharma)
Catch Them If You Can: How to Serve Impatient Users

Innovations in Theoretical Computer Science Conference, 2013
[
doi
]
(with Marek Cygan, Matthias Englert, Marcin Mucha and Piotr Sankowski)
Packing Interdiction and Partial Covering Problems

Integer Programming and Combinatorial Optimization Conference (IPCO), 2013
[
doi
]
(with Michael Dinitz)
An Improved Integrality Gap for Asymmetric TSP Paths

Integer Programming and Combinatorial Optimization Conference (IPCO), 2013
[
doi
]

Math. Oper. Res., 41, 2016
[
url doi
]

CoRR, abs/1302.3145, 2013
[
url
]
(with Zachary Friggstad and Mohit Singh)
The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online

ACM Symposium on the Theory of Computing (STOC), 2013
[
doi
]

{SIAM} J. Comput., 45, 2016
[
url doi
]

CoRR, abs/1307.3757, 2013
[
url
]
(with Albert Gu and Amit Kumar)
The Approximability of the Binary Paintshop Problem

APPROX-RANDOM, 2013
[
doi
]
(with Satyen Kale, Viswanath Nagarajan, Rishi Saket and Baruch Schieber)
A Stochastic Probing Problem with Applications

Integer Programming and Combinatorial Optimization Conference (IPCO), 2013
[
doi
]

CoRR, 1302.5913, 2013
[
url
]
(with Viswanath Nagarajan)
Thrifty Algorithms for Multistage Robust Optimization

Integer Programming and Combinatorial Optimization Conference (IPCO), 2013
[
doi
]

CoRR, 1302.5445, 2013
[
url
]
(with Viswanath Nagarajan and Vijay V. Vazirani)
Random Rates for 0-Extension and Low-Diameter Decompositions

CoRR, 1307.5582, 2013
[
url
]
(with Kunal Talwar)
On the Non-Uniform Sparsest Cut Problem on Bounded Treewidth Graphs

ACM Symposium on the Theory of Computing (STOC), 2013
[
doi
]

CoRR, 1305.1347, 2013
[
url
]
(with Kunal Talwar and David Witmer)

2012

Multicast Routing for Energy Minimization Using Speed Scaling

First Mediterranean Conference on Algorithms (MedAlg), 2012
[
doi
]
(with Nikhil Bansal, Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs and Cliff Stein)
Parallel Probabilistic Tree Embeddings, k-Median, and Buy-at-Bulk Network Design

SPAA, 2012
[
doi
]
(with Guy E. Blelloch and Kanat Tangwongsan)
Scheduling Heterogeneous Processors Isn't As Easy As You Think

SODA, 2012
[
url
]
(with Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley and Kirk Pruhs)
Approximation Algorithms for Stochastic Orienteering

SODA, 2012
[
url
]

Math. Oper. Res., 40, 2015
[
url doi
]
(with Ravishankar Krishnaswamy, Viswanath Nagarajan and R. Ravi)
Online Primal-Dual For Non-linear Optimization with Applications to Speed Scaling

Workshop on Approximation and Online Algorithms, 7846, 2012
[
doi
]

CoRR, abs/1109.5931, 2011
[
url
]
(with Ravishankar Krishnaswamy and Kirk Pruhs)
The Online Metric Matching Problem for Doubling Metrics

ICALP (1), 2012
[
doi
]
(with Kevin Lewi)
Approximating Sparse Covering Integer Programs Online

ICALP (1), 2012
[
doi
]

Mathematics of Operations Research, 39, 2014
[
url doi
]

CoRR, abs/1205.0175, 2012
[
url
]
(with Viswanath Nagarajan)
Approximation Algorithms for VRP with Stochastic Demands

Operations Research, 60, 2012
[
doi
]
(with Viswanath Nagarajan and R. Ravi)
Iterative Constructions and Private Data Release

TCC, 2012
[
doi
]

CoRR, abs/1107.3731, 2011
[
url
]
(with Aaron Roth and Jonathan Ullman)

2011

Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs

SPAA, 2011
[
doi
]

Theory of Computing Systems (Special Issue for SPAA 2011 papers), 55, 2014
[
doi
]
(with Guy E. Blelloch, Ioannis Koutis, Gary L. Miller, Richard Peng and Kanat Tangwongsan)
Welfare and Profit Maximization with Production Costs

FOCS, 2011
[
doi
]

CoRR, abs/1110.4992, 2011
[
url
]
(with Avrim Blum, Yishay Mansour and Ankit Sharma)
Privately Releasing Conjunctions and the Statistical Query Barrier

ACM Symposium on the Theory of Computing (STOC), 2011
[
doi
]

SIAM J. Comput., 42, 2013
[
doi
]

CoRR, abs/1011.1296, 2010
[
url
]
(with Moritz Hardt, Aaron Roth and Jonathan Ullman)
Approximation algorithms for network design: A survey

Surveys in Operations Research and Management Science, 16, 2011
[
doi
]
(with Jochen K\"{o}nemann)
Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits

Symposium on the Foundations of Computer Science (FOCS), 2011
[
doi
]

CoRR, abs/1102.3749, 2011
[
url
]
(with Ravishankar Krishnaswamy, Marco Molinaro and R. Ravi)

2010

A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover

SODA, 2010
[
doi
]
(with Nikhil Bansal and Ravishankar Krishnaswamy)
When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings

ESA (2), 2010
[
doi
]

Algorithmica, 63, 2012
[
doi
]

CoRR, abs/1008.5356, 2010
[
url
]
(with Nikhil Bansal, Jian Li, Juli{\'a}n Mestre, Viswanath Nagarajan and Atri Rudra)
Vertex Sparsifiers: New Results from Old Techniques

APPROX-RANDOM, 2010
[
doi
]

CoRR, abs/1006.4586, 2010
[
url
]

{SIAM} J. Comput., 43, 2014
[
url doi
]
(with Matthias Englert, Robert Krauthgamer, Harald R{\"a}cke, Inbal Talgam-Cohen and Kunal Talwar)
Discovering pathways by orienting edges in protein interaction networks.

Nucleic Acids Res, 2010
[
doi
]
(with Anthony Gitter, Judith Klein-Seetharaman and Ziv Bar-Joseph)
Scheduling jobs with varying parallelizability to reduce variance

SPAA, 2010
[
doi
]
(with Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley and Kirk Pruhs)
Scalably Scheduling Power-Heterogeneous Processors

ICALP (1), 2010
[
doi
]

CoRR, abs/1105.3748, 2011
[
url
]
(with Ravishankar Krishnaswamy and Kirk Pruhs)
Nonclairvoyantly scheduling power-heterogeneous processors

International Green Computing Conference, 2010
[
doi
]

Sustainable Computing: Informatics and Systems, 1, 2011
[
doi
]
(with Gupta, Anupam, Krishnaswamy, Ravishankar and Pruhs, Kirk)
Tree Embeddings for Two-Edge-Connected Network Design

SODA, 2010
[
doi
]
(with Ravishankar Krishnaswamy and R. Ravi)
Forest Density Estimation

COLT, 2010
[
url
]

Journal of Machine Learning Research, 12, 2011
[
url
]

CoRR, abs/1001.1557, 2010
[
url
]
(with John Lafferty, Han Liu, Larry Wasserman and Min Xu)
Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems

ICALP (1), 2010
[
doi
]

Math. Oper. Res., 42, 2017
[
url doi
]

CoRR, abs/1003.0722, 2010
[
url
]
(with Viswanath Nagarajan and R. Ravi)
Improved Approximation Algorithms for Requirement Cut

Operations Research Letters, 38, 2010
[
doi
]
(with Viswanath Nagarajan and R. Ravi)
Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms

WINE, 2010
[
doi
]

CoRR, abs/1003.1517, 2010
[
url
]
(with Aaron Roth, Grant Schoenebeck and Kunal Talwar)
Coordinated Sampling sans Origin-Destination Identifiers: Algorithms, Analysis, and Evaluation

IEEE Communication Systems and Networks (COMSNETS), 2010
[
doi
]
(with Vyas Sekar, Michael K. Reiter and Hui Zhang)
Network-Wide Deployment of Intrusion Detection and Prevention Systems

ACM CoNEXT, 2010
[
url doi
]
(with Vyas Sekar, Ravishankar Krishnaswamy and Michael K. Reiter)

2009

Secretary problems: weights and discounts

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009
[
doi
]
(with Babaioff, Moshe, Dinitz, Michael, Gupta, Anupam, Immorlica, Nicole and Talwar, Kunal)
Approximate clustering without the approximation

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009
[
doi
]

JACM, 60, 2013
[
doi
]
(with Maria-Florina Balcan and Avrim Blum)
Scheduling with Outliers

International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2009
[
doi
]

CoRR, abs/0906.2020, 2009
[
url
]
(with Ravishankar Krishnaswamy, Amit Kumar and Danny Segev)
Online and stochastic survivable network design

STOC, 2009
[
doi
]

SIAM J. Comput., 41, 2012
[
doi
]
(with Gupta, Anupam, Krishnaswamy, Ravishankar and Ravi, R.)
A constant-factor approximation for stochastic Steiner forest

STOC, 2009
[
doi
]
(with Gupta, Anupam and Kumar, Amit)
Differentially Private Combinatorial Optimization

SODA, 2010
[
doi
]

CoRR, abs/0903.4510, 2009
[
url
]
(with Katrina Ligett, Frank McSherry, Aaron Roth and Kunal Talwar)
Thresholded Covering Algorithms for Robust and Max-min Optimization

ICALP (1), 2010
[
doi
]

{ACM} Trans. Algorithms, 12, 2016
[
url doi
]

Math. Program., 146, 2014
[
url doi
]

CoRR, abs/1012.4962, 2010
[
url
]

CoRR, abs/0912.1045, 2009
[
url
]
(with Viswanath Nagarajan and R. Ravi)
Simultaneous placement and scheduling of sensors

IPSN, 2009
[
doi
]

IEEE Transactions on Automatic Control, 56, 2011
[
doi
]
(with Andreas Krause, Ram Rajagopal and Carlos Guestrin)

2008

A plant location guide for the unsure

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008
[
doi
]

Math. Oper. Res., 35, 2010
[
url doi
]
(with Barbara M. Anthony, Vineet Goyal and Viswanath Nagarajan)
Approximating TSP on metrics with bounded global growth

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008
[
doi
]

SIAM Journal on Computing, 41, 2012
[
doi
]
(with T.-H. Hubert Chan)
Ultra-low-dimensional embeddings for doubling metrics

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008
[
doi
]

J. ACM, 57, 2010
[
doi
]
(with T.-H. Hubert Chan and Kunal Talwar)
Set connectivity problems in undirected graphs and the directed Steiner network problem

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008
[
doi
]

ACM Transactions on Algorithms, 7, 2011
[
doi
]
(with Chandra Chekuri, Guy Even and Danny Segev)
Stochastic analyses for online combinatorial optimization problems

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008
[
doi
]
(with Naveen Garg, Stefano Leonardi and Piotr Sankowski)
All-Norms and All-$L_p$-Norms Approximation Algorithms

Foundations of Software Technology and Theoretical Computer Science (FST\&TCS), 08004, 2008
[
url doi
]
(with Daniel Golovin, Amit Kumar and Kanat Tangwongsan)
Set Covering with our Eyes Closed

Symposium on the Foundations of Computer Science (FOCS), 2008
[
doi
]

SIAM J. Comput., 42, 2013
[
url doi
]
(with Grandoni, Fabrizio, Gupta, Anupam, Leonardi, Stefano, Miettinen, Pauli, Sankowski, Piotr and Singh, Mohit)
Extracting Dynamics from Static Cancer Expression Data

IEEE/ACM Trans. Comput. Biol. Bioinformatics, 5, 2008
[
doi
]
(with Gupta, Anupam and Bar-Joseph, Ziv)
Simpler Analyses of Local Search Algorithms for Facility Location

CoRR, abs/0809.2554, 2008
[
url
]
(with Kanat Tangwongsan)
Selecting Observations against Adversarial Objectives

Advances in Neural Information Processing Systems 20, 2008
[
url
]

Journal of Machine Learning Research, 9, 2008
[
url
]
(with Andreas Krause, Brendan McMahan and Carlos Guestrin)

2007

Infrastructure Leasing Problems

Integer Programming and Combinatorial Optimization Conference (IPCO), 2007
[
doi
]
(with Barbara M. Anthony)
An $O(\log^2 k)$-Competitive Algorithm for Metric Bipartite Matching

Annual European Symposium on Algorithms (ESA), 2007
[
doi
]

Algorithmica, 68, 2014
[
doi
]
(with Nikhil Bansal, Niv Buchbinder and Joseph Naor)
On Configuring BGP Route Reflectors

2nd International Conference on COMmunication System softWAre and MiddlewaRE (COMSWARE), 2007
[
doi
]
(with Yuri Breitbart, Minos N. Garofalakis, Amit Kumar and Rajeev Rastogi)
Pricing Tree Access Networks with Connected Backbones

Annual European Symposium on Algorithms (ESA), 2007
[
doi
]
(with Vineet Goyal, Stefano Leonardi and R. Ravi)
Stochastic Steiner Tree with Non-Uniform Inflation

International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2007
[
doi
]
(with MohammadTaghi Hajiaghayi and Amit Kumar)
Dial a Ride from $k$-Forest

Annual European Symposium on Algorithms (ESA), 2007
[
doi
]

CoRR, abs/0707.0648, 2007
[
url
]

ACM Transactions on Algorithms, 6, 2010
[
doi
]
(with MohammadTaghi Hajiaghayi, Viswanath Nagarajan and R. Ravi)
An Efficient Cost-Sharing Mechanism for the Prize-Collecting Steiner Forest Problem

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007
[
doi
]

Mathematical Programming, 2014
[
url
]
(with Jochen K\"{o}nemann, Stefano Leonardi, R. Ravi and Guido Sch\"{a}fer)
How to Complete a Doubling Metric

Latin American Symposium on Theoretical Informatics, 2008
[
doi
]

Algorithmica, 59, 2011
[
doi
]

CoRR, abs/0712.3331, 2007
[
url
]
(with Kunal Talwar)

2006

Spanners with Slack

ESA, 2006
[
doi
]
(with T.-H. Hubert Chan and Michael Dinitz)
Small hop-diameter sparse spanners for doubling metrics

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006
[
doi
]

Discrete {\&} Computational Geometry, 41, 2009
[
doi
]
(with T.-H. Hubert Chan)
Improved embeddings of graph metrics into random trees (article withdrawn)

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006
[
doi
]
(with Kedar Dhamdhere and Harald R{\"a}cke)
Quorum placement in networks: minimizing network congestion

Annual ACM Symposium on Principles of Distributed Computing (PODC), 2006
[
doi
]
(with Daniel Golovin, Bruce M. Maggs, Florian Oprea and Michael K. Reiter)
Oblivious network design

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006
[
doi
]
(with MohammadTaghi Hajiaghayi and Harald R{\"a}cke)
Approximating unique games

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006
[
doi
]
(with Kunal Talwar)
Near-optimal sensor placements: maximizing information while minimizing communication cost

Conference on Information Processing in Sensor Networks, 2006
[
doi
]

ACM Transactions on Sensor Networks, 7, 2011
[
doi
]
(with Andreas Krause, Carlos Guestrin and Jon M. Kleinberg)

2005

Metric Embeddings with Relaxed Guarantees

Symposium on the Foundations of Computer Science (FOCS), 2005
[
doi
]

SIAM Journal on Computing, 38, 2009
[
doi
]
(with Ittai Abraham, Yair Bartal, T.-H. Hubert Chan, Kedar Dhamdhere, Jon M. Kleinberg, Ofer Neiman and Aleksandrs Slivkins)
Approximation Algorithms for Embeddings Into Low-Dimensional Spaces

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005
[
doi
]

{SIAM} J. Discrete Math., 33, 2019
[
url doi
]
(with Mihai B\u{a}doiu, Kedar Dhamdhere, Yuri Rabinovich, Harald R{\"a}cke, R. Ravi and Anastasios Sidiropoulos)
On Hierarchical Routing in Doubling Metrics

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005
[
doi
]

{ACM} Trans. Algorithms, 12, 2016
[
url doi
]
(with T.-H. Hubert Chan, Bruce M. Maggs and Shuheng Zhou)
Improved Approximations for Sparsest Cut

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005
[
doi
]

ACM Trans. Algorithms, 4, 2008
[
doi
]
(with Shuchi Chawla and Harald R{\"a}cke)
On a bidirected relaxation for the Multiway Cut problem

Discrete Appl. Math., 150, 2005
[
doi
]
(with Chekuri, Chandra, Gupta, Anupam and Kumar, Amit)
On the Approximability of Network Design Problems

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005
[
doi
]

ACM Trans. Algorithms, 4, 2008
[
doi
]
(with Julia Chuzhoy, Joseph (Seffi) Naor and Amitabh Sinha)
Where's the Winner? Max-Finding and Sorting with Metric Costs

International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 3624, 2005
[
doi
]
(with Amit Kumar)
Quorum placement in networks to minimize access delays

Annual ACM Symposium on Principles of Distributed Computing (PODC), 2005
[
doi
]
(with Bruce M. Maggs, Florian Oprea and Michael K. Reiter)
Stochastic Steiner Trees Without a Root

International Colloquium on Automata, Languages and Programming (ICALP), 3580, 2005
[
doi
]
(with Martin P{\'a}l)
What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization

International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 3624, 2005
[
doi
]
(with Martin P{\'a}l, R. Ravi and Amitabh Sinha)

2004

Approximation Algorithms for Minimizing Average Distortion

Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2996, 2004
[
doi
]

Theory of Computing Systems, 39, 2006
[
doi
]
(with Kedar Dhamdhere and R. Ravi)
Boosted Sampling: Approximation algorithms for stochastic optimization problems

ACM Symposium on the Theory of Computing (STOC), 2004
[
doi
]

SIAM J. Comput., 40, 2011
[
doi
]
(with Martin P{\'a}l, R. Ravi and Amitabh Sinha)
An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design.

Symposium on the Foundations of Computer Science (FOCS), 2004
[
doi
]

Mathematics of Operations Research, 32, 2007
[
doi
]
(with R. Ravi and Amitabh Sinha)
Cost-Sharing Mechanisms for Network Design.

International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 3122, 2004
[
doi
]

Algorithmica, 50, 2008
[
doi
]
(with Aravind Srinivasan and \'E}va Tardos)

2003

Lower Bounds for Embedding Edit Distance into Normed Spaces

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003
[
doi
]
(with Alexandr Andoni, Michel Marie Deza, Piotr Indyk and Sofya Raskhodnikova)
Embedding $k$-outerplanar graphs into $\ell_1$

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003
[
doi
]

SIAM J. Discrete Math., 20, 2006
[
doi
]
(with Chandra Chekuri, Ilan Newman, Yuri Rabinovich and Alistair Sinclair)
Improved Approximations for Directed Multicut

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003
[
doi
]
Bounded geometries, fractals, and low--distortion embeddings

Symposium on the Foundations of Computer Science (FOCS), 2003
[
doi
]
(with Robert Krauthgamer and James R.\ Lee)
Approximations via Cost-Sharing

Symposium on the Foundations of Computer Science (FOCS), 2003
[
doi
]

J. ACM, 54, 2007
[
doi
]
(with Amit Kumar, Martin P{\'a}l and Tim Roughgarden)
Exploring the Trade-off between Label Size and Stack Depth in MPLS Routing

Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 1, 2003

(with Amit Kumar and Rajeev Rastogi)
Simpler and Better Approximation Algorithms for Network Design

ACM Symposium on the Theory of Computing (STOC), 2003
[
doi
]
(with Amit Kumar and Tim Roughgarden)
Tree based MPLS routing

Annual ACM symposium on Parallel Algorithms and Architectures (SPAA), 2003
[
doi
]
(with Amit Kumar and Mikkel Thorup)
On the Covering Steiner Problem

Foundations of Software Technology and Theoretical Computer Science (FST\&TCS), 2003
[
doi
]

Theory of Computing, 2, 2006
[
doi
]
(with Aravind Srinivasan)
Counting Inversions in Lists

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003
[
doi
]
(with Francis X. Zane)

2002

Approximation Algorithms for Unsplittable Flow Problems

International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2462, 2002
[
doi
]

Algorithmica, 47, 2007
[
doi
]
(with Amit Chakrabarti, Chandra Chekuri and Amit Kumar)
Building edge-failure resilient networks

Integer Programming and Combinatorial Optimization Conference (IPCO), 2337, 2002
[
doi
]

Algorithmica, 43, 2005
[
doi
]
(with Chandra Chekuri, Amit Kumar, Joseph (Seffi) Naor and Danny Raz)
A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem

Symposium on the Foundations of Computer Science (FOCS), 2002
[
doi
]
(with Amit Kumar and Tim Roughgarden)

2001

Steiner points in tree metrics don't (really) help

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2001
[
doi
]
Sorting and selection with structured costs

Symposium on the Foundations of Computer Science (FOCS), 2001
[
doi
]
(with Amit Kumar)
Provisioning a Virtual Private Network: A Network Design Problem for Multicommodity Flow

STOC, 2001
[
doi
]
(with Amit Kumar, Jon M. Kleinberg, Rajeev Rastogi and B{\"u}lent Yener)
Traveling with a Pez dispenser (or, routing issues in MPLS)

Symposium on the Foundations of Computer Science (FOCS), 2001
[
doi
]

SIAM J. Comput., 34, 2004
[
doi
]
(with Amit Kumar and Rajeev Rastogi)

2000

Improved bandwidth approximation for trees

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000
[
doi
]

J. Algorithms, 40, 2001
[
doi
]
Embeddings of Finite Metrics

Preprint, 2000
A Constant Factor Approximation Algorithm for a Class of Classification Problems

ACM Symposium on the Theory of Computing (STOC), 2000
[
doi
]
(with \'E}va Tardos)

1999

An elementary proof of a theorem of Johnson and Lindenstrauss

Random Structures Algorithms, 22, 2003
[
doi
]

Preprint, 1999
[
url
]
(with Sanjoy Dasgupta)
Embedding tree metrics into low dimensional Euclidean spaces

ACM Symposium on the Theory of Computing (STOC), 1999
[
doi
]

Discrete Comput. Geom., 24, 2000
[
doi
]
Cuts, trees and $\ell_1$-embeddings of graphs

Symposium on the Foundations of Computer Science (FOCS), 1999
[
doi
]

Combinatorica, 24, 2004
[
doi
]
(with Ilan Newman, Yuri Rabinovich and Alistair Sinclair)

>> Publications

2026

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

2000

1999

Designed by Kanat Tangwongsan, mildly altered by AG. Last updated: 2026-01-13.

Designed by Kanat Tangwongsan, mildly altered by AG.
Last updated: 2026-01-13.