>> Publications

DBLP | ACM DL | Google Scholar | BibTeX

    2026


  1. An Optimal Online Algorithm for Robust Flow Time Scheduling
    SODA, 2026
    [
    url
    ]
    (with Amit Kumar, Debmalya Panigrahi, Zhaozi Wang)
  2. A Learning Perspective on Random-Order Covering Problems
    SOSA, 2026
    [
    url
    ]
    ArXiv, abs/2511.07283, 2025
    [
    url
    ]
    (with Marco Molinaro, Matteo Russo)
  3. Learning Packing and Covering from Samples
    SODA, 2026
    [
    url
    ]
    (with Marco Molinaro)
  4. Complexity of Local Search for CSPs Parameterized by Constraint Difference
    ArXiv, abs/2512.03275, 2025
    [
    url
    ]
    (with Aditya Anand, Vincent Cohen-Addad, Tommaso d'Orsi, Euiwoong Lee, Debmalya Panigrahi, Sijin Peng)
  5. Steiner Forest: A Simplified Better-Than-2 Approximation
    ArXiv, abs/2511.18460, 2025
    [
    url
    ]
    (with Vera Traub)
  6. Combinatorial Optimization using Comparison Oracles
    ArXiv, 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, David P. Woodruff)

    7. 2025


  7. Length Generalization via Auxiliary Tasks
    NeurIPS, 2025
    [
    url
    ]
    (with Pranjal Awasthi, Ravi Kumar)
  8. Robust Contextual Pricing
    NeurIPS, 2025
    [
    url
    ]
    (with Guru Guruganesh, Renato Paes Leme, Jon Schneider)
  9. Parsimonious Predictions for Strategyproof Scheduling
    NeurIPS, 2025
    [
    url
    ]
    (with Richard Cole, Pranav Jangir)
  10. A Little Clairvoyance Is All You Need
    FOCS, 2025
    [
    ]
    ArXiv, abs/2508.17759, 2025
    [
    url
    ]
    (with Haim Kaplan, Alexander Lindermayr, Jens Schloeter, Sorrachai Yingchareonthawornchai)
  11. Tight Results for Online Convex Paging
    STOC, 2025
    [
    url
    ]
    (with Amit Kumar, Debmalya Panigrahi)
  12. Multi-Platform Autobidding with and without Predictions
    WWW, 2025
    [
    url
    ]
    ArXiv, abs/2502.19317, 2025
    [
    url
    ]
    (with Gagan Aggarwal, Xizhi Tan, Mingfei Zhao)
  13. Why is My Route Different Today? An Algorithm for Explaining Route Selection
    ArXiv, abs/2506.05604, 2025
    [
    url
    ]
    SIAM Applied and Computational Discrete Algorithms, 2025
    [
    ]
    (with Aaron Schild, Sreenivas Gollapudi, Kostas Kollias, Ali Kemal Sinop)

    14. 2024


  14. Pairwise-Independent Contention Resolution
    IPCO, 2024
    [
    url
    ]
    ArXiv, abs/2406.15876, 2024
    [
    url
    ]
    (with Jinqiao Hu, Gregory Kehne, Roie Levin)
  15. Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems
    NeurIPS, 2024
    [
    url
    ]
    ArXiv, abs/2402.18263, 2024
    [
    url
    ]
    (with Vincent Cohen-Addad, Tommaso d'Orsi, Euiwoong Lee, Debmalya Panigrahi)
  16. Maintaining Matroid Intersections Online
    SODA, 2024
    [
    url
    ]
    ArXiv, abs/2309.10214, 2023
    [
    url
    ]
    (with Niv Buchbinder, Daniel Hathcock, Anna R. Karlin, Sherry Sarkar)
  17. Set Covering with Our Eyes Wide Shut
    SODA, 2024
    [
    url
    ]
    ArXiv, abs/2304.02063, 2023
    [
    url
    ]
    (with Gregory Kehne, Roie Levin)
  18. Poly-logarithmic Competitiveness for the k-Taxi Problem
    SODA, 2024
    [
    url
    ]
    (with Amit Kumar, Debmalya Panigrahi)
  19. Randomized Truthful Auctions with Learning Agents
    NeurIPS, 2024
    [
    url
    ]
    ArXiv, abs/2411.09517, 2024
    [
    url
    ]
    (with Gagan Aggarwal, Andr\'{e}s Perlroth, Grigoris Velegkas)
  20. Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structure
    NeurIPS, 2024
    [
    url
    ]
    ArXiv, abs/2405.20671, 2024
    [
    url
    ]
    (with Hanseul Cho, Jaeyoung Cha, Pranjal Awasthi, Srinadh Bhojanapalli, Chulhee Yun)
  21. The Average-Value Allocation Problem
    APPROX, 2024
    [
    url
    ]
    ArXiv, abs/2407.10401, 2024
    [
    url
    ]
    (with Kshipra Bhawalkar, Zhe Feng, Aranyak Mehta, David Wajc, Di Wang)
  22. MAC Advice for facility location mechanism design
    NeurIPS, 2024
    [
    url
    ]
    ArXiv, abs/2403.12181, 2024
    [
    url
    ]
    (with Zohar Barak, Inbal Talgam-Cohen)

    23. 2023


  23. Improving Length-Generalization in Transformers via Task Hinting
    ArXiv, abs/2310.00726, 2023
    [
    url
    ]
    (with Pranjal Awasthi)
  24. Configuration balancing for stochastic requests
    Math. Program., 210(1):2025
    [
    url
    ]
    ArXiv, abs/2208.13702, 2022
    [
    url
    ]
    IPCO, 2023
    [
    url
    ]
    (with Franziska Eberle, Nicole Megow, Benjamin Moseley, Rudy Zhou)
  25. 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)
  26. A Local Search-Based Approach for Set Covering
    ArXiv, abs/2211.04444, 2022
    [
    url
    ]
    SOSA, 2023
    [
    doi
    ]
    (with Euiwoong Lee, Jason Li)
  27. Graph Searching with Predictions
    ArXiv, abs/2212.14220, 2022
    [
    url
    ]
    ITCS, 2023
    [
    ]
    (with Siddhartha Banerjee, Vincent Cohen-Addad, Zhouzi Li)
  28. Minimizing Completion Times for Stochastic Jobs via Batched Free Times
    SODA, 2023
    [
    doi
    ]
    ArXiv, abs/2208.13696, 2022
    [
    url
    ]
    (with Benjamin Moseley, Rudy Zhou)
  29. The Price of Explainability for Clustering
    FOCS, 2023
    [
    url
    ]
    ArXiv, abs/2304.09743, 2023
    [
    url
    ]
    (with Madhusudhan Reddy Pittu, Ola Svensson, Rachel Yuan)

    30. 2022


  30. Augmenting Online Algorithms with $\varepsilon$-Accurate Predictions
    NeurIPS, 2022
    [
    url
    ]
    (with Debmalya Panigrahi, Bernardo Subercaseaux, Kevin Sun)
  31. Learning from a Sample in Online Algorithms
    NeurIPS, 2022
    [
    url
    ]
    (with C.J. Argue, Alan Frieze, Christopher Seiler)
  32. 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)
  33. 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)
  34. 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)
  35. Probing to Minimize
    ArXiv, abs/2111.01955, 2021
    [
    url
    ]
    ITCS, 2022
    [
    url
    ]
    (with Weina Wang, Jalani Williams)
  36. Matroid-based TSP rounding for half-integral solutions
    Math. Program., 206(1):2024
    [
    url
    ]
    ArXiv, abs/2111.09290, 2021
    [
    url
    ]
    IPCO, 2022
    [
    url
    ]
    (with Euiwoong Lee, Jason Li, Marcin Mucha, Heather Newman, Sherry Sarkar)
  37. Nonadaptive Stochastic Score Classification and Explainable Half-Space Evaluation
    Oper. Res., 73(4):2025
    [
    url
    ]
    IPCO, 2022
    [
    url
    ]
    ArXiv, abs/2111.05687, 2021
    [
    url
    ]
    (with Rohan Ghuge, Viswanath Nagarajan)

    38. 2021


  38. Random Order Online Set Cover is as Easy as Offline
    FOCS, 2021
    [
    ]
    ArXiv, abs/2111.06842, 2021
    [
    url
    ]
    (with Gregory Kehne, Roie Levin)
  39. 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)
  40. The Power of Adaptivity for Stochastic Submodular Cover
    Oper. Res., 72(3):2024
    [
    url
    ]
    ArXiv, abs/2106.16115, 2021
    [
    url
    ]
    ICML, 2021
    [
    url
    ]
    (with Rohan Ghuge, Viswanath Nagarajan)
  41. Structural iterative rounding for generalized k-median problems
    Math. Program., 212(1):2025
    [
    doi url
    ]
    ICALP, 2021
    [
    url
    ]
    (with Benjamin Moseley, Rudy Zhou)
  42. 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)
  43. 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)
  44. The Connectivity Threshold for Dense Graphs
    SODA, 2021
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  45. Fair algorithms for selecting citizens' assemblies
    Nature, 596, 2021
    [
    url
    ]
    (with Bailey Flanigan, Paul G\"{olz}, Brett Hennig, Ariel Procaccia)
  46. Bag-Of-Tasks Scheduling on Related Machines
    APPROX, 2021
    [
    url
    ]
    (with Amit Kumar, Sahil Singla)

    47. 2020


  47. Online Carpooling using Expander Decompositions
    ArXiv, abs/2007.10545, 2020
    [
    url
    ]
    FSTTCS, 2020
    [
    doi url
    ]
    (with Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla)
  48. 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)
  49. Fully-Dynamic Submodular Cover with Bounded Recourse
    ArXiv, abs/2009.00800, 2020
    [
    url
    ]
    FOCS, 2020
    [
    ]
    (with Roie Levin)
  50. Random-Order Models
    [
    url
    ]
    ArXiv, abs/2002.12159, 2020
    [
    url
    ]
    (with Sahil Singla)
  51. Dimension-Free Bounds on Chasing Convex Functions
    ArXiv, abs/2005.14058, 2020
    [
    url
    ]
    COLT, 2020
    [
    url
    ]
    (with C. J. Argue, Guru Guruganesh)
  52. 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)
  53. The Online Submodular Cover Problem
    SODA, 2020
    [
    doi url
    ]
    (with Roie Levin)
  54. 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)
  55. 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)
  56. Robust Algorithms for the Secretary Problem
    ArXiv, abs/1911.07352, 2019
    [
    url
    ]
    ITCS, 2020
    [
    doi url
    ]
    (with Domagoj Bradac, Sahil Singla, Goran Zuzic)
  57. The Karger-Stein Algorithm is Optimal for {$k$}-Cut
    STOC, 2020
    [
    doi url
    ]
    ArXiv, abs/1911.09165, 2019
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  58. 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)

    59. 2019


  59. Potential-Function Proofs for Gradient Methods
    Theory of Computing, 15(4):2019
    [
    doi url
    ]
    ArXiv, abs/1712.04581, 2017
    [
    url
    ]
    (with Nikhil Bansal)
  60. 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)
  61. Stochastic Online Metric Matching
    ICALP, 2019
    [
    doi url
    ]
    ArXiv, abs/1904.09284, 2019
    [
    url
    ]
    (with Guru Guruganesh, Binghui Peng, David Wajc)
  62. Non-clairvoyant Precedence Constrained Scheduling
    ArXiv, abs/1905.02133, 2019
    [
    url
    ]
    ICALP, 2019
    [
    doi url
    ]
    (with Naveen Garg, Amit Kumar, Sahil Singla)
  63. 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)
  64. Better Algorithms for Stochastic Bandits with Adversarial Corruptions
    COLT, 2019
    [
    url
    ]
    ArXiv, abs/1902.08647, 2019
    [
    url
    ]
    (with Tomer Koren, Kunal Talwar)
  65. The Markovian Price of Information
    ArXiv, abs/1902.07856, 2019
    [
    url
    ]
    IPCO, 2019
    [
    doi url
    ]
    (with Haotian Jiang, Ziv Scully, Sahil Singla)
  66. Losing Treewidth by Separating Subsets
    SODA, 2019
    [
    doi url
    ]
    ArXiv, abs/1804.01366, 2018
    [
    url
    ]
    (with Euiwoong Lee, Jason Li, Pasin Manurangsi, Michal Wlodarczyk)
  67. Elastic Caching
    SODA, 2019
    [
    doi url
    ]
    (with Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi)
  68. 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)
  69. 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)

    70. 2018


  70. Faster Exact and Approximate Algorithms for k-Cut
    FOCS, 2018
    [
    doi url
    ]
    ArXiv, abs/1807.08144, 2018
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  71. Maximizing Profit with Convex Costs in the Random-order Model
    ICALP, 2018
    [
    url
    ]
    ArXiv, abs/1804.08172, 2018
    [
    url
    ]
    (with Ruta Mehta, Marco Molinaro)
  72. Non-Preemptive Flow-Time Minimization via Rejections
    ICALP, 2018
    [
    url
    ]
    ArXiv, abs/1805.09602, 2018
    [
    url
    ]
    (with Amit Kumar, Jason Li)
  73. 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)
  74. 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)
  75. An FPT Algorithm Beating 2-Approximation for {$k$}-Cut
    SODA, 2018
    [
    doi url
    ]
    ArXiv, abs/1710.08488, 2017
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  76. 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)
  77. 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)

    78. 2017


  78. Stochastic Unsplittable Flows
    APPROX, 2017
    [
    doi url
    ]
    (with Archit Karandikar)
  79. 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)
  80. Online and Dynamic Algorithms for Set Cover
    STOC, 2017
    [
    url
    ]
    ArXiv, abs/1611.05646, 2016
    [
    url
    ]
    (with Amit Kumar, Ravishankar Krishnaswamy, Debmalya Panigrahi)
  81. 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)
  82. Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
    SODA, 2017
    [
    doi url
    ]
    (with Viswanath Nagarajan, Sahil Singla)

    83. 2016


  83. Online Packing and Covering Framework with Convex Objectives
    ArXiv, abs/1412.8347, 2014
    [
    url
    ]
    (with Niv Buchbinder, Shahar Chen, Viswanath Nagarajan, Joseph (Seffi) Naor)
  84. 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)
  85. Pure Exploration of Multi-armed Bandit Under Matroid Constraints
    ArXiv, abs/1605.07162, 2016
    [
    url
    ]
    COLT, 2016
    [
    url
    ]
    (with Lijie Chen, Jian Li)
  86. Approximation algorithms for aversion $k$-clustering via local {$k$}-median
    ICALP, 2016
    [
    doi url
    ]
    (with Guru Guruganesh, Melanie Schmidt)
  87. Algorithms and Adaptivity Gaps for Stochastic Probing
    SODA, 2016
    [
    doi url
    ]
    (with Viswanath Nagarajan, Sahil Singla)

    88. 2015


  88. 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)
  89. Greedy Algorithms for Steiner Forest
    ArXiv, abs/1412.7693, 2015
    [
    url
    ]
    STOC, 2015
    [
    doi url
    ]
    (with Amit Kumar)
  90. 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)

    91. 2014


  91. 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)
  92. 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)
  93. Changing Bases: Multistage Optimization for Matroids and Matchings
    ArXiv, 1404.3768, 2014
    [
    url
    ]
    ICALP, 2014
    [
    doi url
    ]
    (with Kunal Talwar, Udi Wieder)
  94. Minimum d-dimensional arrangement with fixed points
    SODA, 2014
    [
    doi
    ]
    ArXiv, 1307.6627, 2013
    [
    url
    ]
    (with Anastasios Sidiropoulos)
  95. Online Steiner Tree with Deletions
    SODA, 2014
    [
    doi
    ]
    ArXiv, 1312.7296, 2014
    [
    url
    ]
    (with Amit Kumar)
  96. Towards $(1+\epsilon)$-Approximate Flow Sparsifiers
    SODA, 2014
    [
    doi
    ]
    ArXiv, 1310.3252, 2013
    [
    url
    ]
    (with Alexandr Andoni, Robert Krauthgamer)
  97. Maintaining Assignments Online: Matching, Scheduling, and Flows
    SODA, 2014
    [
    doi
    ]
    (with Amit Kumar, Cliff Stein)

    98. 2013


  98. Random Rates for 0-Extension and Low-Diameter Decompositions
    ArXiv, 1307.5582, 2013
    [
    url
    ]
    (with Kunal Talwar)
  99. Harnessing the Power of Two Crossmatches
    14th ACM Conference on Electronic Commerce, 2013
    [
    doi
    ]
    (with Avrim Blum, Ariel Procaccia, Ankit Sharma)
  100. 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)
  101. On the Non-Uniform Sparsest Cut Problem on Bounded Treewidth Graphs
    STOC, 2013
    [
    doi
    ]
    ArXiv, 1305.1347, 2013
    [
    url
    ]
    (with Kunal Talwar, David Witmer)
  102. The Approximability of the Binary Paintshop Problem
    APPROX-RANDOM, 2013
    [
    doi
    ]
    (with Satyen Kale, Viswanath Nagarajan, Rishi Saket, Baruch Schieber)
  103. 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)
  104. Thrifty Algorithms for Multistage Robust Optimization
    IPCO, 2013
    [
    doi
    ]
    ArXiv, 1302.5445, 2013
    [
    url
    ]
    (with Viswanath Nagarajan, Vijay V. Vazirani)
  105. A Stochastic Probing Problem with Applications
    IPCO, 2013
    [
    doi
    ]
    ArXiv, 1302.5913, 2013
    [
    url
    ]
    (with Viswanath Nagarajan)
  106. 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)
  107. Packing Interdiction and Partial Covering Problems
    IPCO, 2013
    [
    doi
    ]
    (with Michael Dinitz)
  108. 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)

    109. 2012


  109. 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)
  110. 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)
  111. Parallel Probabilistic Tree Embeddings, k-Median, and Buy-at-Bulk Network Design
    SPAA, 2012
    [
    doi
    ]
    (with Guy E. Blelloch, Kanat Tangwongsan)
  112. The Online Metric Matching Problem for Doubling Metrics
    ICALP (1), 2012
    [
    doi
    ]
    (with Kevin Lewi)
  113. 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)
  114. Iterative Constructions and Private Data Release
    TCC, 2012
    [
    doi
    ]
    ArXiv, abs/1107.3731, 2011
    [
    url
    ]
    (with Aaron Roth, Jonathan Ullman)
  115. 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)
  116. Scheduling Heterogeneous Processors Isn't As Easy As You Think
    SODA, 2012
    [
    url
    ]
    (with Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs)
  117. Approximation Algorithms for VRP with Stochastic Demands
    Operations Research, 60(1):2012
    [
    doi
    ]
    (with Viswanath Nagarajan, R. Ravi)

    118. 2011


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

    123. 2010


  123. Discovering pathways by orienting edges in protein interaction networks.
    Nucleic Acids Res, 2010
    [
    doi
    ]
    (with Anthony Gitter, Judith Klein-Seetharaman, Ziv Bar-Joseph)
  124. Network-Wide Deployment of Intrusion Detection and Prevention Systems
    ACM CoNEXT, 2010
    [
    doi url
    ]
    (with Vyas Sekar, Ravishankar Krishnaswamy, Michael K. Reiter)
  125. 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)
  126. 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)
  127. Improved Approximation Algorithms for Requirement Cut
    Operations Research Letters, 38(4):2010
    [
    doi
    ]
    (with Viswanath Nagarajan, R. Ravi)
  128. 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)
  129. 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)
  130. Tree Embeddings for Two-Edge-Connected Network Design
    SODA, 2010
    [
    doi
    ]
    (with Ravishankar Krishnaswamy, R. Ravi)
  131. 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)
  132. Scalably Scheduling Power-Heterogeneous Processors
    ICALP (1), 2010
    [
    doi
    ]
    ArXiv, abs/1105.3748, 2011
    [
    url
    ]
    (with Ravishankar Krishnaswamy, Kirk Pruhs)
  133. Scheduling jobs with varying parallelizability to reduce variance
    SPAA, 2010
    [
    pdf doi
    ]
    (with Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs)
  134. 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)
  135. 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\'an Mestre, Viswanath Nagarajan, Atri Rudra)
  136. A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover
    SODA, 2010
    [
    doi
    ]
    (with Nikhil Bansal, Ravishankar Krishnaswamy)

    137. 2009


  137. 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)
  138. 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)
  139. Differentially Private Approximation Algorithms
    ArXiv, abs/0903.4510, 2009
    [
    url
    ]
    SODA, 2010
    [
    doi
    ]
    (with Katrina Ligett, Frank McSherry, Aaron Roth, Kunal Talwar)
  140. A constant-factor approximation for stochastic Steiner forest
    STOC, 2009
    [
    pdf doi
    ]
    (with Amit Kumar)
  141. Online and Stochastic Survivable Network Design
    SIAM J. Comput., 41(6):2012
    [
    doi
    ]
    STOC, 2009
    [
    pdf doi
    ]
    (with Ravishankar Krishnaswamy, R. Ravi)
  142. Scheduling with Outliers
    ArXiv, abs/0906.2020, 2009
    [
    url
    ]
    APPROX, 2009
    [
    doi
    ]
    (with Ravishankar Krishnaswamy, Amit Kumar, Danny Segev)
  143. Clustering under approximation stability
    JACM, 60(2):2013
    [
    doi
    ]
    SODA, 2009
    [
    pdf doi
    ]
    (with Maria-Florina Balcan, Avrim Blum)
  144. Secretary problems: weights and discounts
    SODA, 2009
    [
    pdf doi
    ]
    (with Moshe Babaioff, Michael Dinitz, Nicole Immorlica, Kunal Talwar)

    145. 2008


  145. 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)
  146. Simpler Analyses of Local Search Algorithms for Facility Location
    ArXiv, abs/0809.2554, 2008
    [
    url
    ]
    (with Kanat Tangwongsan)
  147. Extracting Dynamics from Static Cancer Expression Data
    IEEE/ACM Trans. Comput. Biol. Bioinformatics, 5(2):2008
    [
    doi
    ]
    (with Ziv Bar-Joseph)
  148. 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)
  149. All-Norms and All-$L_p$-Norms Approximation Algorithms
    FST&TCS, 2008
    [
    doi url
    ]
    (with Daniel Golovin, Amit Kumar, Kanat Tangwongsan)
  150. Stochastic analyses for online combinatorial optimization problems
    SODA, 2008
    [
    pdf doi
    ]
    (with Naveen Garg, Stefano Leonardi, Piotr Sankowski)
  151. 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)
  152. Ultra-low-dimensional embeddings for doubling metrics
    SODA, 2008
    [
    pdf doi
    ]
    J. ACM, 57(4):2010
    [
    doi
    ]
    (with T.-H. Hubert Chan, Kunal Talwar)
  153. 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)
  154. 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)

    155. 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
    [
    pdf doi
    ]
    (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
    [
    pdf doi
    ]
    (with MohammadTaghi Hajiaghayi, Amit Kumar)
  159. Pricing Tree Access Networks with Connected Backbones
    ESA, 2007
    [
    pdf doi
    ]
    (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
    [
    pdf doi
    ]
    (with Nikhil Bansal, Niv Buchbinder, Joseph Naor)
  162. Infrastructure Leasing Problems
    IPCO, 2007
    [
    pdf doi
    ]
    (with Barbara M. Anthony)

    163. 2006


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

    170. 2005


  170. What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization
    APPROX, 2005
    [
    pdf doi
    ]
    (with Martin P\'al, R. Ravi, Amitabh Sinha)
  171. Stochastic Steiner Trees Without a Root
    ICALP, 2005
    [
    pdf doi
    ]
    (with Martin P\'al)
  172. Quorum placement in networks to minimize access delays
    PODC, 2005
    [
    pdf doi
    ]
    (with Bruce M. Maggs, Florian Oprea, Michael K. Reiter)
  173. Where's the Winner? Max-Finding and Sorting with Metric Costs
    APPROX, 2005
    [
    pdf doi
    ]
    (with Amit Kumar)
  174. 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)
  175. On a bidirected relaxation for the Multiway {Cut} problem
    Discrete Appl. Math., 150(1-3):2005
    [
    doi
    ]
    (with Chandra Chekuri, Amit Kumar)
  176. Improved Approximations for Sparsest {Cut}
    SODA, 2005
    [
    pdf doi
    ]
    ACM Trans. Algorithms, 4(2):2008
    [
    doi
    ]
    (with Shuchi Chawla, Harald Räcke)
  177. 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)
  178. 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)
  179. 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)

    180. 2004


  180. Cost-Sharing Mechanisms for Network Design.
    APPROX, 2004
    [
    pdf doi
    ]
    Algorithmica, 50(1):2008
    [
    doi
    ]
    (with Aravind Srinivasan, \'Eva Tardos)
  181. 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)
  182. Sampling and cost-sharing: approximation algorithms for stochastic optimization problems
    SIAM J. Comput., 40(5):2011
    [
    doi
    ]
    STOC, 2004
    [
    pdf doi
    ]
    (with Martin P\'al, R. Ravi, Amitabh Sinha)
  183. Approximation Algorithms for Minimizing Average Distortion
    STACS, 2004
    [
    pdf doi
    ]
    Theory of Computing Systems, 39(1):2006
    [
    doi
    ]
    (with Kedar Dhamdhere, R. Ravi)

    184. 2003


  184. Counting Inversions in Lists
    SODA, 2003
    [
    pdf doi
    ]
    (with Francis X. Zane)
  185. On the Covering {Steiner} Problem
    FST&TCS, 2003
    [
    pdf doi
    ]
    Theory of Computing, 2, 2006
    [
    doi
    ]
    (with Aravind Srinivasan)
  186. Tree based MPLS routing
    SPAA, 2003
    [
    doi
    ]
    (with Amit Kumar, Mikkel Thorup)
  187. Simpler and Better Approximation Algorithms for Network Design
    STOC, 2003
    [
    pdf doi
    ]
    (with Amit Kumar, Tim Roughgarden)
  188. Exploring the Trade-off between Label Size and Stack Depth in MPLS Routing
    INFOCOM, 2003
    [
    ]
    (with Amit Kumar, Rajeev Rastogi)
  189. Approximations via Cost-Sharing
    FOCS, 2003
    [
    pdf doi
    ]
    J. ACM, 54(3):2007
    [
    doi
    ]
    (with Amit Kumar, Martin P\'al, Tim Roughgarden)
  190. Bounded geometries, fractals, and low--distortion embeddings
    FOCS, 2003
    [
    pdf doi
    ]
    (with Robert Krauthgamer, James R. Lee)
  191. Improved Approximations for Directed Multicut
    SODA, 2003
    [
    pdf doi
    ]
  192. 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)
  193. Lower Bounds for Embedding Edit Distance into Normed Spaces
    SODA, 2003
    [
    pdf doi
    ]
    (with Alexandr Andoni, Michel Marie Deza, Piotr Indyk, Sofya Raskhodnikova)

    194. 2002


  194. A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem
    FOCS, 2002
    [
    pdf doi
    ]
    (with Amit Kumar, Tim Roughgarden)
  195. 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)
  196. Approximation Algorithms for Unsplittable Flow Problems
    APPROX, 2002
    [
    pdf doi
    ]
    Algorithmica, 47(1):2007
    [
    doi
    ]
    (with Amit Chakrabarti, Chandra Chekuri, Amit Kumar)

    197. 2001


  197. 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)
  198. 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)
  199. Sorting and selection with structured costs
    FOCS, 2001
    [
    pdf doi
    ]
    (with Amit Kumar)
  200. Steiner points in tree metrics don't (really) help
    SODA, 2001
    [
    pdf doi
    ]

    201. 2000


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

    204. 1999


  204. Cuts, trees and $\ell_1$-embeddings of graphs
    FOCS, 1999
    [
    pdf doi
    ]
    Combinatorica, 24(2):2004
    [
    doi
    ]
    (with Ilan Newman, Yuri Rabinovich, Alistair Sinclair)
  205. Embedding tree metrics into low dimensional Euclidean spaces
    STOC, 1999
    [
    pdf doi
    ]
    Discrete Comput. Geom., 24(1):2000
    [
    doi
    ]
  206. 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: 2026-01-13.