>> Publications


DBLP | ACM DL | Google Scholar | BibTeX


    2013


  1. Algorithms for Hub Label Optimization
    ICALP, 2013
    [
    ]
    (with Maxim Babenko, Andrew V. Goldberg, and Viswanath Nagarajan)
  2. Harnessing the Power of Two Crossmatches
    14th ACM Conference on Electronic Commerce, 2013
    [
    ]
    (with Avrim Blum, Ariel Procaccia, and Ankit Sharma)
  3. On the Non-Uniform Sparsest Cut Problem on Bounded Treewidth Graphs
    STOC, 2013
    [
    ]
    (with Kunal Talwar and David Witmer)
  4. The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
    STOC, 2013
    [
    ]
    (with Albert Gu and Amit Kumar)
  5. Thrifty Algorithms for Multistage Robust Optimization
    ArXiv, 1302.5445, 2013
    [
    url
    ]
    IPCO, 2013
    [
    doi
    ]
    (with Viswanath Nagarajan and Vijay V. Vazirani)
  6. A Stochastic Probing Problem with Applications
    IPCO, 2013
    [
    doi
    ]
    ArXiv, 1302.5913, 2013
    [
    url
    ]
    (with Viswanath Nagarajan)
  7. An Improved Integrality Gap for Asymmetric TSP Paths
    IPCO, 2013
    [
    doi
    ]
    ArXiv, abs/1302.3145, 2013
    [
    url
    ]
    (with Zachary Friggstad and Mohit Singh)
  8. Packing Interdiction and Partial Covering Problems
    IPCO, 2013
    [
    doi
    ]
    (with Michael Dinitz)
  9. Catch Them If You Can: How to Serve Impatient Users
    Innovations in Theoretical Computer Science Conference, 2013
    [ ]
    (with Marek Cygan, Matthias Englert, Marcin Mucha, and Piotr Sankowski)


  10. 2012


  11. Multicast Routing for Energy Minimization Using Speed Scaling
    First Mediterranean Conference on Algorithms (MedAlg), 2012
    [
    doi
    ]
    (with Nikhil Bansal, Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, and Cliff Stein)
  12. Online Primal-Dual For Non-linear Optimization with Applications to Speed Scaling
    ArXiv, abs/1109.5931, 2011
    [
    url
    ]
    Workshop on Approximation and Online Algorithms, 2012
    [
    ]
    (with Ravishankar Krishnaswamy and Kirk Pruhs)
  13. Parallel Probabilistic Tree Embeddings, k-Median, and Buy-at-Bulk Network Design
    SPAA, 2012
    [
    doi
    ]
    (with Guy E. Blelloch and Kanat Tangwongsan)
  14. The Online Metric Matching Problem for Doubling Metrics
    ICALP (1), 2012
    [
    doi
    ]
    (with Kevin Lewi)
  15. Approximating Sparse Covering Integer Programs Online
    ArXiv, abs/1205.0175, 2012
    [
    url
    ]
    ICALP (1), 2012
    [
    doi
    ]
    (with Viswanath Nagarajan)
  16. Iterative Constructions and Private Data Release
    ArXiv, abs/1107.3731, 2011
    [
    url
    ]
    TCC, 2012
    [
    doi
    ]
    (with Aaron Roth and Jonathan Ullman)
  17. Scheduling Heterogeneous Processors Isn't As Easy As You Think
    SODA, 2012
    [
    url
    ]
    (with Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, and Kirk Pruhs)
  18. Approximation Algorithms for Stochastic Orienteering
    SODA, 2012
    [
    url
    ]
    (with Ravishankar Krishnaswamy, Viswanath Nagarajan, and R. Ravi)
  19. Approximation Algorithms for VRP with Stochastic Demands
    Operations Research, 60(1):2012
    [
    doi
    ]
    (with Viswanath Nagarajan and R. Ravi)


  20. 2011


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


  26. 2010


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


  41. 2009


  42. Simultaneous placement and scheduling of sensors
    IPSN, 2009
    [
    doi
    ]
    IEEE Transactions on Automatic Control, 56(10):2011
    [
    doi
    ]
    (with Andreas Krause, Ram Rajagopal, and Carlos Guestrin)
  43. Thresholded Covering Algorithms for Robust and Max-Min Optimization
    ArXiv, abs/0912.1045, 2009
    [
    url
    ]
    ArXiv, abs/1012.4962, 2010
    [
    url
    ]
    ICALP (1), 2010
    [
    doi
    ]
    (with Viswanath Nagarajan and R. Ravi)
  44. Scheduling with Outliers
    ArXiv, abs/0906.2020, 2009
    [
    url
    ]
    APPROX, 2009
    [
    doi
    ]
    (with Ravishankar Krishnaswamy, Amit Kumar, and Danny Segev)
  45. Online and stochastic survivable network design
    STOC, 2009
    [ ]
    SIAM J. Comput., 41(6):2012
    [
    doi
    ]
    (with Ravishankar Krishnaswamy and R. Ravi)
  46. A constant-factor approximation for stochastic Steiner forest
    STOC, 2009
    [ ]
    (with Amit Kumar)
  47. Approximate clustering without the approximation
    JACM, to appear
    [
    ]
    SODA, 2009
    [ ]
    (with Maria-Florina Balcan and Avrim Blum)
  48. Secretary problems: weights and discounts
    SODA, 2009
    [ ]
    (with Moshe Babaioff, Michael Dinitz, Nicole Immorlica, and Kunal Talwar)
  49. Differentially Private Approximation Algorithms
    ArXiv, abs/0903.4510, 2009
    [
    url
    ]
    SODA, 2010
    [
    doi
    ]
    (with Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar)


  50. 2008


  51. Approximating TSP on metrics with bounded global growth
    SODA, 2008
    [ ]
    SIAM Journal on Computing, 41(3):2012
    [
    doi
    ]
    (with T.-H. Hubert Chan)
  52. Selecting Observations against Adversarial Objectives
    Advances in Neural Information Processing Systems 20, 2008
    [
    url
    ]
    Journal of Machine Learning Research, 9, 2008
    [
    url
    ]
    (with Andreas Krause, Brendan McMahan, and Carlos Guestrin)
  53. Simpler Analyses of Local Search Algorithms for Facility Location
    ArXiv, abs/0809.2554, 2008
    [
    url
    ]
    (with Kanat Tangwongsan)
  54. Ultra-low-dimensional embeddings for doubling metrics
    SODA, 2008
    [ ]
    J. ACM, 57(4):2010
    [
    doi
    ]
    (with T.-H. Hubert Chan and Kunal Talwar)
  55. Extracting Dynamics from Static Cancer Expression Data
    IEEE/ACM Trans. Comput. Biol. Bioinformatics, 5(2):2008
    [
    doi
    ]
    (with Ziv Bar-Joseph)
  56. All-Norms and All-$L_p$-Norms Approximation Algorithms
    FST&TCS, 2008
    [ ]
    (with Daniel Golovin, Amit Kumar, and Kanat Tangwongsan)
  57. 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, and Danny Segev)
  58. Stochastic analyses for online combinatorial optimization problems
    SODA, 2008
    [ ]
    (with Naveen Garg, Stefano Leonardi, and Piotr Sankowski)
  59. Set Covering with our Eyes Closed
    FOCS, 2008
    [ ]
    (with Fabrizio Grandoni, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, and Mohit Singh)
  60. A plant location guide for the unsure
    SODA, 2008
    [ ]
    Math. Oper. Res., 35(1):2010
    [ ]
    (with Barbara M. Anthony, Vineet Goyal, and Viswanath Nagarajan)


  61. 2007


  62. How to Complete a Doubling Metric
    ArXiv, abs/0712.3331, 2007
    [
    url
    ]
    LATIN, 2008
    [
    doi
    ]
    Algorithmica, 59(1):2011
    [
    doi
    ]
    (with Kunal Talwar)
  63. Infrastructure Leasing Problems
    IPCO, 2007
    [ ]
    (with Barbara M. Anthony)
  64. Stochastic Steiner Tree with Non-Uniform Inflation
    APPROX, 2007
    [ ]
    (with MohammadTaghi Hajiaghayi and Amit Kumar)
  65. An Efficient Cost-Sharing Mechanism for the Prize-Collecting Steiner Forest Problem
    SODA, 2007
    [ ]
    (with Jochen Könemann, Stefano Leonardi, R. Ravi, and Guido Schäfer)
  66. On Configuring BGP Route Reflectors
    2nd International Conference on COMmunication System softWAre and MiddlewaRE (COMSWARE), 2007
    [
    doi
    ]
    (with Yuri Breitbart, Minos N. Garofalakis, Amit Kumar, and Rajeev Rastogi)
  67. A Randomized $O(\log^2 k)$-Competitive Algorithm for Metric Bipartite Matching
    Algorithmica, 2012
    [
    doi
    ]
    ESA, 2007
    [ ]
    (with Nikhil Bansal, Niv Buchbinder, and Joseph Naor)
  68. Pricing Tree Access Networks with Connected Backbones
    ESA, 2007
    [ ]
    (with Vineet Goyal, Stefano Leonardi, and R. Ravi)
  69. 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, and R. Ravi)


  70. 2006


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


  78. 2005


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


  89. 2004


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


  94. 2003


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


  105. 2002


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


  109. 2001


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


  114. 2000


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


  118. 1999


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