>> Publications

DBLP | ACM DL | Google Scholar | BibTeX

    2011


  1. Approximation algorithms for network design: A survey
    Surveys in Operations Research and Management Science, 16(1):2011
    [
    doi
    ]
    (with Jochen Könemann)
  2. Iterative Constructions and Private Data Release
    ArXiv, abs/1107.3731, 2011
    [
    url
    ]
    (with Aaron Roth and Jonathan Ullman)
  3. Welfare and Profit Maximization with Production Costs
    ArXiv, abs/1110.4992, 2011
    [
    url
    ]
    FOCS, 2011
    [
    ]
    (with Avrim Blum, Yishay Mansour, and Ankit Sharma)
  4. Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits
    ArXiv, abs/1102.3749, 2011
    [
    url
    ]
    FOCS, 2011
    [
    ]
    (with Ravishankar Krishnaswamy, Marco Molinaro, and R. Ravi)
  5. Online Primal-Dual For Non-linear Optimization with Applications to Speed Scaling
    ArXiv, abs/1109.5931, 2011
    [
    url
    ]
    (with Ravishankar Krishnaswamy and Kirk Pruhs)
  6. Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
    SPAA, 2011
    [
    doi
    ]
    (with Guy E. Blelloch, Ioannis Koutis, Gary L. Miller, Richard Peng, and Kanat Tangwongsan)

    7. 2010


  7. Discovering pathways by orienting edges in protein interaction networks.
    Nucleic Acids Res, 2010
    [
    doi
    ]
    (with Anthony Gitter, Judith Klein-Seetharaman, and Ziv Bar-Joseph)
  8. Scheduling jobs with varying parallelizability to reduce variance
    SPAA, 2010
    [
    pdf doi
    ]
    (with Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, and Kirk Pruhs)
  9. When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
    ArXiv, abs/1008.5356, 2010
    [
    url
    ]
    ESA (2), 2010
    [
    doi
    ]
    (with Nikhil Bansal, Jian Li, Julián Mestre, Viswanath Nagarajan, and Atri Rudra)
  10. A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover
    SODA, 2010
    [
    doi
    ]
    (with Nikhil Bansal and Ravishankar Krishnaswamy)
  11. Vertex Sparsifiers: New Results from Old Techniques
    ArXiv, abs/1006.4586, 2010
    [
    url
    ]
    APPROX-RANDOM, 2010
    [
    doi
    ]
    (with Matthias Englert, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, and Kunal Talwar)
  12. Nonclairvoyantly scheduling power-heterogeneous processors
    International Green Computing Conference, 2010
    [
    pdf doi
    ]
    (with A. Gupta, R. Krishnaswamy, and K. Pruhs)
  13. Network-Wide Deployment of Intrusion Detection and Prevention Systems
    ACM CoNEXT, 2010
    [
    ]
    (with Vyas Sekar, Ravishankar Krishnaswamy, and Michael K. Reiter)
  14. 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)
  15. Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
    ICALP (1), 2010
    [
    doi
    ]
    ArXiv, abs/1003.0722, 2010
    [
    url
    ]
    (with Viswanath Nagarajan and R. Ravi)
  16. Tree Embeddings for Two-Edge-Connected Network Design
    SODA, 2010
    [
    doi
    ]
    (with Ravishankar Krishnaswamy and R. Ravi)
  17. 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)
  18. 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)
  19. Improved Approximation Algorithms for Requirement Cut
    Operations Research Letters, 38(4):2010
    [
    doi
    ]
    (with Viswanath Nagarajan and R. Ravi)
  20. Scalably Scheduling Power-Heterogeneous Processors
    ICALP (1), 2010
    [
    doi
    ]
    ArXiv, abs/1105.3748, 2011
    [
    url
    ]
    (with Ravishankar Krishnaswamy and Kirk Pruhs)
  21. Forest Density Estimation
    colt, 2010
    [
    url
    ]
    (with John Lafferty, Han Liu, Larry Wasserman, and Min Xu)

    22. 2009


  22. Secretary problems: weights and discounts
    SODA, 2009
    [
    pdf doi
    ]
    (with Moshe Babaioff, Michael Dinitz, Nicole Immorlica, and Kunal Talwar)
  23. Approximate clustering without the approximation
    SODA, 2009
    [
    pdf doi
    ]
    (with Maria-Florina Balcan and Avrim Blum)
  24. Scheduling with Outliers
    APPROX, 2009
    [
    doi
    ]
    ArXiv, abs/0906.2020, 2009
    [
    url
    ]
    (with Ravishankar Krishnaswamy, Amit Kumar, and Danny Segev)
  25. Simultaneous placement and scheduling of sensors
    IPSN, 2009
    [
    doi
    ]
    (with Andreas Krause, Ram Rajagopal, and Carlos Guestrin)
  26. A constant-factor approximation for stochastic Steiner forest
    STOC, 2009
    [
    pdf doi
    ]
    (with Amit Kumar)
  27. Online and stochastic survivable network design
    STOC, 2009
    [
    pdf doi
    ]
    (with Ravishankar Krishnaswamy and R. Ravi)
  28. Differentially Private Approximation Algorithms
    ArXiv, abs/0903.4510, 2009
    [
    url
    ]
    SODA, 2010
    [
    doi
    ]
    (with Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar)
  29. 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)

    30. 2008


  30. Approximating TSP on metrics with bounded global growth
    SODA, 2008
    [
    pdf doi
    ]
    (with T.-H. Hubert Chan)
  31. 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, and Danny Segev)
  32. Stochastic analyses for online combinatorial optimization problems
    SODA, 2008
    [
    pdf doi
    ]
    (with Naveen Garg, Stefano Leonardi, and Piotr Sankowski)
  33. All-Norms and All-$L_p$-Norms Approximation Algorithms
    FST&TCS, 2008
    [
    doi url
    ]
    (with Daniel Golovin, Amit Kumar, and Kanat Tangwongsan)
  34. Extracting Dynamics from Static Cancer Expression Data
    IEEE/ACM Trans. Comput. Biol. Bioinformatics, 5(2):2008
    [
    doi
    ]
    (with Ziv Bar-Joseph)
  35. Set Covering with our Eyes Closed
    FOCS, 2008
    [
    pdf doi
    ]
    (with Fabrizio Grandoni, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, and Mohit Singh)
  36. 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)
  37. 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, and Viswanath Nagarajan)
  38. Ultra-low-dimensional embeddings for doubling metrics
    SODA, 2008
    [
    pdf doi
    ]
    J. ACM, 57(4):2010
    [
    doi
    ]
    (with T.-H. Hubert Chan and Kunal Talwar)
  39. Simpler Analyses of Local Search Algorithms for Facility Location
    ArXiv, abs/0809.2554, 2008
    [
    url
    ]
    (with Kanat Tangwongsan)

    40. 2007


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

    48. 2006


  48. Oblivious network design
    SODA, 2006
    [
    pdf doi
    ]
    (with MohammadTaghi Hajiaghayi and Harald Räcke)
  49. Quorum placement in networks: minimizing network congestion
    PODC, 2006
    [
    pdf doi
    ]
    (with Daniel Golovin, Bruce M. Maggs, Florian Oprea, and Michael K. Reiter)
  50. Spanners with Slack
    ESA, 2006
    [
    pdf doi
    ]
    (with T.-H. Hubert Chan and Michael Dinitz)
  51. Approximating unique games
    SODA, 2006
    [
    pdf doi
    ]
    (with Kunal Talwar)
  52. Near-optimal sensor placements: maximizing information while minimizing communication cost
    Conference on Information Processing in Sensor Networks, 2006
    [
    doi
    ]
    TOSN, 7(4):2011
    [
    doi
    ]
    (with Andreas Krause, Carlos Guestrin, and Jon M. Kleinberg)
  53. Small hop-diameter sparse spanners for doubling metrics
    SODA, 2006
    [
    pdf doi
    ]
    Discrete & Computational Geometry, 41(1):2009
    [
    doi
    ]
    (with T.-H. Hubert Chan)
  54. Improved embeddings of graph metrics into random trees
    SODA, 2006
    [
    doi
    ]
    (with Kedar Dhamdhere and Harald Räcke)

    55. 2005


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

    65. 2004


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

    69. 2003


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

    79. 2002


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

    82. 2001


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

    86. 2000


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

    89. 1999


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