>> 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


  6. Improving Length-Generalization in Transformers via Task Hinting
    ArXiv, abs/2310.00726, 2023
    [
    url
    ]
    (with Pranjal Awasthi)
  7. Configuration Balancing for Stochastic Requests
    IPCO, 2023
    [
    url
    ]
    (with Franziska Eberle, Nicole Megow, Benjamin Moseley, Rudy Zhou)
  8. 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)
  9. A Local Search-Based Approach for Set Covering
    ArXiv, abs/2211.04444, 2022
    [
    url
    ]
    SOSA, 2023
    [
    doi
    ]
    (with Euiwoong Lee, Jason Li)
  10. Graph Searching with Predictions
    ArXiv, abs/2212.14220, 2022
    [
    url
    ]
    ITCS, 2023
    [
    ]
    (with Siddhartha Banerjee, Vincent Cohen-Addad, Zhouzi Li)
  11. Minimizing Completion Times for Stochastic Jobs via Batched Free Times
    SODA, 2023
    [
    doi
    ]
    ArXiv, abs/2208.13696, 2022
    [
    url
    ]
    (with Benjamin Moseley, Rudy Zhou)
  12. The Price of Explainability for Clustering
    FOCS, 2023
    [
    url
    ]
    ArXiv, abs/2304.09743, 2023
    [
    url
    ]
    (with Madhusudhan Reddy Pittu, Ola Svensson, Rachel Yuan)

    13. 2022


  13. Augmenting Online Algorithms with $\varepsilon$-Accurate Predictions
    NeurIPS, 2022
    [
    url
    ]
    (with Debmalya Panigrahi, Bernardo Subercaseaux, Kevin Sun)
  14. Learning from a Sample in Online Algorithms
    NeurIPS, 2022
    [
    url
    ]
    (with C.J. Argue, Alan Frieze, Christopher Seiler)
  15. 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)
  16. 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)
  17. 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)
  18. Probing to Minimize
    ArXiv, abs/2111.01955, 2021
    [
    url
    ]
    ITCS, 2022
    [
    url
    ]
    (with Weina Wang, Jalani Williams)
  19. 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)
  20. Non-Adaptive Stochastic Score Classification and Explainable Halfspace Evaluation
    ArXiv, abs/2111.05687, 2021
    [
    url
    ]
    IPCO, 2022
    [
    url
    ]
    (with Rohan Ghuge, Viswanath Nagarajan)

    21. 2021


  21. Random Order Online Set Cover is as Easy as Offline
    FOCS, 2021
    [
    ]
    ArXiv, abs/2111.06842, 2021
    [
    url
    ]
    (with Gregory Kehne, Roie Levin)
  22. 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)
  23. The Power of Adaptivity for Stochastic Submodular Cover
    ICML, 2021
    [
    url
    ]
    ArXiv, abs/2106.16115, 2021
    [
    url
    ]
    (with Rohan Ghuge, Viswanath Nagarajan)
  24. Structural Iterative Rounding for Generalized k-Median Problems
    ICALP, 2021
    [
    url
    ]
    (with Benjamin Moseley, Rudy Zhou)
  25. 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)
  26. 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)
  27. The Connectivity Threshold for Dense Graphs
    SODA, 2021
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  28. Fair algorithms for selecting citizens' assemblies
    Nature, 596, 2021
    [
    url
    ]
    (with Bailey Flanigan, Paul G\"{olz}, Brett Hennig, Ariel Procaccia)
  29. Bag-Of-Tasks Scheduling on Related Machines
    APPROX, 2021
    [
    url
    ]
    (with Amit Kumar, Sahil Singla)

    30. 2020


  30. Online Carpooling using Expander Decompositions
    ArXiv, abs/2007.10545, 2020
    [
    url
    ]
    FSTTCS, 2020
    [
    doi url
    ]
    (with Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla)
  31. 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)
  32. Fully-Dynamic Submodular Cover with Bounded Recourse
    ArXiv, abs/2009.00800, 2020
    [
    url
    ]
    FOCS, 2020
    [
    ]
    (with Roie Levin)
  33. Random-Order Models
    [
    url
    ]
    ArXiv, abs/2002.12159, 2020
    [
    url
    ]
    (with Sahil Singla)
  34. Dimension-Free Bounds on Chasing Convex Functions
    ArXiv, abs/2005.14058, 2020
    [
    url
    ]
    COLT, 2020
    [
    url
    ]
    (with C. J. Argue, Guru Guruganesh)
  35. 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)
  36. The Online Submodular Cover Problem
    SODA, 2020
    [
    doi url
    ]
    (with Roie Levin)
  37. Chasing Convex Bodies with Linear Competitive Ratio
    J. ACM, 68(5):2021
    [
    url
    ]
    SODA, 2020
    [
    doi url
    ]
    ArXiv, abs/1905.11877, 2019
    [
    url
    ]
    (with C. J. Argue, Guru Guruganesh, Ziye Tang)
  38. Stochastic makespan minimization in structured set systems
    Math. Program., 192(1):2022
    [
    url
    ]
    IPCO, 2020
    [
    doi url
    ]
    ArXiv, abs/2002.11153, 2020
    [
    url
    ]
    (with Amit Kumar, Viswanath Nagarajan, Xiangkun Shen)
  39. Robust Algorithms for the Secretary Problem
    ArXiv, abs/1911.07352, 2019
    [
    url
    ]
    ITCS, 2020
    [
    doi url
    ]
    (with Domagoj Bradac, Sahil Singla, Goran Zuzic)
  40. The Karger-Stein Algorithm is Optimal for {$k$}-Cut
    STOC, 2020
    [
    doi url
    ]
    ArXiv, abs/1911.09165, 2019
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  41. Caching with Time Windows and Delays
    SIAM J. Comput., 51(4):2022
    [
    url
    ]
    ArXiv, abs/2006.09665, 2020
    [
    url
    ]
    STOC, 2020
    [
    doi url
    ]
    (with Amit Kumar, Debmalya Panigrahi)

    42. 2019


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

    53. 2018


  53. Faster Exact and Approximate Algorithms for k-Cut
    FOCS, 2018
    [
    doi url
    ]
    ArXiv, abs/1807.08144, 2018
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  54. Maximizing Profit with Convex Costs in the Random-order Model
    ICALP, 2018
    [
    url
    ]
    ArXiv, abs/1804.08172, 2018
    [
    url
    ]
    (with Ruta Mehta, Marco Molinaro)
  55. Non-Preemptive Flow-Time Minimization via Rejections
    ICALP, 2018
    [
    url
    ]
    ArXiv, abs/1805.09602, 2018
    [
    url
    ]
    (with Amit Kumar, Jason Li)
  56. 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)
  57. 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)
  58. An FPT Algorithm Beating 2-Approximation for {$k$}-Cut
    SODA, 2018
    [
    doi url
    ]
    ArXiv, abs/1710.08488, 2017
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  59. Stochastic Load Balancing on Unrelated Machines
    Math. Oper. Res., 46(1):2021
    [
    doi url
    ]
    SODA, 2018
    [
    doi url
    ]
    ArXiv, abs/1904.07271, 2019
    [
    url
    ]
    (with Amit Kumar, Viswanath Nagarajan, Xiangkun Shen)
  60. A Local-Search Algorithm for Steiner Forest
    ITCS, 2018
    [
    doi url
    ]
    ArXiv, abs/1707.02753, 2017
    [
    url
    ]
    (with Martin Gro\ss, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt, Jos\'{e} Verschae)

    61. 2017


  61. Stochastic Unsplittable Flows
    APPROX, 2017
    [
    doi url
    ]
    (with Archit Karandikar)
  62. 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)
  63. Online and Dynamic Algorithms for Set Cover
    STOC, 2017
    [
    url
    ]
    ArXiv, abs/1611.05646, 2016
    [
    url
    ]
    (with Amit Kumar, Ravishankar Krishnaswamy, Debmalya Panigrahi)
  64. LAST but not Least: Online Spanners for Buy-at-Bulk
    SODA, 2017
    [
    doi url
    ]
    ArXiv, abs/1611.00052, 2016
    [
    url
    ]
    (with R. Ravi, Kunal Talwar, Seeun William Umboh)
  65. Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
    SODA, 2017
    [
    doi url
    ]
    (with Viswanath Nagarajan, Sahil Singla)

    66. 2016


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

    71. 2015


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

    74. 2014


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

    81. 2013


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

    92. 2012


  92. 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)
  93. 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)
  94. Parallel Probabilistic Tree Embeddings, k-Median, and Buy-at-Bulk Network Design
    SPAA, 2012
    [
    doi
    ]
    (with Guy E. Blelloch, Kanat Tangwongsan)
  95. The Online Metric Matching Problem for Doubling Metrics
    ICALP (1), 2012
    [
    doi
    ]
    (with Kevin Lewi)
  96. Approximating Sparse Covering Integer Programs Online
    Mathematics of Operations Research, 39(4):2014
    [
    doi url
    ]
    ICALP (1), 2012
    [
    doi
    ]
    ArXiv, abs/1205.0175, 2012
    [
    url
    ]
    (with Viswanath Nagarajan)
  97. Iterative Constructions and Private Data Release
    TCC, 2012
    [
    doi
    ]
    ArXiv, abs/1107.3731, 2011
    [
    url
    ]
    (with Aaron Roth, Jonathan Ullman)
  98. Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
    Math. Oper. Res., 40(1):2015
    [
    doi url
    ]
    SODA, 2012
    [
    url
    ]
    (with Ravishankar Krishnaswamy, Viswanath Nagarajan, R. Ravi)
  99. Scheduling Heterogeneous Processors Isn't As Easy As You Think
    SODA, 2012
    [
    url
    ]
    (with Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs)
  100. Approximation Algorithms for VRP with Stochastic Demands
    Operations Research, 60(1):2012
    [
    doi
    ]
    (with Viswanath Nagarajan, R. Ravi)

    101. 2011


  101. 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)
  102. Welfare and Profit Maximization with Production Costs
    ArXiv, abs/1110.4992, 2011
    [
    url
    ]
    FOCS, 2011
    [
    doi
    ]
    (with Avrim Blum, Yishay Mansour, Ankit Sharma)
  103. 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)
  104. 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)
  105. Approximation algorithms for network design: A survey
    Surveys in Operations Research and Management Science, 16(1):2011
    [
    pdf doi
    ]
    (with Jochen Könemann)

    106. 2010


  106. Discovering pathways by orienting edges in protein interaction networks.
    Nucleic Acids Res, 2010
    [
    doi
    ]
    (with Anthony Gitter, Judith Klein-Seetharaman, Ziv Bar-Joseph)
  107. Network-Wide Deployment of Intrusion Detection and Prevention Systems
    ACM CoNEXT, 2010
    [
    doi url
    ]
    (with Vyas Sekar, Ravishankar Krishnaswamy, Michael K. Reiter)
  108. 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)
  109. 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)
  110. Improved Approximation Algorithms for Requirement Cut
    Operations Research Letters, 38(4):2010
    [
    doi
    ]
    (with Viswanath Nagarajan, R. Ravi)
  111. Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
    Math. Oper. Res., 42(3):2017
    [
    doi url
    ]
    ICALP (1), 2010
    [
    doi
    ]
    ArXiv, abs/1003.0722, 2010
    [
    url
    ]
    (with Viswanath Nagarajan, R. Ravi)
  112. 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)
  113. Tree Embeddings for Two-Edge-Connected Network Design
    SODA, 2010
    [
    doi
    ]
    (with Ravishankar Krishnaswamy, R. Ravi)
  114. Nonclairvoyantly scheduling power-heterogeneous processors
    Sustainable Computing: Informatics and Systems, 1(3):2011
    [
    doi
    ]
    International Green Computing Conference, 2010
    [
    pdf doi
    ]
    (with Ravishankar Krishnaswamy, Kirk Pruhs)
  115. Scalably Scheduling Power-Heterogeneous Processors
    ICALP (1), 2010
    [
    doi
    ]
    ArXiv, abs/1105.3748, 2011
    [
    url
    ]
    (with Ravishankar Krishnaswamy, Kirk Pruhs)
  116. Scheduling jobs with varying parallelizability to reduce variance
    SPAA, 2010
    [
    pdf doi
    ]
    (with Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs)
  117. Vertex Sparsifiers: New Results from Old Techniques
    APPROX-RANDOM, 2010
    [
    doi
    ]
    SIAM J. Comput., 43(4):2014
    [
    doi url
    ]
    ArXiv, abs/1006.4586, 2010
    [
    url
    ]
    (with Matthias Englert, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, Kunal Talwar)
  118. 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)
  119. A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover
    SODA, 2010
    [
    doi
    ]
    (with Nikhil Bansal, Ravishankar Krishnaswamy)

    120. 2009


  120. 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)
  121. Thresholded Covering Algorithms for Robust and Max-Min Optimization
    ArXiv, abs/0912.1045, 2009
    [
    url
    ]
    ACM Trans. Algorithms, 12(1):2016
    [
    doi url
    ]
    ArXiv, abs/1012.4962, 2010
    [
    url
    ]
    ICALP (1), 2010
    [
    doi
    ]
    Math. Program., 146(1-2):2014
    [
    doi url
    ]
    (with Viswanath Nagarajan, R. Ravi)
  122. Differentially Private Approximation Algorithms
    ArXiv, abs/0903.4510, 2009
    [
    url
    ]
    SODA, 2010
    [
    doi
    ]
    (with Katrina Ligett, Frank McSherry, Aaron Roth, Kunal Talwar)
  123. A constant-factor approximation for stochastic Steiner forest
    STOC, 2009
    [
    pdf doi
    ]
    (with Amit Kumar)
  124. Online and Stochastic Survivable Network Design
    SIAM J. Comput., 41(6):2012
    [
    doi
    ]
    STOC, 2009
    [
    pdf doi
    ]
    (with Ravishankar Krishnaswamy, R. Ravi)
  125. Scheduling with Outliers
    ArXiv, abs/0906.2020, 2009
    [
    url
    ]
    APPROX, 2009
    [
    doi
    ]
    (with Ravishankar Krishnaswamy, Amit Kumar, Danny Segev)
  126. Clustering under approximation stability
    JACM, 60(2):2013
    [
    doi
    ]
    SODA, 2009
    [
    pdf doi
    ]
    (with Maria-Florina Balcan, Avrim Blum)
  127. Secretary problems: weights and discounts
    SODA, 2009
    [
    pdf doi
    ]
    (with Moshe Babaioff, Michael Dinitz, Nicole Immorlica, Kunal Talwar)

    128. 2008


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

    138. 2007


  138. How to Complete a Doubling Metric
    ArXiv, abs/0712.3331, 2007
    [
    url
    ]
    LATIN, 2008
    [
    doi
    ]
    Algorithmica, 59(1):2011
    [
    doi
    ]
    (with Kunal Talwar)
  139. An Efficient Cost-Sharing Mechanism for the Prize-Collecting Steiner Forest Problem
    Mathematical Programming, 2014
    [
    url
    ]
    SODA, 2007
    [
    pdf doi
    ]
    (with Jochen Könemann, Stefano Leonardi, R. Ravi, Guido Schäfer)
  140. 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)
  141. Stochastic Steiner Tree with Non-Uniform Inflation
    APPROX, 2007
    [
    pdf doi
    ]
    (with MohammadTaghi Hajiaghayi, Amit Kumar)
  142. Pricing Tree Access Networks with Connected Backbones
    ESA, 2007
    [
    pdf doi
    ]
    (with Vineet Goyal, Stefano Leonardi, R. Ravi)
  143. 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)
  144. A Randomized $O(\log^2 k)$-Competitive Algorithm for Metric Bipartite Matching
    Algorithmica, 68(2):2014
    [
    doi
    ]
    ESA, 2007
    [
    pdf doi
    ]
    (with Nikhil Bansal, Niv Buchbinder, Joseph Naor)
  145. Infrastructure Leasing Problems
    IPCO, 2007
    [
    pdf doi
    ]
    (with Barbara M. Anthony)

    146. 2006


  146. 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)
  147. Approximating unique games
    SODA, 2006
    [
    pdf doi
    ]
    (with Kunal Talwar)
  148. Oblivious network design
    SODA, 2006
    [
    pdf doi
    ]
    (with MohammadTaghi Hajiaghayi, Harald Räcke)
  149. Quorum placement in networks: minimizing network congestion
    PODC, 2006
    [
    pdf doi
    ]
    (with Daniel Golovin, Bruce M. Maggs, Florian Oprea, Michael K. Reiter)
  150. Improved embeddings of graph metrics into random trees (article withdrawn)
    SODA, 2006
    [
    doi
    ]
    (with Kedar Dhamdhere, Harald Räcke)
  151. Small hop-diameter sparse spanners for doubling metrics
    SODA, 2006
    [
    pdf doi
    ]
    Discrete & Computational Geometry, 41(1):2009
    [
    doi
    ]
    (with T.-H. Hubert Chan)
  152. Spanners with Slack
    ESA, 2006
    [
    pdf doi
    ]
    (with T.-H. Hubert Chan, Michael Dinitz)

    153. 2005


  153. What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization
    APPROX, 2005
    [
    pdf doi
    ]
    (with Martin Pál, R. Ravi, Amitabh Sinha)
  154. Stochastic Steiner Trees Without a Root
    ICALP, 2005
    [
    pdf doi
    ]
    (with Martin Pál)
  155. Quorum placement in networks to minimize access delays
    PODC, 2005
    [
    pdf doi
    ]
    (with Bruce M. Maggs, Florian Oprea, Michael K. Reiter)
  156. Where's the Winner? Max-Finding and Sorting with Metric Costs
    APPROX, 2005
    [
    pdf doi
    ]
    (with Amit Kumar)
  157. On the Approximability of Network Design Problems
    SODA, 2005
    [
    pdf doi
    ]
    ACM Trans. Algorithms, 4(2):2008
    [
    doi
    ]
    (with Julia Chuzhoy, Joseph (Seffi) Naor, Amitabh Sinha)
  158. On a bidirected relaxation for the Multiway {Cut} problem
    Discrete Appl. Math., 150(1-3):2005
    [
    doi
    ]
    (with Chandra Chekuri, Amit Kumar)
  159. Improved Approximations for Sparsest {Cut}
    SODA, 2005
    [
    pdf doi
    ]
    ACM Trans. Algorithms, 4(2):2008
    [
    doi
    ]
    (with Shuchi Chawla, Harald Räcke)
  160. On Hierarchical Routing in Doubling Metrics
    ACM Trans. Algorithms, 12(4):2016
    [
    doi url
    ]
    SODA, 2005
    [
    pdf doi
    ]
    (with T.-H. Hubert Chan, Bruce M. Maggs, Shuheng Zhou)
  161. Approximation Algorithms for Embeddings Into Low-Dimensional Spaces
    SODA, 2005
    [
    pdf doi
    ]
    SIAM J. Discrete Math., 33(1):2019
    [
    doi url
    ]
    (with Mihai B\uadoiu, Kedar Dhamdhere, Yuri Rabinovich, Harald Räcke, R. Ravi, Anastasios Sidiropoulos)
  162. Metric Embeddings with Relaxed Guarantees
    FOCS, 2005
    [
    pdf doi
    ]
    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)

    163. 2004


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

    167. 2003


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

    177. 2002


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

    180. 2001


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

    184. 2000


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

    187. 1999


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

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