>> Publications


DBLP | ACM DL | Google Scholar | BibTeX


    2024


  1. Limited Independence Prophets
    IPCO, 2024
    [
    ]
    (with Jinqiao Hu, Gregory Kehne, Roie Levin)
  2. Max-Cut with $\varepsilon$-Accurate Predictions
    ArXiv, abs/2402.18263, 2024
    [
    url
    ]
    (with Vincent Cohen-Addad, Tommaso d'Orsi, Euiwoong Lee, Debmalya Panigrahi)
  3. Maintaining Matroid Intersections Online
    SODA, 2024
    [
    ]
    ArXiv, abs/2309.10214, 2023
    [
    url
    ]
    (with Niv Buchbinder, Daniel Hathcock, Anna R. Karlin, Sherry Sarkar)
  4. Set Covering with Our Eyes Wide Shut
    SODA, 2024
    [
    ]
    ArXiv, abs/2304.02063, 2023
    [
    url
    ]
    (with Gregory Kehne, Roie Levin)
  5. Poly-logarithmic Competitiveness for the k-Taxi Problem
    SODA, 2024
    [
    ]
    (with Amit Kumar, Debmalya Panigrahi)


  6. 2023


  7. Improving Length-Generalization in Transformers via Task Hinting
    ArXiv, abs/2310.00726, 2023
    [
    url
    ]
    (with Pranjal Awasthi)
  8. Configuration Balancing for Stochastic Requests
    IPCO, 2023
    [
    url
    ]
    (with Franziska Eberle, Nicole Megow, Benjamin Moseley, Rudy Zhou)
  9. Efficient Algorithms and Hardness Results for the Weighted k-Server Problem
    APPROX, 2023
    [
    url
    ]
    ArXiv, abs/2307.11913, 2023
    [
    url
    ]
    (with Amit Kumar, Debmalya Panigrahi)
  10. A Local Search-Based Approach for Set Covering
    ArXiv, abs/2211.04444, 2022
    [
    url
    ]
    SOSA, 2023
    [
    doi
    ]
    (with Euiwoong Lee, Jason Li)
  11. Graph Searching with Predictions
    ArXiv, abs/2212.14220, 2022
    [
    url
    ]
    ITCS, 2023
    [
    ]
    (with Siddhartha Banerjee, Vincent Cohen-Addad, Zhouzi Li)
  12. Minimizing Completion Times for Stochastic Jobs via Batched Free Times
    SODA, 2023
    [
    doi
    ]
    ArXiv, abs/2208.13696, 2022
    [
    url
    ]
    (with Benjamin Moseley, Rudy Zhou)
  13. The Price of Explainability for Clustering
    FOCS, 2023
    [
    url
    ]
    ArXiv, abs/2304.09743, 2023
    [
    url
    ]
    (with Madhusudhan Reddy Pittu, Ola Svensson, Rachel Yuan)


  14. 2022


  15. Augmenting Online Algorithms with $\varepsilon$-Accurate Predictions
    NeurIPS, 2022
    [
    url
    ]
    (with Debmalya Panigrahi, Bernardo Subercaseaux, Kevin Sun)
  16. Learning from a Sample in Online Algorithms
    NeurIPS, 2022
    [
    url
    ]
    (with C.J. Argue, Alan Frieze, Christopher Seiler)
  17. An Improved Local Search Algorithm for k-Median
    SODA, 2022
    [
    url
    ]
    ArXiv, abs/2111.04589, 2021
    [
    url
    ]
    (with Vincent Cohen-Addad, Lunjia Hu, Hoon Oh, David Saulpic)
  18. Robust Secretary and Prophet Algorithms for Packing Integer Programs
    SODA, 2022
    [
    url
    ]
    ArXiv, abs/2112.12920, 2021
    [
    url
    ]
    (with C. J. Argue, Marco Molinaro, Sahil Singla)
  19. Online Discrepancy with Recourse for Vectors and Graphs
    SODA, 2022
    [
    url
    ]
    ArXiv, abs/2111.06308, 2021
    [
    url
    ]
    (with Vijaykrishna Gurunathan, Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla)
  20. Probing to Minimize
    ArXiv, abs/2111.01955, 2021
    [
    url
    ]
    ITCS, 2022
    [
    url
    ]
    (with Weina Wang, Jalani Williams)
  21. Matroid-Based TSP Rounding for Half-Integral Solutions
    IPCO, 2022
    [
    url
    ]
    ArXiv, abs/2111.09290, 2021
    [
    url
    ]
    (with Euiwoong Lee, Jason Li, Marcin Mucha, Heather Newman, Sherry Sarkar)
  22. Non-Adaptive Stochastic Score Classification and Explainable Halfspace Evaluation
    ArXiv, abs/2111.05687, 2021
    [
    url
    ]
    IPCO, 2022
    [
    url
    ]
    (with Rohan Ghuge, Viswanath Nagarajan)


  23. 2021


  24. Random Order Online Set Cover is as Easy as Offline
    FOCS, 2021
    [
    ]
    ArXiv, abs/2111.06842, 2021
    [
    url
    ]
    (with Gregory Kehne, Roie Levin)
  25. A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows
    FOCS, 2021
    [
    ]
    ArXiv, abs/2111.09255, 2021
    [
    url
    ]
    (with Amit Kumar, Debmalya Panigrahi)
  26. The Power of Adaptivity for Stochastic Submodular Cover
    ICML, 2021
    [
    url
    ]
    ArXiv, abs/2106.16115, 2021
    [
    url
    ]
    (with Rohan Ghuge, Viswanath Nagarajan)
  27. Structural Iterative Rounding for Generalized k-Median Problems
    ICALP, 2021
    [
    url
    ]
    (with Benjamin Moseley, Rudy Zhou)
  28. A Quasipolynomial (2 + $\varepsilon$)-Approximation for Planar Sparsest Cut
    STOC, 2021
    [
    url
    ]
    ArXiv, abs/2105.15187, 2021
    [
    url
    ]
    (with Vincent Cohen-Addad, Philip N. Klein, Jason Li)
  29. Lipschitz Selectors may not Yield Competitive Algorithms for Convex Body Chasing
    ArXiv, abs/2104.07487, 2021
    [
    url
    ]
    Discret. Comput. Geom., 70(3):2023
    [
    url
    ]
    (with C. J. Argue, Marco Molinaro)
  30. The Connectivity Threshold for Dense Graphs
    SODA, 2021
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  31. Fair algorithms for selecting citizens' assemblies
    Nature, 596, 2021
    [
    url
    ]
    (with Bailey Flanigan, Paul G\"{olz}, Brett Hennig, Ariel Procaccia)
  32. Bag-Of-Tasks Scheduling on Related Machines
    APPROX, 2021
    [
    url
    ]
    (with Amit Kumar, Sahil Singla)


  33. 2020


  34. Online Carpooling using Expander Decompositions
    ArXiv, abs/2007.10545, 2020
    [
    url
    ]
    FSTTCS, 2020
    [ ]
    (with Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla)
  35. Neutralizing Self-Selection Bias in Sampling for Sortition
    NeurIPS, 2020
    [
    url
    ]
    ArXiv, abs/2006.10498, 2020
    [
    url
    ]
    (with Bailey Flanigan, Paul Goelz, Ariel D. Procaccia)
  36. Fully-Dynamic Submodular Cover with Bounded Recourse
    ArXiv, abs/2009.00800, 2020
    [
    url
    ]
    FOCS, 2020
    [
    ]
    (with Roie Levin)
  37. Random-Order Models
    [
    url
    ]
    ArXiv, abs/2002.12159, 2020
    [
    url
    ]
    (with Sahil Singla)
  38. Dimension-Free Bounds on Chasing Convex Functions
    ArXiv, abs/2005.14058, 2020
    [
    url
    ]
    COLT, 2020
    [
    url
    ]
    (with C. J. Argue, Guru Guruganesh)
  39. Optimal Bounds for the $k$-cut Problem
    J. ACM, 69(1):2022
    [
    url
    ]
    ArXiv, abs/2005.08301, 2020
    [
    url
    ]
    (with David G. Harris, Euiwoong Lee, Jason Li)
  40. The Online Submodular Cover Problem
    SODA, 2020
    [ ]
    (with Roie Levin)
  41. Chasing Convex Bodies with Linear Competitive Ratio
    J. ACM, 68(5):2021
    [
    url
    ]
    SODA, 2020
    [ ]
    ArXiv, abs/1905.11877, 2019
    [
    url
    ]
    (with C. J. Argue, Guru Guruganesh, Ziye Tang)
  42. Stochastic makespan minimization in structured set systems
    Math. Program., 192(1):2022
    [
    url
    ]
    IPCO, 2020
    [ ]
    ArXiv, abs/2002.11153, 2020
    [
    url
    ]
    (with Amit Kumar, Viswanath Nagarajan, Xiangkun Shen)
  43. Robust Algorithms for the Secretary Problem
    ArXiv, abs/1911.07352, 2019
    [
    url
    ]
    ITCS, 2020
    [ ]
    (with Domagoj Bradac, Sahil Singla, Goran Zuzic)
  44. The Karger-Stein Algorithm is Optimal for {$k$}-Cut
    STOC, 2020
    [ ]
    ArXiv, abs/1911.09165, 2019
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  45. Caching with Time Windows and Delays
    SIAM J. Comput., 51(4):2022
    [
    url
    ]
    ArXiv, abs/2006.09665, 2020
    [
    url
    ]
    STOC, 2020
    [ ]
    (with Amit Kumar, Debmalya Panigrahi)


  46. 2019


  47. Potential-Function Proofs for Gradient Methods
    Theory of Computing, 15(4):2019
    [ ]
    ArXiv, abs/1712.04581, 2017
    [
    url
    ]
    (with Nikhil Bansal)
  48. The number of minimum k-cuts: improving the Karger-{Stein} bound
    STOC, 2019
    [
    url
    ]
    ArXiv, abs/1906.00417, 2019
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  49. Stochastic Online Metric Matching
    ICALP, 2019
    [ ]
    ArXiv, abs/1904.09284, 2019
    [
    url
    ]
    (with Guru Guruganesh, Binghui Peng, David Wajc)
  50. Non-clairvoyant Precedence Constrained Scheduling
    ArXiv, abs/1905.02133, 2019
    [
    url
    ]
    ICALP, 2019
    [ ]
    (with Naveen Garg, Amit Kumar, Sahil Singla)
  51. Tight FPT Approximations for {$k$}-Median and k-Means
    ArXiv, abs/1904.12334, 2019
    [
    url
    ]
    ICALP, 2019
    [ ]
    (with Vincent Cohen-Addad, Amit Kumar, Euiwoong Lee, Jason Li)
  52. Better Algorithms for Stochastic Bandits with Adversarial Corruptions
    COLT, 2019
    [
    url
    ]
    ArXiv, abs/1902.08647, 2019
    [
    url
    ]
    (with Tomer Koren, Kunal Talwar)
  53. The Markovian Price of Information
    ArXiv, abs/1902.07856, 2019
    [
    url
    ]
    IPCO, 2019
    [ ]
    (with Haotian Jiang, Ziv Scully, Sahil Singla)
  54. Losing Treewidth by Separating Subsets
    SODA, 2019
    [ ]
    ArXiv, abs/1804.01366, 2018
    [
    url
    ]
    (with Euiwoong Lee, Jason Li, Pasin Manurangsi, Michal Wlodarczyk)
  55. Elastic Caching
    SODA, 2019
    [ ]
    (with Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi)
  56. k-Servers with a Smile: Online Algorithms via Projections
    ArXiv, abs/1810.07508, 2018
    [
    url
    ]
    SODA, 2019
    [ ]
    (with Niv Buchbinder, Marco Molinaro, Joseph Naor)
  57. A Nearly-Linear Bound for Chasing Nested Convex Bodies
    SODA, 2019
    [ ]
    ArXiv, abs/1806.08865, 2018
    [
    url
    ]
    (with C. J. Argue, S\'{e}bastien Bubeck, Michael B. Cohen, Yin Tat Lee)


  58. 2018


  59. Faster Exact and Approximate Algorithms for k-Cut
    FOCS, 2018
    [ ]
    ArXiv, abs/1807.08144, 2018
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  60. Maximizing Profit with Convex Costs in the Random-order Model
    ICALP, 2018
    [
    url
    ]
    ArXiv, abs/1804.08172, 2018
    [
    url
    ]
    (with Ruta Mehta, Marco Molinaro)
  61. Non-Preemptive Flow-Time Minimization via Rejections
    ICALP, 2018
    [
    url
    ]
    ArXiv, abs/1805.09602, 2018
    [
    url
    ]
    (with Amit Kumar, Jason Li)
  62. Fully-Dynamic Bin Packing with Little Repacking
    ICALP, 2018
    [
    url
    ]
    ArXiv, abs/1711.02078, 2017
    [
    url
    ]
    (with Bj\"{o}rn Feldkord, Matthias Feldotto, Guru Guruganesh, Amit Kumar, S\"{o}ren Riechers, David Wajc)
  63. Metric Embedding via Shortest Path Decompositions
    SIAM J. Comput., 51(2):2022
    [
    url
    ]
    ArXiv, abs/1708.04073, 2017
    [
    url
    ]
    STOC, 2018
    [
    url
    ]
    (with Ittai Abraham, Arnold Filtser, Ofer Neiman)
  64. An FPT Algorithm Beating 2-Approximation for {$k$}-Cut
    SODA, 2018
    [ ]
    ArXiv, abs/1710.08488, 2017
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  65. Stochastic Load Balancing on Unrelated Machines
    Math. Oper. Res., 46(1):2021
    [ ]
    SODA, 2018
    [ ]
    ArXiv, abs/1904.07271, 2019
    [
    url
    ]
    (with Amit Kumar, Viswanath Nagarajan, Xiangkun Shen)
  66. A Local-Search Algorithm for Steiner Forest
    ITCS, 2018
    [ ]
    ArXiv, abs/1707.02753, 2017
    [
    url
    ]
    (with Martin Gro\ss, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt, Jos\'{e} Verschae)


  67. 2017


  68. Stochastic Unsplittable Flows
    APPROX, 2017
    [ ]
    (with Archit Karandikar)
  69. Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
    ArXiv, abs/1706.01081, 2017
    [
    url
    ]
    COLT, 2017
    [
    url
    ]
    (with Lijie Chen, Jian Li, Mingda Qiao, Ruosong Wang)
  70. Online and Dynamic Algorithms for Set Cover
    STOC, 2017
    [
    url
    ]
    ArXiv, abs/1611.05646, 2016
    [
    url
    ]
    (with Amit Kumar, Ravishankar Krishnaswamy, Debmalya Panigrahi)
  71. LAST but not Least: Online Spanners for Buy-at-Bulk
    SODA, 2017
    [ ]
    ArXiv, abs/1611.00052, 2016
    [
    url
    ]
    (with R. Ravi, Kunal Talwar, Seeun William Umboh)
  72. Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
    SODA, 2017
    [ ]
    (with Viswanath Nagarajan, Sahil Singla)


  73. 2016


  74. Online Packing and Covering Framework with Convex Objectives
    ArXiv, abs/1412.8347, 2014
    [
    url
    ]
    (with Niv Buchbinder, Shahar Chen, Viswanath Nagarajan, Joseph (Seffi) Naor)
  75. Online Algorithms for Covering and Packing Problems with Convex Objectives
    FOCS, 2016
    [ ]
    (with Yossi Azar, Niv Buchbinder, T.-H. Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor, Debmalya Panigrahi)
  76. Pure Exploration of Multi-armed Bandit Under Matroid Constraints
    ArXiv, abs/1605.07162, 2016
    [
    url
    ]
    COLT, 2016
    [
    url
    ]
    (with Lijie Chen, Jian Li)
  77. Approximation algorithms for aversion $k$-clustering via local {$k$}-median
    ICALP, 2016
    [ ]
    (with Guru Guruganesh, Melanie Schmidt)
  78. Algorithms and Adaptivity Gaps for Stochastic Probing
    SODA, 2016
    [ ]
    (with Viswanath Nagarajan, Sahil Singla)


  79. 2015


  80. A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs
    APPROX-RANDOM, 2015
    [ ]
    (with Nikhil Bansal, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, Clifford Stein)
  81. Greedy Algorithms for Steiner Forest
    ArXiv, abs/1412.7693, 2015
    [
    url
    ]
    STOC, 2015
    [ ]
    (with Amit Kumar)
  82. On the Lov\'{a}sz Theta Function for Independent Sets in Sparse Graphs
    SIAM J. Comput., 47(3):2018
    [
    url
    ]
    STOC, 2015
    [ ]
    ArXiv, abs/1504.04767, 2015
    [
    url
    ]
    (with Nikhil Bansal, Guru Guruganesh)


  83. 2014


  84. How the Experts Algorithm Can Help Solve LPs Online
    Math. Oper. Res., 41(4):2016
    [ ]
    ArXiv, abs/1407.5298, 2014
    [
    url
    ]
    ESA, 2014
    [ ]
    (with Marco Molinaro)
  85. Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
    SIAM J. Comput., 48(3):2019
    [ ]
    ArXiv, abs/1311.3048, 2013
    [
    url
    ]
    STOC, 2014
    [ ]
    (with Ittai Abraham, Cyril Gavoille, Ofer Neiman, Kunal Talwar)
  86. Changing Bases: Multistage Optimization for Matroids and Matchings
    ArXiv, 1404.3768, 2014
    [
    url
    ]
    ICALP, 2014
    [ ]
    (with Kunal Talwar, Udi Wieder)
  87. Minimum d-dimensional arrangement with fixed points
    SODA, 2014
    [
    doi
    ]
    ArXiv, 1307.6627, 2013
    [
    url
    ]
    (with Anastasios Sidiropoulos)
  88. Online Steiner Tree with Deletions
    SODA, 2014
    [
    doi
    ]
    ArXiv, 1312.7296, 2014
    [
    url
    ]
    (with Amit Kumar)
  89. Towards $(1+\epsilon)$-Approximate Flow Sparsifiers
    SODA, 2014
    [
    doi
    ]
    ArXiv, 1310.3252, 2013
    [
    url
    ]
    (with Alexandr Andoni, Robert Krauthgamer)
  90. Maintaining Assignments Online: Matching, Scheduling, and Flows
    SODA, 2014
    [
    doi
    ]
    (with Amit Kumar, Cliff Stein)


  91. 2013


  92. Random Rates for 0-Extension and Low-Diameter Decompositions
    ArXiv, 1307.5582, 2013
    [
    url
    ]
    (with Kunal Talwar)
  93. Harnessing the Power of Two Crossmatches
    14th ACM Conference on Electronic Commerce, 2013
    [
    doi
    ]
    (with Avrim Blum, Ariel Procaccia, Ankit Sharma)
  94. Algorithms for Hub Label Optimization
    ACM Trans. Algorithms, 13(1):2016
    [ ]
    ICALP, 2013
    [
    doi
    ]
    (with Maxim A. Babenko, Andrew V. Goldberg, Viswanath Nagarajan)
  95. On the Non-Uniform Sparsest Cut Problem on Bounded Treewidth Graphs
    STOC, 2013
    [
    doi
    ]
    ArXiv, 1305.1347, 2013
    [
    url
    ]
    (with Kunal Talwar, David Witmer)
  96. The Approximability of the Binary Paintshop Problem
    APPROX-RANDOM, 2013
    [
    doi
    ]
    (with Satyen Kale, Viswanath Nagarajan, Rishi Saket, Baruch Schieber)
  97. The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
    SIAM J. Comput., 45(1):2016
    [ ]
    ArXiv, abs/1307.3757, 2013
    [
    url
    ]
    STOC, 2013
    [ ]
    (with Albert Gu, Amit Kumar)
  98. Thrifty Algorithms for Multistage Robust Optimization
    IPCO, 2013
    [
    doi
    ]
    ArXiv, 1302.5445, 2013
    [
    url
    ]
    (with Viswanath Nagarajan, Vijay V. Vazirani)
  99. A Stochastic Probing Problem with Applications
    IPCO, 2013
    [
    doi
    ]
    ArXiv, 1302.5913, 2013
    [
    url
    ]
    (with Viswanath Nagarajan)
  100. An Improved Integrality Gap for Asymmetric TSP Paths
    Math. Oper. Res., 41(3):2016
    [ ]
    ArXiv, abs/1302.3145, 2013
    [
    url
    ]
    IPCO, 2013
    [
    doi
    ]
    (with Zachary Friggstad, Mohit Singh)
  101. Packing Interdiction and Partial Covering Problems
    IPCO, 2013
    [
    doi
    ]
    (with Michael Dinitz)
  102. Catch Them If You Can: How to Serve Impatient Users
    Innovations in Theoretical Computer Science Conference, 2013
    [ ]
    (with Marek Cygan, Matthias Englert, Marcin Mucha, Piotr Sankowski)


  103. 2012


  104. 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, Cliff Stein)
  105. Online Primal-Dual For Non-linear Optimization with Applications to Speed Scaling
    Workshop on Approximation and Online Algorithms, 2012
    [
    doi
    ]
    ArXiv, abs/1109.5931, 2011
    [
    url
    ]
    (with Ravishankar Krishnaswamy, Kirk Pruhs)
  106. Parallel Probabilistic Tree Embeddings, k-Median, and Buy-at-Bulk Network Design
    SPAA, 2012
    [
    doi
    ]
    (with Guy E. Blelloch, Kanat Tangwongsan)
  107. The Online Metric Matching Problem for Doubling Metrics
    ICALP (1), 2012
    [
    doi
    ]
    (with Kevin Lewi)
  108. Approximating Sparse Covering Integer Programs Online
    Mathematics of Operations Research, 39(4):2014
    [ ]
    ICALP (1), 2012
    [
    doi
    ]
    ArXiv, abs/1205.0175, 2012
    [
    url
    ]
    (with Viswanath Nagarajan)
  109. Iterative Constructions and Private Data Release
    TCC, 2012
    [
    doi
    ]
    ArXiv, abs/1107.3731, 2011
    [
    url
    ]
    (with Aaron Roth, Jonathan Ullman)
  110. Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
    Math. Oper. Res., 40(1):2015
    [ ]
    SODA, 2012
    [
    url
    ]
    (with Ravishankar Krishnaswamy, Viswanath Nagarajan, R. Ravi)
  111. Scheduling Heterogeneous Processors Isn't As Easy As You Think
    SODA, 2012
    [
    url
    ]
    (with Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs)
  112. Approximation Algorithms for VRP with Stochastic Demands
    Operations Research, 60(1):2012
    [
    doi
    ]
    (with Viswanath Nagarajan, R. Ravi)


  113. 2011


  114. Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits
    ArXiv, abs/1102.3749, 2011
    [
    url
    ]
    FOCS, 2011
    [
    doi
    ]
    (with Ravishankar Krishnaswamy, Marco Molinaro, R. Ravi)
  115. Welfare and Profit Maximization with Production Costs
    ArXiv, abs/1110.4992, 2011
    [
    url
    ]
    FOCS, 2011
    [
    doi
    ]
    (with Avrim Blum, Yishay Mansour, Ankit Sharma)
  116. Privately Releasing Conjunctions and the Statistical Query Barrier
    SIAM J. Comput., 42(4):2013
    [
    doi
    ]
    ArXiv, abs/1011.1296, 2010
    [
    url
    ]
    STOC, 2011
    [
    doi
    ]
    (with Moritz Hardt, Aaron Roth, Jonathan Ullman)
  117. Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs
    Theory of Computing Systems (Special Issue for SPAA 2011 papers), 55(3):2014
    [
    doi
    ]
    SPAA, 2011
    [
    doi
    ]
    (with Guy E. Blelloch, Ioannis Koutis, Gary L. Miller, Richard Peng, Kanat Tangwongsan)
  118. Approximation algorithms for network design: A survey
    Surveys in Operations Research and Management Science, 16(1):2011
    [ ]
    (with Jochen Könemann)


  119. 2010


  120. Discovering pathways by orienting edges in protein interaction networks.
    Nucleic Acids Res, 2010
    [
    doi
    ]
    (with Anthony Gitter, Judith Klein-Seetharaman, Ziv Bar-Joseph)
  121. Network-Wide Deployment of Intrusion Detection and Prevention Systems
    ACM CoNEXT, 2010
    [ ]
    (with Vyas Sekar, Ravishankar Krishnaswamy, Michael K. Reiter)
  122. Coordinated Sampling sans Origin-Destination Identifiers: Algorithms, Analysis, and Evaluation
    IEEE Communication Systems and Networks (COMSNETS), 2010
    [
    doi
    ]
    (with Vyas Sekar, Michael K. Reiter, Hui Zhang)
  123. Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms
    WINE, 2010
    [
    doi
    ]
    ArXiv, abs/1003.1517, 2010
    [
    url
    ]
    (with Aaron Roth, Grant Schoenebeck, Kunal Talwar)
  124. Improved Approximation Algorithms for Requirement Cut
    Operations Research Letters, 38(4):2010
    [
    doi
    ]
    (with Viswanath Nagarajan, R. Ravi)
  125. Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
    Math. Oper. Res., 42(3):2017
    [ ]
    ICALP (1), 2010
    [
    doi
    ]
    ArXiv, abs/1003.0722, 2010
    [
    url
    ]
    (with Viswanath Nagarajan, R. Ravi)
  126. Forest Density Estimation
    COLT, 2010
    [
    url
    ]
    ArXiv, abs/1001.1557, 2010
    [
    url
    ]
    Journal of Machine Learning Research, 12, 2011
    [
    url
    ]
    (with John Lafferty, Han Liu, Larry Wasserman, Min Xu)
  127. Tree Embeddings for Two-Edge-Connected Network Design
    SODA, 2010
    [
    doi
    ]
    (with Ravishankar Krishnaswamy, R. Ravi)
  128. Nonclairvoyantly scheduling power-heterogeneous processors
    Sustainable Computing: Informatics and Systems, 1(3):2011
    [
    doi
    ]
    International Green Computing Conference, 2010
    [ ]
    (with Ravishankar Krishnaswamy, Kirk Pruhs)
  129. Scalably Scheduling Power-Heterogeneous Processors
    ICALP (1), 2010
    [
    doi
    ]
    ArXiv, abs/1105.3748, 2011
    [
    url
    ]
    (with Ravishankar Krishnaswamy, Kirk Pruhs)
  130. Scheduling jobs with varying parallelizability to reduce variance
    SPAA, 2010
    [ ]
    (with Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs)
  131. Vertex Sparsifiers: New Results from Old Techniques
    APPROX-RANDOM, 2010
    [
    doi
    ]
    SIAM J. Comput., 43(4):2014
    [ ]
    ArXiv, abs/1006.4586, 2010
    [
    url
    ]
    (with Matthias Englert, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, Kunal Talwar)
  132. When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
    Algorithmica, 63(4):2012
    [
    doi
    ]
    ArXiv, abs/1008.5356, 2010
    [
    url
    ]
    ESA (2), 2010
    [
    doi
    ]
    (with Nikhil Bansal, Jian Li, Julián Mestre, Viswanath Nagarajan, Atri Rudra)
  133. A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover
    SODA, 2010
    [
    doi
    ]
    (with Nikhil Bansal, Ravishankar Krishnaswamy)


  134. 2009


  135. Simultaneous Optimization of Sensor Placements and Balanced Schedules
    IEEE Transactions on Automatic Control, 56(10):2011
    [
    doi
    ]
    IPSN, 2009
    [
    doi
    ]
    (with Andreas Krause, Ram Rajagopal, Carlos Guestrin)
  136. Thresholded Covering Algorithms for Robust and Max-Min Optimization
    ArXiv, abs/0912.1045, 2009
    [
    url
    ]
    ACM Trans. Algorithms, 12(1):2016
    [ ]
    ArXiv, abs/1012.4962, 2010
    [
    url
    ]
    ICALP (1), 2010
    [
    doi
    ]
    Math. Program., 146(1-2):2014
    [ ]
    (with Viswanath Nagarajan, R. Ravi)
  137. Differentially Private Approximation Algorithms
    ArXiv, abs/0903.4510, 2009
    [
    url
    ]
    SODA, 2010
    [
    doi
    ]
    (with Katrina Ligett, Frank McSherry, Aaron Roth, Kunal Talwar)
  138. A constant-factor approximation for stochastic Steiner forest
    STOC, 2009
    [ ]
    (with Amit Kumar)
  139. Online and Stochastic Survivable Network Design
    SIAM J. Comput., 41(6):2012
    [
    doi
    ]
    STOC, 2009
    [ ]
    (with Ravishankar Krishnaswamy, R. Ravi)
  140. Scheduling with Outliers
    ArXiv, abs/0906.2020, 2009
    [
    url
    ]
    APPROX, 2009
    [
    doi
    ]
    (with Ravishankar Krishnaswamy, Amit Kumar, Danny Segev)
  141. Clustering under approximation stability
    JACM, 60(2):2013
    [
    doi
    ]
    SODA, 2009
    [ ]
    (with Maria-Florina Balcan, Avrim Blum)
  142. Secretary problems: weights and discounts
    SODA, 2009
    [ ]
    (with Moshe Babaioff, Michael Dinitz, Nicole Immorlica, Kunal Talwar)


  143. 2008


  144. 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, Carlos Guestrin)
  145. Simpler Analyses of Local Search Algorithms for Facility Location
    ArXiv, abs/0809.2554, 2008
    [
    url
    ]
    (with Kanat Tangwongsan)
  146. Extracting Dynamics from Static Cancer Expression Data
    IEEE/ACM Trans. Comput. Biol. Bioinformatics, 5(2):2008
    [
    doi
    ]
    (with Ziv Bar-Joseph)
  147. Set covering with our eyes closed
    SIAM J. Comput., 42(3):2013
    [ ]
    FOCS, 2008
    [ ]
    (with Fabrizio Grandoni, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, Mohit Singh)
  148. All-Norms and All-$L_p$-Norms Approximation Algorithms
    FST&TCS, 2008
    [ ]
    (with Daniel Golovin, Amit Kumar, Kanat Tangwongsan)
  149. Stochastic analyses for online combinatorial optimization problems
    SODA, 2008
    [ ]
    (with Naveen Garg, Stefano Leonardi, Piotr Sankowski)
  150. Set connectivity problems in undirected graphs and the directed Steiner network problem
    SODA, 2008
    [ ]
    ACM Transactions on Algorithms, 7(2):2011
    [
    doi
    ]
    (with Chandra Chekuri, Guy Even, Danny Segev)
  151. Ultra-low-dimensional embeddings for doubling metrics
    SODA, 2008
    [ ]
    J. ACM, 57(4):2010
    [
    doi
    ]
    (with T.-H. Hubert Chan, Kunal Talwar)
  152. Approximating TSP on Metrics with Bounded Global Growth
    SIAM Journal on Computing, 41(3):2012
    [
    doi
    ]
    SODA, 2008
    [ ]
    (with T.-H. Hubert Chan)
  153. A plant location guide for the unsure
    SODA, 2008
    [ ]
    Math. Oper. Res., 35(1):2010
    [ ]
    (with Barbara M. Anthony, Vineet Goyal, Viswanath Nagarajan)


  154. 2007


  155. How to Complete a Doubling Metric
    ArXiv, abs/0712.3331, 2007
    [
    url
    ]
    LATIN, 2008
    [
    doi
    ]
    Algorithmica, 59(1):2011
    [
    doi
    ]
    (with Kunal Talwar)
  156. An Efficient Cost-Sharing Mechanism for the Prize-Collecting Steiner Forest Problem
    Mathematical Programming, 2014
    [
    url
    ]
    SODA, 2007
    [ ]
    (with Jochen Könemann, Stefano Leonardi, R. Ravi, Guido Schäfer)
  157. Dial a Ride from k-forest
    ArXiv, abs/0707.0648, 2007
    [
    url
    ]
    ACM Transactions on Algorithms, 6(2):2010
    [
    doi
    ]
    ESA, 2007
    [
    doi
    ]
    (with MohammadTaghi Hajiaghayi, Viswanath Nagarajan, R. Ravi)
  158. Stochastic Steiner Tree with Non-Uniform Inflation
    APPROX, 2007
    [ ]
    (with MohammadTaghi Hajiaghayi, Amit Kumar)
  159. Pricing Tree Access Networks with Connected Backbones
    ESA, 2007
    [ ]
    (with Vineet Goyal, Stefano Leonardi, R. Ravi)
  160. 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, Rajeev Rastogi)
  161. A Randomized $O(\log^2 k)$-Competitive Algorithm for Metric Bipartite Matching
    Algorithmica, 68(2):2014
    [
    doi
    ]
    ESA, 2007
    [ ]
    (with Nikhil Bansal, Niv Buchbinder, Joseph Naor)
  162. Infrastructure Leasing Problems
    IPCO, 2007
    [ ]
    (with Barbara M. Anthony)


  163. 2006


  164. 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(4):2011
    [
    doi
    ]
    (with Andreas Krause, Carlos Guestrin, Jon M. Kleinberg)
  165. Approximating unique games
    SODA, 2006
    [ ]
    (with Kunal Talwar)
  166. Oblivious network design
    SODA, 2006
    [ ]
    (with MohammadTaghi Hajiaghayi, Harald Räcke)
  167. Quorum placement in networks: minimizing network congestion
    PODC, 2006
    [ ]
    (with Daniel Golovin, Bruce M. Maggs, Florian Oprea, Michael K. Reiter)
  168. Improved embeddings of graph metrics into random trees (article withdrawn)
    SODA, 2006
    [
    doi
    ]
    (with Kedar Dhamdhere, Harald Räcke)
  169. Small hop-diameter sparse spanners for doubling metrics
    SODA, 2006
    [ ]
    Discrete & Computational Geometry, 41(1):2009
    [
    doi
    ]
    (with T.-H. Hubert Chan)
  170. Spanners with Slack
    ESA, 2006
    [ ]
    (with T.-H. Hubert Chan, Michael Dinitz)


  171. 2005


  172. What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization
    APPROX, 2005
    [ ]
    (with Martin Pál, R. Ravi, Amitabh Sinha)
  173. Stochastic Steiner Trees Without a Root
    ICALP, 2005
    [ ]
    (with Martin Pál)
  174. Quorum placement in networks to minimize access delays
    PODC, 2005
    [ ]
    (with Bruce M. Maggs, Florian Oprea, Michael K. Reiter)
  175. Where's the Winner? Max-Finding and Sorting with Metric Costs
    APPROX, 2005
    [ ]
    (with Amit Kumar)
  176. On the Approximability of Network Design Problems
    SODA, 2005
    [ ]
    ACM Trans. Algorithms, 4(2):2008
    [
    doi
    ]
    (with Julia Chuzhoy, Joseph (Seffi) Naor, Amitabh Sinha)
  177. On a bidirected relaxation for the Multiway {Cut} problem
    Discrete Appl. Math., 150(1-3):2005
    [
    doi
    ]
    (with Chandra Chekuri, Amit Kumar)
  178. Improved Approximations for Sparsest {Cut}
    SODA, 2005
    [ ]
    ACM Trans. Algorithms, 4(2):2008
    [
    doi
    ]
    (with Shuchi Chawla, Harald Räcke)
  179. On Hierarchical Routing in Doubling Metrics
    ACM Trans. Algorithms, 12(4):2016
    [ ]
    SODA, 2005
    [ ]
    (with T.-H. Hubert Chan, Bruce M. Maggs, Shuheng Zhou)
  180. Approximation Algorithms for Embeddings Into Low-Dimensional Spaces
    SODA, 2005
    [ ]
    SIAM J. Discrete Math., 33(1):2019
    [ ]
    (with Mihai B\uadoiu, Kedar Dhamdhere, Yuri Rabinovich, Harald Räcke, R. Ravi, Anastasios Sidiropoulos)
  181. Metric Embeddings with Relaxed Guarantees
    FOCS, 2005
    [ ]
    SIAM Journal on Computing, 38(6):2009
    [
    doi
    ]
    (with Ittai Abraham, Yair Bartal, T.-H. Hubert Chan, Kedar Dhamdhere, Jon M. Kleinberg, Ofer Neiman, Aleksandrs Slivkins)


  182. 2004


  183. Cost-Sharing Mechanisms for Network Design.
    APPROX, 2004
    [ ]
    Algorithmica, 50(1):2008
    [
    doi
    ]
    (with Aravind Srinivasan, \'Eva Tardos)
  184. An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design.
    FOCS, 2004
    [ ]
    Mathematics of Operations Research, 32(2):2007
    [
    doi
    ]
    (with R. Ravi, Amitabh Sinha)
  185. Sampling and cost-sharing: approximation algorithms for stochastic optimization problems
    SIAM J. Comput., 40(5):2011
    [
    doi
    ]
    STOC, 2004
    [ ]
    (with Martin Pál, R. Ravi, Amitabh Sinha)
  186. Approximation Algorithms for Minimizing Average Distortion
    STACS, 2004
    [ ]
    Theory of Computing Systems, 39(1):2006
    [
    doi
    ]
    (with Kedar Dhamdhere, R. Ravi)


  187. 2003


  188. Counting Inversions in Lists
    SODA, 2003
    [ ]
    (with Francis X. Zane)
  189. On the Covering {Steiner} Problem
    FST&TCS, 2003
    [ ]
    Theory of Computing, 2, 2006
    [
    doi
    ]
    (with Aravind Srinivasan)
  190. Tree based MPLS routing
    SPAA, 2003
    [
    doi
    ]
    (with Amit Kumar, Mikkel Thorup)
  191. Simpler and Better Approximation Algorithms for Network Design
    STOC, 2003
    [ ]
    (with Amit Kumar, Tim Roughgarden)
  192. Exploring the Trade-off between Label Size and Stack Depth in MPLS Routing
    INFOCOM, 2003
    [
    ]
    (with Amit Kumar, Rajeev Rastogi)
  193. Approximations via Cost-Sharing
    FOCS, 2003
    [ ]
    J. ACM, 54(3):2007
    [
    doi
    ]
    (with Amit Kumar, Martin Pál, Tim Roughgarden)
  194. Bounded geometries, fractals, and low--distortion embeddings
    FOCS, 2003
    [ ]
    (with Robert Krauthgamer, James R. Lee)
  195. Improved Approximations for Directed Multicut
    SODA, 2003
    [ ]
  196. Embedding $k$-outerplanar graphs into $\ell_1$
    SODA, 2003
    [ ]
    SIAM J. Discrete Math., 20(1):2006
    [
    doi
    ]
    (with Chandra Chekuri, Ilan Newman, Yuri Rabinovich, Alistair Sinclair)
  197. Lower Bounds for Embedding Edit Distance into Normed Spaces
    SODA, 2003
    [ ]
    (with Alexandr Andoni, Michel Marie Deza, Piotr Indyk, Sofya Raskhodnikova)


  198. 2002


  199. A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem
    FOCS, 2002
    [ ]
    (with Amit Kumar, Tim Roughgarden)
  200. Building edge-failure resilient networks
    IPCO, 2002
    [ ]
    Algorithmica, 43(1-2):2005
    [
    doi
    ]
    (with Chandra Chekuri, Amit Kumar, Joseph (Seffi) Naor, Danny Raz)
  201. Approximation Algorithms for Unsplittable Flow Problems
    APPROX, 2002
    [ ]
    Algorithmica, 47(1):2007
    [
    doi
    ]
    (with Amit Chakrabarti, Chandra Chekuri, Amit Kumar)


  202. 2001


  203. Traveling with a Pez dispenser (or, routing issues in {MPLS})
    FOCS, 2001
    [ ]
    SIAM J. Comput., 34(2):2004
    [
    doi
    ]
    (with Amit Kumar, Rajeev Rastogi)
  204. Provisioning a Virtual Private Network: {A} Network Design Problem for Multicommodity Flow
    STOC, 2001
    [ ]
    (with Amit Kumar, Jon M. Kleinberg, Rajeev Rastogi, Bülent Yener)
  205. Sorting and selection with structured costs
    FOCS, 2001
    [ ]
    (with Amit Kumar)
  206. Steiner points in tree metrics don't (really) help
    SODA, 2001
    [ ]


  207. 2000


  208. A Constant Factor Approximation Algorithm for a Class of Classification Problems
    STOC, 2000
    [ ]
    (with \'Eva Tardos)
  209. Embeddings of Finite Metrics
    Ph.D. Thesis, University of California, Berkeley, 2000
    [
    ]
  210. Improved bandwidth approximation for trees
    SODA, 2000
    [ ]
    J. Algorithms, 40(1):2001
    [
    doi
    ]


  211. 1999


  212. Cuts, trees and $\ell_1$-embeddings of graphs
    FOCS, 1999
    [ ]
    Combinatorica, 24(2):2004
    [
    doi
    ]
    (with Ilan Newman, Yuri Rabinovich, Alistair Sinclair)
  213. Embedding tree metrics into low dimensional Euclidean spaces
    STOC, 1999
    [ ]
    Discrete Comput. Geom., 24(1):2000
    [
    doi
    ]
  214. A simple proof of the Johnson-Lindenstrauss lemma
    Tech report, International Computer Science Institute, 1999
    [
    url
    ]
    Random Structures Algorithms, 22(1):2003
    [ ]
    (with Sanjoy Dasgupta)

Designed by Kanat Tangwongsan, mildly altered by AG.
Last updated: 2024-03-03.