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.

Professional Activities

• Committee member: APPROX 2011, SWAT 2010, COCOON 2010, COCOON 2009, APPROX 2007.

Teaching

• CO 327: Deterministic OR Models (Non-Spec), Spring 2011.
• CO 350: Linear Optimization, Fall 2006.
• CO 351: Network Flows, Spring 2009.
• CO 353: Computational Discrete Optimization, Winter 2011.
• CO 370: Deterministic OR Models, Fall 2011, Fall 2010, Winter 2009, Fall 2007, Winter 2007.
• CO 453: Network Design, Winter 2007.
• CO 456: Game Theory, Fall 2011.
• CO 759: Algorithmic Game Theory, Fall 2010, Spring 2008.
• CO 452/652: Integer Programming. Winter 2009.

Recent Publications

• Improved Approximation Guarantees for Lower-Bounded Facility Location. CS arXiv, April 2011.
• Facility Location with Client Latencies: Linear-Programming based Techniques for Minimum-Latency Problems. IPCO 2011.
• Risk-Averse Stochastic Optimization: Probabilistically-Constrained Models and Algorithms for Black-Box Distributions. SODA 2011.
• The Effectiveness of Lloyd-Type Methods for the k-Means Problem. Accepted to JACM (full version of FOCS 2006 paper.)
• Truthful and Near-optimal Mechanism Design via Linear Programming. Accepted to JACM (full version of FOCS 2005 paper.)
• Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization. Accepted to SICOMP (full version of FOCS 2005 paper.)
• The Effectiveness of Stackelberg Strategies and Tolls for Network Congestion Games. Accepted to TALG (full version of SODA 2007 paper).
• LP-based Approximation Algorithms for Capacitated Facility Location. Math. Programming (full version of IPCO 2004 paper).
• Approximability of the Firefighter Problem: Computing Cuts over Time. Algorithmica (full version of ISAAC 2009 paper).
• Approximation Algorithms for Non-Single-minded Profit-Maximization Problems with Limited Supply. WINE 2010.
• Fault-Tolerant Facility Location: A Randomized Dependent LP-Rounding Algorithm. IPCO 2010.

Publications (in reverse chronological order)

• Inference from Sparse Sampling (with Yuval Rabani and Leonard Schulman).
  
  
• Improved Approximation Guarantees for Lower-Bounded Facility Location (with Sara Ahmadian).
  CS arXiv, April 2011. ps or pdf.
  
  
• Approximation Algorithms for Non-Single-minded Profit-Maximization Problems with Limited Supply (with Khaled Elbassioni and Mahmoud Fouz).
  Proceedings of WINE 2010, pages 462-472. ps or pdf.
  
  
• Risk-Averse Stochastic Optimization: Probabilistically-Constrained Models and Algorithms for Black-Box Distributions.
  Proceedings of SODA 2011, pages 1627-1646. ps or pdf.
  An older version appeared as "Algorithms for Probabilistically-Constrained Models of Risk-Averse Stochastic Optimization with Black-Box 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 SODA, January 2011; Dagstuhl Workshop on Algorithm Engineering, June 2010; 3rd Workshop on Flexible Network Design, July 2008; Theory seminar at Cornell University, September 2008.
  
  
• Facility Location with Client Latencies: Linear-Programming based Techniques for Minimum-Latency Problems (with Deeparnab Chakrabarty).
  To appear in Proceedings of IPCO 2011.
  Detailed version posted on the CS arXiv, September 2010.
  Detailed version ps, pdf or conference version ps, pdf
  
  
• Fault-Tolerant Facility Location: A Randomized Dependent LP-rounding Algorithm (with Jaroslaw Byrka and Aravind Srinivasan).
  Proceedings of IPCO 2010, pages 244-257.
  Detailed version ps, pdf or conference version ps, pdf.
  
  
• Approximability of the Firefighter Problem: Computing Cuts over Time (with Elliot Anshelevich, Deeparnab Chakrabarty and Ameya Hate).
  To appear in Algorithmica.
  Preliminary version appeared as "Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity" in Proceedings of ISAAC 2009, pages 974-983.
  Journal version ps, pdf or conference version ps, pdf.
  
  
• Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply (with Maurice Cheung).
  Proceedings of FOCS 2008, pages 35-44. ps or pdf.
  Slides: Long version (ppt).
  
  Presented at the Caltech CMI 5th Anniversary Workshop (invited talk), November 2009; CORS-INFORMS 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 671-680. ps or pdf.
  
  
• Truthful Mechanism Design for Multidimensional Scheduling via Cycle Monotonicity (with Ron Lavi).
  Games and Economic Behavior, 67(1):99-124, 2009. Special issue devoted to selected papers from EC 2007.
  Preliminary version in Proceedings of EC 2007, pages 252-261.
  Journal version ps, pdf or conference version ps, pdf.
  
  
• The Effectiveness of Stackelberg Strategies and Tolls for Network Congestion Games.
  To appear in ACM Transactions on Algorithms.
  Preliminary version appeared in Proceedings of SODA 2007, pages 1133-1142.
  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 1275-1284. ps or pdf.
  Slides: Long version (ppt).
  
  Presented at the Combinatorial Optimization Seminar at the University of Waterloo, February 2007.
  
  
• The Effectiveness of Lloyd-Type Methods for the k-Means Problem (with Rafail Ostrovsky, Yuval Rabani and Leonard Schulman).
  Accepted to Journal of the ACM (with revisions).
  Preliminary version appeared in Proceedings of FOCS 2006, pages 165-174.
  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 176-187. ps or pdf.
  Slides: Long version (ppt).
  
  Presented at the Combinatorial Optimization Seminar at the University of Waterloo, November 2006.
  
  
• Approximation Algorithms for 2-Stage Stochastic Optimization Problems (with David Shmoys).
  Survey article in ACM SIGACT News, 37(1):33-46, March 2006. ps or pdf.
  See also a (slightly) shorter survey that appeared in Proceedings of FSTTCS 2006, pages 5-19. ps or pdf.
  Slides (ppt) from a survey talk given at the Aladdin Workshop on Flexible Network Design, November 2005.
  
  
• Truthful and Near-optimal Mechanism Design via Linear Programming (with Ron Lavi).
  Accepted to Journal of the ACM (with revisions).
  Preliminary version appeared in Proceedings of FOCS 2005, pages 595-604.
  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.
  
  
• Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization (with David Shmoys).
  Accepted to SIAM Journal on Computing (with revisions).
  Preliminary version appeared in Proceedings of FOCS 2005, pages 357-366.
  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 2-stage 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 2-stage 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 933-942. ps or pdf.
  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):978-1012, 2006.
  Preliminary version appeared as "Stochastic Optimization is (almost) as Easy as Deterministic Optimization"
  in Proceedings of FOCS 2004, pages 228-237. (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 Power-down Strategies (with John Augustine and Sandy Irani).
  SIAM Journal on Computing, 37(5):1499-1516, 2008.
  Preliminary version appeared in Proceedings of FOCS 2004, pages 530-539.
  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):1411-1429, 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.
  
  
• LP-based Approximation Algorithms for Capacitated Facility Location (with Retsef Levi and David Shmoys).
  To appear in Mathematical Programming.
  Preliminary version appeared in Proceedings of IPCO 2004, pages 206-218.
  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 519-520. 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 1081-1090. ps or pdf.
  Slides: Short version (ppt).
  
  Presented at SODA, New Orleans, January 2004.
  
  
• Fault-Tolerant 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 735-736.
  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.
  
  
• Primal-Dual Algorithms for Connected Facility Location Problems (with Amit Kumar).
  Algorithmica, 40(4):245-269, 2004. Special issue devoted to selected papers from APPROX 2002.
  Preliminary version in Proceedings of APPROX 2002, pages 256-269.
  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 Max-Planck-Institut 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 213-218. 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 cluster-selection rule in the demand-oblivious primal-rounding algorithm, and the approximation factor increases to 1.858. This correspondingly affects the approximation ratios of the algorithms for 2-stage stochastic UFL (Chapter 4), and 2-stage stochastic FLSIC (Section 5.6). The version posted here is the corrected version.
  
  
• Improving the Quality vs. Time Ratio of Graph-Cut 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.