>> Publications


DBLP | ACM DL | Google Scholar | BibTeX


    2020


  1. Online Carpooling using Expander Decompositions
    ArXiv, abs/2007.10545, 2020
    [
    url
    ]
    FSTTCS, 2020
    [ ]
    (with Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla)
  2. 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)
  3. Fully-Dynamic Submodular Cover with Bounded Recourse
    ArXiv, abs/2009.00800, 2020
    [
    url
    ]
    FOCS, 2020
    [
    ]
    (with Roie Levin)
  4. Dimension-Free Bounds for Chasing Convex Functions
    COLT, 2020
    [
    url
    ]
    (with C. J. Argue, Guru Guruganesh)
  5. Optimal Bounds for the k-cut Problem
    ArXiv, abs/2005.08301, 2020
    [
    url
    ]
    (with David G. Harris, Euiwoong Lee, Jason Li)
  6. The Online Submodular Cover Problem
    SODA, 2020
    [ ]
    (with Roie Levin)
  7. Chasing Convex Bodies with Linear Competitive Ratio
    ArXiv, abs/1905.11877, 2019
    [
    url
    ]
    SODA, 2020
    [ ]
    (with C. J. Argue, Guru Guruganesh, Ziye Tang)
  8. Random-Order Models
    ArXiv, abs/2002.12159, 2020
    [
    url
    ]
    (with Sahil Singla)
  9. Stochastic Makespan Minimization in Structured Set Systems
    ArXiv, abs/2002.11153, 2020
    [
    url
    ]
    IPCO, 2020
    [ ]
    (with Amit Kumar, Viswanath Nagarajan, Xiangkun Shen)
  10. Robust Algorithms for the Secretary Problem
    ArXiv, abs/1911.07352, 2019
    [
    url
    ]
    ITCS, 2020
    [ ]
    (with Domagoj Bradac, Sahil Singla, Goran Zuzic)
  11. The Karger-Stein Algorithm is Optimal for k-Cut
    STOC, 2020
    [ ]
    ArXiv, abs/1911.09165, 2019
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  12. Caching with Time-Windows
    STOC, 2020
    [ ]
    ArXiv, abs/2006.09665, 2020
    [
    url
    ]
    (with Amit Kumar, Debmalya Panigrahi)


  13. 2019


  14. Potential-Function Proofs for Gradient Methods
    Theory of Computing, 15(4):2019
    [ ]
    ArXiv, abs/1712.04581, 2017
    [
    url
    ]
    (with Nikhil Bansal)
  15. 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)
  16. Stochastic Online Metric Matching
    ICALP, 2019
    [ ]
    ArXiv, abs/1904.09284, 2019
    [
    url
    ]
    (with Guru Guruganesh, Binghui Peng, David Wajc)
  17. Non-clairvoyant Precedence Constrained Scheduling
    ArXiv, abs/1905.02133, 2019
    [
    url
    ]
    ICALP, 2019
    [ ]
    (with Naveen Garg, Amit Kumar, Sahil Singla)
  18. Tight FPT Approximations for k-Median and k-Means
    ICALP, 2019
    [ ]
    (with Vincent Cohen-Addad, Amit Kumar, Euiwoong Lee, Jason Li)
  19. Better Algorithms for Stochastic Bandits with Adversarial Corruptions
    COLT, 2019
    [
    url
    ]
    ArXiv, abs/1902.08647, 2019
    [
    url
    ]
    (with Tomer Koren, Kunal Talwar)
  20. The Markovian Price of Information
    ArXiv, abs/1902.07856, 2019
    [
    url
    ]
    IPCO, 2019
    [ ]
    (with Haotian Jiang, Ziv Scully, Sahil Singla)
  21. Losing Treewidth by Separating Subsets
    SODA, 2019
    [ ]
    ArXiv, abs/1804.01366, 2018
    [
    url
    ]
    (with Euiwoong Lee, Jason Li, Pasin Manurangsi, Michal Wlodarczyk)
  22. Elastic Caching
    SODA, 2019
    [ ]
    (with Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi)
  23. k-Servers with a Smile: Online Algorithms via Projections
    ArXiv, abs/1810.07508, 2018
    [
    url
    ]
    SODA, 2019
    [ ]
    (with Niv Buchbinder, Marco Molinaro, Joseph Naor)
  24. 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)


  25. 2018


  26. Faster Exact and Approximate Algorithms for k-Cut
    FOCS, 2018
    [ ]
    ArXiv, abs/1807.08144, 2018
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  27. Maximizing Profit with Convex Costs in the Random-order Model
    ICALP, 2018
    [
    url
    ]
    ArXiv, abs/1804.08172, 2018
    [
    url
    ]
    (with Ruta Mehta, Marco Molinaro)
  28. Non-Preemptive Flow-Time Minimization via Rejections
    ICALP, 2018
    [
    url
    ]
    ArXiv, abs/1805.09602, 2018
    [
    url
    ]
    (with Amit Kumar, Jason Li)
  29. 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)
  30. Metric Embedding via Shortest Path Decompositions
    STOC, 2018
    [
    url
    ]
    ArXiv, abs/1708.04073, 2017
    [
    url
    ]
    (with Ittai Abraham, Arnold Filtser, Ofer Neiman)
  31. An FPT Algorithm Beating 2-Approximation for \emph{k}-Cut
    SODA, 2018
    [ ]
    ArXiv, abs/1710.08488, 2017
    [
    url
    ]
    (with Euiwoong Lee, Jason Li)
  32. Stochastic Load Balancing on Unrelated Machines
    ArXiv, abs/1904.07271, 2019
    [
    url
    ]
    SODA, 2018
    [ ]
    (with Amit Kumar, Viswanath Nagarajan, Xiangkun Shen)
  33. 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)


  34. 2017


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


  40. 2016


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


  46. 2015


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


  50. 2014


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


  58. 2013


  59. Random Rates for 0-Extension and Low-Diameter Decompositions
    ArXiv, 1307.5582, 2013
    [
    url
    ]
    (with Kunal Talwar)
  60. Harnessing the Power of Two Crossmatches
    14th ACM Conference on Electronic Commerce, 2013
    [
    doi
    ]
    (with Avrim Blum, Ariel Procaccia, Ankit Sharma)
  61. Algorithms for Hub Label Optimization
    ACM Trans. Algorithms, 13(1):2016
    [ ]
    ICALP, 2013
    [
    doi
    ]
    (with Maxim A. Babenko, Andrew V. Goldberg, Viswanath Nagarajan)
  62. On the Non-Uniform Sparsest Cut Problem on Bounded Treewidth Graphs
    STOC, 2013
    [
    doi
    ]
    ArXiv, 1305.1347, 2013
    [
    url
    ]
    (with Kunal Talwar, David Witmer)
  63. The Approximability of the Binary Paintshop Problem
    APPROX-RANDOM, 2013
    [
    doi
    ]
    (with Satyen Kale, Viswanath Nagarajan, Rishi Saket, Baruch Schieber)
  64. 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)
  65. Thrifty Algorithms for Multistage Robust Optimization
    IPCO, 2013
    [
    doi
    ]
    ArXiv, 1302.5445, 2013
    [
    url
    ]
    (with Viswanath Nagarajan, Vijay V. Vazirani)
  66. A Stochastic Probing Problem with Applications
    IPCO, 2013
    [
    doi
    ]
    ArXiv, 1302.5913, 2013
    [
    url
    ]
    (with Viswanath Nagarajan)
  67. 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)
  68. Packing Interdiction and Partial Covering Problems
    IPCO, 2013
    [
    doi
    ]
    (with Michael Dinitz)
  69. 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)


  70. 2012


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


  80. 2011


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


  86. 2010


  87. Discovering pathways by orienting edges in protein interaction networks.
    Nucleic Acids Res, 2010
    [
    doi
    ]
    (with Anthony Gitter, Judith Klein-Seetharaman, Ziv Bar-Joseph)
  88. Network-Wide Deployment of Intrusion Detection and Prevention Systems
    ACM CoNEXT, 2010
    [ ]
    (with Vyas Sekar, Ravishankar Krishnaswamy, Michael K. Reiter)
  89. 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)
  90. 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)
  91. Improved Approximation Algorithms for Requirement Cut
    Operations Research Letters, 38(4):2010
    [
    doi
    ]
    (with Viswanath Nagarajan, R. Ravi)
  92. 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)
  93. 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)
  94. Tree Embeddings for Two-Edge-Connected Network Design
    SODA, 2010
    [
    doi
    ]
    (with Ravishankar Krishnaswamy, R. Ravi)
  95. Nonclairvoyantly scheduling power-heterogeneous processors
    Sustainable Computing: Informatics and Systems, 1(3):2011
    [
    doi
    ]
    International Green Computing Conference, 2010
    [ ]
    (with Ravishankar Krishnaswamy, Kirk Pruhs)
  96. Scalably Scheduling Power-Heterogeneous Processors
    ICALP (1), 2010
    [
    doi
    ]
    ArXiv, abs/1105.3748, 2011
    [
    url
    ]
    (with Ravishankar Krishnaswamy, Kirk Pruhs)
  97. Scheduling jobs with varying parallelizability to reduce variance
    SPAA, 2010
    [ ]
    (with Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs)
  98. 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)
  99. 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)
  100. A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover
    SODA, 2010
    [
    doi
    ]
    (with Nikhil Bansal, Ravishankar Krishnaswamy)


  101. 2009


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


  110. 2008


  111. 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)
  112. Simpler Analyses of Local Search Algorithms for Facility Location
    ArXiv, abs/0809.2554, 2008
    [
    url
    ]
    (with Kanat Tangwongsan)
  113. Extracting Dynamics from Static Cancer Expression Data
    IEEE/ACM Trans. Comput. Biol. Bioinformatics, 5(2):2008
    [
    doi
    ]
    (with Ziv Bar-Joseph)
  114. 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)
  115. All-Norms and All-$L_p$-Norms Approximation Algorithms
    FST&TCS, 2008
    [ ]
    (with Daniel Golovin, Amit Kumar, Kanat Tangwongsan)
  116. Stochastic analyses for online combinatorial optimization problems
    SODA, 2008
    [ ]
    (with Naveen Garg, Stefano Leonardi, Piotr Sankowski)
  117. 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)
  118. Ultra-low-dimensional embeddings for doubling metrics
    SODA, 2008
    [ ]
    J. ACM, 57(4):2010
    [
    doi
    ]
    (with T.-H. Hubert Chan, Kunal Talwar)
  119. Approximating TSP on Metrics with Bounded Global Growth
    SIAM Journal on Computing, 41(3):2012
    [
    doi
    ]
    SODA, 2008
    [ ]
    (with T.-H. Hubert Chan)
  120. A plant location guide for the unsure
    SODA, 2008
    [ ]
    Math. Oper. Res., 35(1):2010
    [ ]
    (with Barbara M. Anthony, Vineet Goyal, Viswanath Nagarajan)


  121. 2007


  122. How to Complete a Doubling Metric
    ArXiv, abs/0712.3331, 2007
    [
    url
    ]
    LATIN, 2008
    [
    doi
    ]
    Algorithmica, 59(1):2011
    [
    doi
    ]
    (with Kunal Talwar)
  123. 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)
  124. 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)
  125. Stochastic Steiner Tree with Non-Uniform Inflation
    APPROX, 2007
    [ ]
    (with MohammadTaghi Hajiaghayi, Amit Kumar)
  126. Pricing Tree Access Networks with Connected Backbones
    ESA, 2007
    [ ]
    (with Vineet Goyal, Stefano Leonardi, R. Ravi)
  127. 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)
  128. 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)
  129. Infrastructure Leasing Problems
    IPCO, 2007
    [ ]
    (with Barbara M. Anthony)


  130. 2006


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


  138. 2005


  139. What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization
    APPROX, 2005
    [ ]
    (with Martin Pál, R. Ravi, Amitabh Sinha)
  140. Stochastic Steiner Trees Without a Root
    ICALP, 2005
    [ ]
    (with Martin Pál)
  141. Quorum placement in networks to minimize access delays
    PODC, 2005
    [ ]
    (with Bruce M. Maggs, Florian Oprea, Michael K. Reiter)
  142. Where's the Winner? Max-Finding and Sorting with Metric Costs
    APPROX, 2005
    [ ]
    (with Amit Kumar)
  143. On the Approximability of Network Design Problems
    SODA, 2005
    [ ]
    ACM Trans. Algorithms, 4(2):2008
    [
    doi
    ]
    (with Julia Chuzhoy, Joseph (Seffi) Naor, Amitabh Sinha)
  144. On a bidirected relaxation for the Multiway {Cut} problem
    Discrete Appl. Math., 150(1-3):2005
    [
    doi
    ]
    (with Chandra Chekuri, Amit Kumar)
  145. Improved Approximations for Sparsest {Cut}
    SODA, 2005
    [ ]
    ACM Trans. Algorithms, 4(2):2008
    [
    doi
    ]
    (with Shuchi Chawla, Harald Räcke)
  146. On Hierarchical Routing in Doubling Metrics
    ACM Trans. Algorithms, 12(4):2016
    [ ]
    SODA, 2005
    [ ]
    (with T.-H. Hubert Chan, Bruce M. Maggs, Shuheng Zhou)
  147. 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)
  148. 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)


  149. 2004


  150. Cost-Sharing Mechanisms for Network Design.
    APPROX, 2004
    [ ]
    Algorithmica, 50(1):2008
    [
    doi
    ]
    (with Aravind Srinivasan, \'Eva Tardos)
  151. 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)
  152. 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)
  153. Approximation Algorithms for Minimizing Average Distortion
    STACS, 2004
    [ ]
    Theory of Computing Systems, 39(1):2006
    [
    doi
    ]
    (with Kedar Dhamdhere, R. Ravi)


  154. 2003


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


  165. 2002


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


  169. 2001


  170. Traveling with a Pez dispenser (or, routing issues in {MPLS})
    FOCS, 2001
    [ ]
    SIAM J. Comput., 34(2):2004
    [
    doi
    ]
    (with Amit Kumar, Rajeev Rastogi)
  171. 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)
  172. Sorting and selection with structured costs
    FOCS, 2001
    [ ]
    (with Amit Kumar)
  173. Steiner points in tree metrics don't (really) help
    SODA, 2001
    [ ]


  174. 2000


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


  178. 1999


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