>>
Publications
DBLP
|
ACM DL
|
Google Scholar
|
BibTeX
2013
Algorithms for Hub Label Optimization
ICALP, 2013
[
]
(with Maxim Babenko, Andrew V. Goldberg, and Viswanath Nagarajan)
Harnessing the Power of Two Crossmatches
14th ACM Conference on Electronic Commerce, 2013
[
]
(with Avrim Blum, Ariel Procaccia, and Ankit Sharma)
On the Non-Uniform Sparsest Cut Problem on Bounded Treewidth Graphs
STOC, 2013
[
]
(with Kunal Talwar and David Witmer)
The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
STOC, 2013
[
]
(with Albert Gu and Amit Kumar)
Thrifty Algorithms for Multistage Robust Optimization
ArXiv, 1302.5445, 2013
[
url
]
IPCO, 2013
[
doi
]
(with Viswanath Nagarajan and Vijay V. Vazirani)
A Stochastic Probing Problem with Applications
IPCO, 2013
[
doi
]
ArXiv, 1302.5913, 2013
[
url
]
(with Viswanath Nagarajan)
An Improved Integrality Gap for Asymmetric TSP Paths
IPCO, 2013
[
doi
]
ArXiv, abs/1302.3145, 2013
[
url
]
(with Zachary Friggstad and Mohit Singh)
Packing Interdiction and Partial Covering Problems
IPCO, 2013
[
doi
]
(with Michael Dinitz)
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, and Piotr Sankowski)
2012
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)
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)
Parallel Probabilistic Tree Embeddings, k-Median, and Buy-at-Bulk Network Design
SPAA, 2012
[
doi
]
(with Guy E. Blelloch and Kanat Tangwongsan)
The Online Metric Matching Problem for Doubling Metrics
ICALP (1), 2012
[
doi
]
(with Kevin Lewi)
Approximating Sparse Covering Integer Programs Online
ArXiv, abs/1205.0175, 2012
[
url
]
ICALP (1), 2012
[
doi
]
(with Viswanath Nagarajan)
Iterative Constructions and Private Data Release
ArXiv, abs/1107.3731, 2011
[
url
]
TCC, 2012
[
doi
]
(with Aaron Roth and Jonathan Ullman)
Scheduling Heterogeneous Processors Isn't As Easy As You Think
SODA, 2012
[
url
]
(with Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, and Kirk Pruhs)
Approximation Algorithms for Stochastic Orienteering
SODA, 2012
[
url
]
(with Ravishankar Krishnaswamy, Viswanath Nagarajan, and R. Ravi)
Approximation Algorithms for VRP with Stochastic Demands
Operations Research, 60(1):2012
[
doi
]
(with Viswanath Nagarajan and R. Ravi)
2011
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)
Welfare and Profit Maximization with Production Costs
FOCS, 2011
[
doi
]
ArXiv, abs/1110.4992, 2011
[
url
]
(with Avrim Blum, Yishay Mansour, and Ankit Sharma)
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)
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)
Approximation algorithms for network design: A survey
Surveys in Operations Research and Management Science, 16(1):2011
[
pdf
doi
]
(with Jochen Könemann)
2010
Discovering pathways by orienting edges in protein interaction networks.
Nucleic Acids Res, 2010
[
doi
]
(with Anthony Gitter, Judith Klein-Seetharaman, and Ziv Bar-Joseph)
Scalably Scheduling Power-Heterogeneous Processors
ICALP (1), 2010
[
doi
]
ArXiv, abs/1105.3748, 2011
[
url
]
(with Ravishankar Krishnaswamy and Kirk Pruhs)
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)
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)
Network-Wide Deployment of Intrusion Detection and Prevention Systems
ACM CoNEXT, 2010
[
doi
url
]
(with Vyas Sekar, Ravishankar Krishnaswamy, and Michael K. Reiter)
A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover
SODA, 2010
[
doi
]
(with Nikhil Bansal and Ravishankar Krishnaswamy)
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)
Improved Approximation Algorithms for Requirement Cut
Operations Research Letters, 38(4):2010
[
doi
]
(with Viswanath Nagarajan and R. Ravi)
Scheduling jobs with varying parallelizability to reduce variance
SPAA, 2010
[
pdf
doi
]
(with Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, and Kirk Pruhs)
Tree Embeddings for Two-Edge-Connected Network Design
SODA, 2010
[
doi
]
(with Ravishankar Krishnaswamy and R. Ravi)
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)
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)
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)
Nonclairvoyantly scheduling power-heterogeneous processors
International Green Computing Conference, 2010
[
pdf
doi
]
Sustainable Computing: Informatics and Systems, 1(3):2011
[
doi
]
(with Ravishankar Krishnaswamy and Kirk Pruhs)
2009
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)
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)
Scheduling with Outliers
ArXiv, abs/0906.2020, 2009
[
url
]
APPROX, 2009
[
doi
]
(with Ravishankar Krishnaswamy, Amit Kumar, and Danny Segev)
Online and stochastic survivable network design
STOC, 2009
[
pdf
doi
]
SIAM J. Comput., 41(6):2012
[
doi
]
(with Ravishankar Krishnaswamy and R. Ravi)
A constant-factor approximation for stochastic Steiner forest
STOC, 2009
[
pdf
doi
]
(with Amit Kumar)
Approximate clustering without the approximation
JACM, to appear
[
]
SODA, 2009
[
pdf
doi
]
(with Maria-Florina Balcan and Avrim Blum)
Secretary problems: weights and discounts
SODA, 2009
[
pdf
doi
]
(with Moshe Babaioff, Michael Dinitz, Nicole Immorlica, and Kunal Talwar)
Differentially Private Approximation Algorithms
ArXiv, abs/0903.4510, 2009
[
url
]
SODA, 2010
[
doi
]
(with Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar)
2008
Approximating TSP on metrics with bounded global growth
SODA, 2008
[
pdf
doi
]
SIAM Journal on Computing, 41(3):2012
[
doi
]
(with T.-H. Hubert Chan)
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)
Simpler Analyses of Local Search Algorithms for Facility Location
ArXiv, abs/0809.2554, 2008
[
url
]
(with Kanat Tangwongsan)
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)
Extracting Dynamics from Static Cancer Expression Data
IEEE/ACM Trans. Comput. Biol. Bioinformatics, 5(2):2008
[
doi
]
(with Ziv Bar-Joseph)
All-Norms and All-$L_p$-Norms Approximation Algorithms
FST&TCS, 2008
[
doi
url
]
(with Daniel Golovin, Amit Kumar, and Kanat Tangwongsan)
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)
Stochastic analyses for online combinatorial optimization problems
SODA, 2008
[
pdf
doi
]
(with Naveen Garg, Stefano Leonardi, and Piotr Sankowski)
Set Covering with our Eyes Closed
FOCS, 2008
[
pdf
doi
]
(with Fabrizio Grandoni, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, and Mohit Singh)
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)
2007
How to Complete a Doubling Metric
ArXiv, abs/0712.3331, 2007
[
url
]
LATIN, 2008
[
doi
]
Algorithmica, 59(1):2011
[
doi
]
(with Kunal Talwar)
Infrastructure Leasing Problems
IPCO, 2007
[
pdf
doi
]
(with Barbara M. Anthony)
Stochastic Steiner Tree with Non-Uniform Inflation
APPROX, 2007
[
pdf
doi
]
(with MohammadTaghi Hajiaghayi and Amit Kumar)
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)
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)
A Randomized $O(\log^2 k)$-Competitive Algorithm for Metric Bipartite Matching
Algorithmica, 2012
[
doi
]
ESA, 2007
[
pdf
doi
]
(with Nikhil Bansal, Niv Buchbinder, and Joseph Naor)
Pricing Tree Access Networks with Connected Backbones
ESA, 2007
[
pdf
doi
]
(with Vineet Goyal, Stefano Leonardi, and R. Ravi)
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)
2006
Oblivious network design
SODA, 2006
[
pdf
doi
]
(with MohammadTaghi Hajiaghayi and Harald Räcke)
Improved embeddings of graph metrics into random trees (article withdrawn)
SODA, 2006
[
doi
]
(with Kedar Dhamdhere and Harald Räcke)
Small hop-diameter sparse spanners for doubling metrics
SODA, 2006
[
pdf
doi
]
Discrete & Computational Geometry, 41(1):2009
[
doi
]
(with T.-H. Hubert Chan)
Spanners with Slack
ESA, 2006
[
pdf
doi
]
(with T.-H. Hubert Chan and Michael Dinitz)
Approximating unique games
SODA, 2006
[
pdf
doi
]
(with Kunal Talwar)
Quorum placement in networks: minimizing network congestion
PODC, 2006
[
pdf
doi
]
(with Daniel Golovin, Bruce M. Maggs, Florian Oprea, and Michael K. Reiter)
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)
2005
On a bidirected relaxation for the Multiway {Cut} problem
Discrete Appl. Math., 150(1-3):2005
[
doi
]
(with Chandra Chekuri and Amit Kumar)
Stochastic Steiner Trees Without a Root
ICALP, 2005
[
pdf
doi
]
(with Martin Pál)
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)
On Hierarchical Routing in Doubling Metrics
SODA, 2005
[
pdf
doi
]
(with T.-H. Hubert Chan, Bruce M. Maggs, and Shuheng Zhou)
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)
Quorum placement in networks to minimize access delays
PODC, 2005
[
pdf
doi
]
(with Bruce M. Maggs, Florian Oprea, and Michael K. Reiter)
Where's the Winner? Max-Finding and Sorting with Metric Costs
APPROX, 2005
[
pdf
doi
]
(with Amit Kumar)
Improved Approximations for Sparsest {Cut}
SODA, 2005
[
pdf
doi
]
ACM Trans. Algorithms, 4(2):2008
[
doi
]
(with Shuchi Chawla and Harald Räcke)
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)
What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization
APPROX, 2005
[
pdf
doi
]
(with Martin Pál, R. Ravi, and Amitabh Sinha)
2004
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)
Boosted Sampling: Approximation algorithms for stochastic optimization problems
STOC, 2004
[
pdf
doi
]
SIAM J. Comput., 40(5):2011
[
doi
]
(with Martin Pál, R. Ravi, and Amitabh Sinha)
Cost-Sharing Mechanisms for Network Design.
APPROX, 2004
[
pdf
doi
]
Algorithmica, 50(1):2008
[
doi
]
(with Aravind Srinivasan and \'Eva Tardos)
Approximation Algorithms for Minimizing Average Distortion
STACS, 2004
[
pdf
doi
]
Theory of Computing Systems, 39(1):2006
[
doi
]
(with Kedar Dhamdhere and R. Ravi)
2003
On the Covering {Steiner} Problem
FST&TCS, 2003
[
pdf
doi
]
Theory of Computing, 2, 2006
[
doi
]
(with Aravind Srinivasan)
Tree based MPLS routing
SPAA, 2003
[
doi
]
(with Amit Kumar and Mikkel Thorup)
Simpler and Better Approximation Algorithms for Network Design
STOC, 2003
[
pdf
doi
]
(with Amit Kumar and Tim Roughgarden)
Improved Approximations for Directed Multicut
SODA, 2003
[
pdf
doi
]
Lower Bounds for Embedding Edit Distance into Normed Spaces
SODA, 2003
[
pdf
doi
]
(with Alexandr Andoni, Michel Marie Deza, Piotr Indyk, and Sofya Raskhodnikova)
Bounded geometries, fractals, and low--distortion embeddings
FOCS, 2003
[
pdf
doi
]
(with Robert Krauthgamer and James R.\ Lee)
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)
Counting Inversions in Lists
SODA, 2003
[
pdf
doi
]
(with Francis X. Zane)
Exploring the Trade-off between Label Size and Stack Depth in MPLS Routing
INFOCOM, 2003
[
]
(with Amit Kumar and Rajeev Rastogi)
Approximations via Cost-Sharing
FOCS, 2003
[
pdf
doi
]
J. ACM, 54(3):2007
[
doi
]
(with Amit Kumar, Martin Pál, and Tim Roughgarden)
2002
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)
Approximation Algorithms for Unsplittable Flow Problems
APPROX, 2002
[
pdf
doi
]
Algorithmica, 47(1):2007
[
doi
]
(with Amit Chakrabarti, Chandra Chekuri, and Amit Kumar)
A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem
FOCS, 2002
[
pdf
doi
]
(with Amit Kumar and Tim Roughgarden)
2001
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)
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)
Sorting and selection with structured costs
FOCS, 2001
[
pdf
doi
]
(with Amit Kumar)
Steiner points in tree metrics don't (really) help
SODA, 2001
[
pdf
doi
]
2000
Improved bandwidth approximation for trees
SODA, 2000
[
pdf
doi
]
J. Algorithms, 40(1):2001
[
doi
]
A Constant Factor Approximation Algorithm for a Class of Classification Problems
STOC, 2000
[
pdf
doi
]
(with \'Eva Tardos)
Embeddings of Finite Metrics
Ph.D. Thesis, University of California, Berkeley, 2000
[
]
1999
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)
Embedding tree metrics into low dimensional Euclidean spaces
STOC, 1999
[
pdf
doi
]
Discrete Comput. Geom., 24(1):2000
[
doi
]
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: 2013-04-21.