Hi.
I joined the Department of
Combinatorics and Optimization at the University of
Waterloo as an assistant professor in September 2006.
Previously I was a postdoctoral scholar at the
Center for the Mathematics of Information (CMI)
at Caltech.
I graduated from the Department of Computer Science
at Cornell University in May 2004.
My advisor was David Shmoys.
For research, I mostly think about algorithms. My research interests include
combinatorial optimization, approximation algorithms, algorithmic game theory,
stochastic optimization, network design, scheduling, and online algorithms.
Approximation Algorithms for MultiVehicle Minimum
Latency Problems via LinearProgramming based Techniques
(with Ian Post).

RegionGrowing and Combinatorial Algorithms
for kRoute Cut Problems (with Guru Guruganesh and
Laura Sanita).

Achieving Target Equilibria in
Network Routing Games without Knowing the Latency Functions
(with Umang Bhaskar,
Katrina Ligett,
and Leonard Schulman). To appear in Proceedings of FOCS 2014. Detailed version posted on the CS arXiv, August 2014. Detailed version ps, pdf or conference version ps, pdf. 
Approximation
Algorithms for MinimumLoad kFacility Location (with Sara
Ahmadian, Babak
Behsaz, Zachary Friggstad,
Amin Jorati,
and Mohammad Salavatipour). To appear in Proceedings of APPROX 2014. pdf. 
Improved Approximation
Algorithms for Matroid and Knapsack Median Problems and Applications. To appear in Proceedings of APPROX 2014. Detailed version posted on the CS arXiv, November 2013. Detailed version ps, pdf, or conference version pdf. 
Approximation Algorithms for
RegretBounded Vehicle Routing and Applications to DistanceConstrained Vehicle
Routing (with Zachary
Friggstad). Proceedings of STOC 2014, pages 744753. Detailed version posted on the CS arXiv, November 2013. Detailed version pdf or conference version ps or pdf. 
Welfare Maximization and
Truthfulness in Mechanism Design with Ordinal Preferences
(with Deeparnab
Chakrabarty). Proceedings of ITCS 2014, pages 105120. Also posted on the CS arXiv, December 2012. ArXiv version ps, pdf, or conference version ps, pdf. 
Learning Mixtures of
Arbitrary Distributions over Large Discrete Domains
(with Yuval Rabani
and Leonard Schulman). Proceedings of ITCS 2014, pages 207224. Also posted on the CS arXiv, December 2012. ArXiv version ps, pdf, or conference version ps, pdf. 
NearOptimal and Robust
Mechanism Design for Covering Problems with Correlated Players (with Hadi
Minooei). Proceedings of WINE 2013, pages 377390. Detailed version posted on the CS arXiv, November 2013. Detailed version ps, pdf or conference version ps, pdf. 
LocalSearch based
Approximation Algorithms for Mobile Facility Location Problems (with
Sara Ahmadian and Zachary
Friggstad). Proceedings of SODA 2013, pages 16071621. Detailed version posted on the CS arXiv, January 2013. Detailed version ps, pdf or conference version ps, pdf. Note: A subtle error in the definition of cand(i) and some typos in the conference publication have been corrected in the versions posted above. 
Truthful Mechanism Design
for Multidimensional Covering Problems (with Hadi Minooei). Proceedings of WINE 2012, pages 448461. Detailed version posted on the CS arXiv, November 2012. Detailed version pdf or conference version ps, pdf. Note: Theorem 13 in the conference publication is incorrect. The claimed guarantee holds if we assume that any two nodes owned by the same player are at least hopdistance 3 away from each other. The correct guarantee in general is: O(γ r log n)approximation for an everywhere γsparse graph, which leads to an O(r log n)approximation for any proper minorclosed family of graphs. This has been corrected in the versions posted above (and on the arXiv). The corrected statement appears as Theorem 4.10 in the detailed version, and Theorem 15 in the conference version. 
BlackBox
Reductions for CostSharing Mechanism Design
(with Konstantinos Georgiou). To appear in Games and Economic Behavior. Special issue devoted selected papers from SODA, FOCS, STOC 2012. Preliminary version in Proceedings of SODA 2012, pages 896913. Journal version ps, pdf or conference version ps, pdf. Slides: Long version (ppt). Presented at SODA, January 2012; Bellairs Workshop on Algorithmic Game Theory, April 2012; Dept. of Computing and Software Seminar at McMaster University, September 2012; IST Lunch Bunch Seminar, Caltech, October 2012. 
Improved Approximation Guarantees for LowerBounded
Facility Location (with Sara Ahmadian). Proceedings of WAOA 2012, pages 257271. Detailed version posted on the CS arXiv, August 2012. Detailed version ps, pdf or conference version ps, pdf. 
RiskAverse Stochastic Optimization:
ProbabilisticallyConstrained Models and Algorithms for BlackBox Distributions. Proceedings of SODA 2011, pages 16271646. ps or pdf. An older version appeared as "Algorithms for ProbabilisticallyConstrained Models of RiskAverse Stochastic Optimization with BlackBox Distributions" on the CS arXiv; a newer detailed version will be posted soon. Slides: Long version (ppt) or a (slightly) shorter version (ppt). Presented at 3rd Workshop on Flexible Network Design, July 2008; Theory seminar at Cornell University, September 2008; Dagstuhl Workshop on Algorithm Engineering, June 2010; SODA, January 2011; ISMP (invited talk), August 2012. 
Facility Location with Client
Latencies: LinearProgramming based Techniques for MinimumLatency Problems
(with Deeparnab Chakrabarty). Proceedings of IPCO 2011, pages 92103. Detailed version posted on the CS arXiv, September 2010. Detailed version ps, pdf or conference version ps, pdf. Slides: Long version (ppt) or short version (ppt). Presented at IPCO, June 2011; Tutte seminar at the University of Waterloo, July 2011; Banff Workshop on Approximation Algorithms and Hardness of Approximation, November 2011; 5th Workshop on Flexible Network Design, Warsaw, July 2012; Theory seminar at RWTH Aachen University, August 2012. 
FaultTolerant Facility Location: A
Randomized Dependent LProunding Algorithm
(with Jaroslaw Byrka
and Aravind Srinivasan). Proceedings of IPCO 2010, pages 244257. Detailed version ps, pdf or conference version ps, pdf. 
Approximation Algorithms for
NonSingleminded ProfitMaximization Problems with Limited Supply
(with Khaled Elbassioni
and Mahmoud Fouz). Proceedings of WINE 2010, pages 462472. ps or pdf. 
Approximability of the
Firefighter Problem: Computing Cuts over Time
(with Elliot Anshelevich,
Deeparnab Chakrabarty and Ameya Hate). Algorithmica, 62(12):520536, 2012. Preliminary version appeared as "Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity" in Proceedings of ISAAC 2009, pages 974983. Journal version ps, pdf or conference version ps, pdf. 
Approximation Algorithms for
Singleminded Envyfree Profitmaximization Problems with Limited Supply
(with Maurice Cheung). Proceedings of FOCS 2008, pages 3544. ps or pdf. Slides: Long version (ppt). Presented at the Caltech CMI 5th Anniversary Workshop (invited talk), November 2009; CORSINFORMS International Meeting (invited talk), June 2009; Theory seminar at SUNY Buffalo, August 2009; Eastern Great Lakes Theory Workshop, September 2008; Tutte seminar at the University of Waterloo, September 2008. 
Approximation Algorithms for Labeling
Hierarchical Taxonomies
(with Yuval Rabani
and Leonard Schulman). Proceedings of SODA 2008, pages 671680. ps or pdf. 
Truthful Mechanism Design for
Multidimensional Scheduling via Cycle Monotonicity
(with Ron Lavi). Games and Economic Behavior, 67(1):99124, 2009. Special issue devoted to selected papers from EC 2007. Preliminary version in Proceedings of EC 2007, pages 252261. Journal version ps, pdf or conference version ps, pdf. 
The Effectiveness of Stackelberg
Strategies and Tolls for Network Congestion Games. ACM Transactions on Algorithms, 8(4):36, 2012. Preliminary version appeared in Proceedings of SODA 2007, pages 11331142. Journal version ps, pdf or conference version ps, pdf. Slides: Short version (ppt). Presented at SODA, January 2007. 
Approximation Algorithms for
Prize Collecting Steiner Forest Problems with Submodular Penalty Functions
(with Yogeshwer Sharma
and David Williamson). Proceedings of SODA 2007, pages 12751284. ps or pdf. Slides: Long version (ppt). Presented at the Combinatorial Optimization Seminar at the University of Waterloo, February 2007. 
The Effectiveness of LloydType Methods
for the kMeans Problem
(with Rafail Ostrovsky,
Yuval Rabani and
Leonard Schulman). Journal of the ACM, 59(6):28, 2012. Preliminary version appeared in Proceedings of FOCS 2006, pages 165174. Detailed version ps, pdf or conference version ps, pdf. Slides: Long version (ppt) or short version (ppt). Presented at FOCS, October 2006; Algorithms and Complexity Seminar at University of Waterloo, November 2006. 
Approximation Algorithms for Graph Homomorphism Problems
(with Michael Langberg and
Yuval Rabani). Proceedings of APPROX 2006, pages 176187. ps or pdf. Slides: Long version (ppt). Presented at the Combinatorial Optimization Seminar at the University of Waterloo, November 2006. 
Approximation Algorithms for 2Stage Stochastic
Optimization Problems
(with David Shmoys). Survey article in ACM SIGACT News, 37(1):3346, March 2006. ps or pdf. See also a (slightly) shorter survey that appeared in Proceedings of FSTTCS 2006,pages 519. ps or pdf. Slides (ppt) from a survey talk given at the Aladdin Workshop on Flexible Network Design , November 2005. 
Truthful and Nearoptimal
Mechanism Design via Linear Programming
(with Ron Lavi). Journal of the ACM, 58(6):25, 2011. Preliminary version appeared in Proceedings of FOCS 2005, pages 595604. Detailed version ps, pdf or conference version ps, pdf. Slides: Long version (ppt) or a (slightly) shorter version (ppt). Presented at FOCS, October 2005; Theory seminars at Caltech, November 2005 and IBM Yorktown Heights, December 2005; Tutte seminar at the University of Waterloo, November 2006; INFORMS Annual Meeting (invited talk), November 2007. 
Samplingbased Approximation
Algorithms for Multistage Stochastic Optimization
(with David Shmoys). SIAM Journal on Computing, 41(4):9751004, 2012. Preliminary version appeared in Proceedings of FOCS 2005, pages 357366. Detailed version ps, pdf or conference version ps, pdf. Note: There was a subtle error in the definition of the grid in the conference version, which has been corrected in the detailed version posted above. This error has also been corrected in the unpublished manuscript below on "The Sample Average Approximation Method for 2stage Stochastic Optimization". Slides: Long version (ppt) or a (slightly) shorter version (ppt). Presented at FOCS, October 2005; Oberwolfach Workshop on Combinatorial Optimization, November 2005; Dagstuhl Workshop on Probabilistic Methods in the Design and Analysis of Algorithms, October 2007. 
The Sample Average Approximation Method for 2stage Stochastic
Optimization
(with David Shmoys). Unpublished manuscript, 2004. ps or pdf. 
Network Design for Information Networks
(with Ara Hayrapetyan and
Éva Tardos). Proceedings of SODA 2005, pages 933942. ps or pdf. Note: On the last page, the paper incorrectly claims that the GoemansWilliamson primaldual algorithm for PCST yields a 2approximation algorithm for PCST with submodular penalties. In fact, this only yields a 3approximation algorithm. (A slightly better guarantee can be obtained via LP rounding; see the paper with Yogeshwer Sharma and David Williamson above.) Slides: Short version (ppt). Presented at the Bertinoro Workshop on Models and Algorithms for Information Networks (MAIN), October 2004; INFORMS Annual Meeting (invited talk), November 2005. 
An Approximation Scheme for Stochastic Linear
Programming and its Application to Stochastic Integer Programs
(with David Shmoys). Journal of the ACM, 53(6):9781012, 2006. Preliminary version appeared as "Stochastic Optimization is (almost) as Easy as Deterministic Optimization" in Proceedings of FOCS 2004, pages 228237. (Invitation to special issue of SIAM Journal on Computing declined.) Journal version ps, pdf or conference version ps, pdf. See also my PhD thesis. Slides: Long version (ppt) or short version (ppt). Presented at Cornell University; CMI Fall 2004 Retreat; 10th International Conference on Stochastic Programming (SPX), 2004; FOCS 2004; Dagstuhl Seminar on Algorithms for Optimization with Incomplete Information, 2005; Theory and IEOR seminars at the University of Rome "La Sapienza", MIT, Brown University, IBM Yorktown Heights, Columbia University. 
Optimal Powerdown Strategies
(with John Augustine and
Sandy Irani). SIAM Journal on Computing, 37(5):14991516, 2008. Preliminary version appeared in Proceedings of FOCS 2004, pages 530539. Journal version ps, pdf or conference version ps, pdf. Slides: Short version (ppt). Presented at FOCS, Rome, October 2004. 
Approximation Algorithms for
Data Placement Problems
(with Ivan Baev and
Rajmohan Rajaraman). SIAM Journal on Computing, 38(4):14111429, 2008. Merger of two papers: "Approximation Algorithms for Data Placement in Arbitrary Networks", SODA 2001, and an unpublished manuscript, "Algorithms for Data Placement Problems", 2004. Journal version ps or pdf. 
LPbased Approximation Algorithms for
Capacitated Facility Location
(with Retsef Levi and
David Shmoys). Mathematical Programming, 131(12):365379, 2012. Preliminary version appeared in Proceedings of IPCO 2004, pages 206218. Detailed version ps, pdf or conference version ps, pdf. Slides: Short version (ppt). Presented at IPCO, New York, June 2004. 
Correlation Clustering: Maximizing Agreements via
Semidefinite Programming. Proceedings of SODA 2004, pages 519520. ps or pdf. Won the Best Student Paper Award. Slides: Short version (ppt). Presented at the Theory Seminar at Cornell, November 2003 and at SODA, New Orleans, January 2004. 
Facility Location with Service Installation Costs
(with David Shmoys and
Retsef Levi). Proceedings of SODA 2004, pages 10811090. ps or pdf. Slides: Short version (ppt). Presented at SODA, New Orleans, January 2004. 
FaultTolerant Facility Location
(with David Shmoys). ACM Transactions on Algorithms, 4(4), article no. 51, August 2008. Preliminary version appeared in Proceedings of SODA 2003, pages 735736. Journal version ps, pdf or conference version ps, pdf. Slides: Long version (ppt) or short version (ppt). Presented at the Theory Seminar at Cornell, April 2002 and at SODA, Baltimore, January 2003. 
PrimalDual Algorithms for Connected Facility Location
Problems
(with Amit Kumar). Algorithmica, 40(4):245269, 2004. Special issue devoted to selected papers from APPROX 2002. Preliminary version in Proceedings of APPROX 2002, pages 256269. Journal version ps, pdf or conference version ps, pdf. Slides: Long version (ppt) or a (slightly) shorter version (ppt). Presented at the Algorithms Seminar at the MaxPlanckInstitut für Informatik, Saarbrücken, August 2002; APPROX, Rome, September 2002; Theory Seminar at Cornell, October 2002; Integrated Logistics Workshop (an ALADDIN PROBE) at Princeton, October 2002. 
A Randomized Algorithm for Flow Shop Scheduling
(with Naveen Garg and
Sachin Jain). Proceedings of FSTTCS 1999, pages 213218. ps or pdf. 
Approximation Algorithms for
Clustering Problems. PhD Thesis, Dept. of Computer Science, Cornell University, May 2004. ps or pdf. Note: There was a small error in Lemma 2.4.1 in the earlier version. As a result, one has to use a slightly different clusterselection rule in the demandoblivious primalrounding algorithm, and the approximation factor increases to 1.858. This correspondingly affects the approximation ratios of the algorithms for 2stage stochastic UFL (Chapter 4), and 2stage stochastic FLSIC (Section 5.6). The version posted here is the corrected version. 
Improving the Quality vs. Time Ratio of GraphCut Based Algorithms for Visual
Correspondence. Unpublished manuscript, 2002. 
Scheduling Algorithms. Undergraduate (B. Tech.) Thesis, Dept. of Computer Science, Indian Institute of Technology, Delhi, May 1999. 