Chaitanya Swamy

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 (selected)

Associate editor: Discrete Optimization, SIAM Journal on Computing (2011-21).
Organizer and chair: CanaDAM 2021 invited minisymposium on "Approximation algorithms".
Organizer and chair: ISMP 2018 session on "Approximation algorithms for clustering" (Discrete optimization and integer programming cluster).
Co-organizer: IPCO 2017, Waterloo.
Co-organizer: Workshop on Flexible Network Design 2013, Fields Institute, Toronto.
Committee member (selected): STOC 2023, APPROX 2022 (Chair), ESA 2021, WAOA 2021, SODA 2021, APPROX 2020, ICALP 2019, FOCS 2017, EC 2017, IPCO 2014, SODA 2014.

Teaching

CO 450/650: Combinatorial Optimization, Fall 2022, Fall 2019.
CO 255: Introduction to Optimization (Advanced), Winter 2019.
CO 454: Scheduling, Spring 2018, Spring 2017, Spring 2016, Spring 2013, Spring 2012.
CO 250: Introduction to Optimization, Spring 2018, Spring 2017, Winter 2016.
CO 759: Algorithmic Game Theory, Spring 2021, Spring 2015, Fall 2010, Spring 2008.
CO 602/CM 740/CS 795: Fundamentals of Optimization, Fall 2021.
CO 372: Portfolio Optimization, Winter 2022.
CO 353: Computational Discrete Optimization, Winter 2022, Winter 2021, Winter 2019, Winter 2015, Winter 2011.
CO 327: Deterministic OR Models (Non-Spec), Winter 2015, Spring 2012, Spring 2011.
CO 351: Network Flows, Fall 2014, Spring 2009.
CO 759: Approximation and Randomized Algorithms, Spring 2013.
CO 350: Linear Optimization, Fall 2006.
CO 370: Deterministic OR Models, Winter 2016, Winter 2013, Fall 2012, Fall 2011, Fall 2010, Winter 2009, Fall 2007, Winter 2007.
CO 453: Network Design, Winter 2007.
CO 456: Game Theory, Fall 2011.
CO 452/652: Integer Programming. Winter 2009.

Students and Postdoctoral fellows

Current students

David Aleman Espinosa, Ph.D, started Fall 2020.
Jason Canon, Master's, started Fall 2021.

Past students

Sharat Ibrahimpur, Ph.D, 2016-2022, thesis: "Stochastic Minimum-Norm Combinatorial Optimization" → Postdoc at London School of Economics (LSE).
Andre Linhares, Ph.D, 2013-2019, thesis: "Approximation Algorithms for Distributionally Robust Stochastic Optimization" → Google, Zurich.
Received the University of Waterloo Alumni Gold Medal, Ph.D awarded to the best student across the university for their academic achievements.
Sara Ahmadian, Ph.D, 2012-2017, thesis: "Approximation Algorithms for Clustering and Facility Location Problems" → Google, New York.
Received the Outstanding Achievement for Graduate Studies (Ph.D) award from the Faculty of Mathematics, University of Waterloo for the best student in the faculty in terms of academic achievements.
Hadi Minooei, Ph.D, 2008-2013, thesis: "Mechanism Design for Covering Problems" → Snapchat, California.
Haripriya Pulyassary, Master's, Spring 2021 - Spring 2022, thesis: "Algorithm Design for Original Settings" → Ph.D student at Cornell University.
Alexander Stoll, Master's, Fall 2017 - Winter 2021, thesis: "Tolls for Atomic Congestion Games" → MITRE Corporation, USA.
Ishan Bansal (with Jochen Koenemann), Master's, Winter 2019 - Spring 2020, thesis: "Capacitated Network Design on Outer Planar Graphs" → Ph.D student at Cornell University.
Named a University Finalist for the Alumni Gold Medal, Master’s, awarded to five outstanding students across the university.
Sanchit Kalhan, Master's, Fall 2016 - Winter 2018, thesis: "The Capacitated Matroid Median Problem" → Ph.D student at Northwestern University.
Sharat Ibrahimpur, Master's, Fall 2015 - Spring 2016, thesis: "Packing and Covering Odd (u,v) Trails" → C&O Ph.D student at U. Waterloo.
Alexander Lange, Master's, Fall 2013 - Winter 2015, thesis: "Approximation Algorithms for Graph Protection Problems" → Square, California.
Shubham Gupta, Master's, Fall 2009 - Spring 2011, thesis: "Building Networks in Uncertainty" → Snapchat, California.
Sara Ahmadian, Master's, Fall 2008 - Spring 2010, thesis: "Approximation Guarantees for Lower-Bounded Facility Location."
Aaron Dos Remedios, Master's, Fall 2008 - Fall 2009, thesis: "Approximation Algorithms for Multi-unit Online Auctions" → Canadian Tire, Canada.
Undergraduate Research Assistants (URAs): Felix Zhou (Spring 2021 → Ph.D, Yale), Ruilin Xiao (Spring 2020 → Citi), Ting Han Hu (Spring 2016), Tyler Johnson (Spring 2011), Ming Ben Feng (Spring 2009 → Ph.D, Northwestern → Faculty, Statistics & Actuarial Science @ UW), Aaron Dos Remedios (Spring 2008), Shane Cernele (Winter 2007 → Ph.D, UBC), Maurice Cheung (Spring 2007 → Ph.D, Cornell → Disney).

Past postdocs

Martin Gross, 2016-2017, (with Jochen Koenemann and Laura Sanita),
Umang Bhaskar, 2014-2015 → TIFR, India.
Andreas Feldmann, 2012-2014 (with Jochen Koenemann and Laura Sanita) → Charles University, Czech Republic.
Ian Post, 2012-2014 (with Jochen Koenemann) → Google, Mountain View.
Zachary Friggstad, 2011-2013 (with Jochen Koenemann) → University of Alberta, Canada.
Costis Georgiou, 2010-2012 (with Jochen Koenemann) → Ryerson University, Canada.
Deeparnab Chakrabarty, 2008-2010 (with Jochen Koenemann) → Dartmouth, USA.

Recent Publications

Combinatorial Algorithms for Rooted Prize-Collecting Walks and Applications to Orienteering and Minimum-Latency Problems. IPCO 2022.
A Simple Approximation Algorithm for Vector Scheduling and Applications to Stochastic Min-Norm Load Balancing. SOSA 2022.
Minimum-Norm Load Balancing Is (Almost) as Easy as Minimizing Makespan. ICALP 2021.
Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-polynomial Time. ICALP 2021.
Approximation Algorithms for Stochastic Minimum Norm Combinatorial Optimization. FOCS 2020.
A Constant-Factor Approximation for Directed Latency in Quasi-polynomial Time. JCSS 2022 (full version of ESA 2020 paper).
Simpler and Better Algorithms for Minimum-Norm Load Balancing. ESA 2019.
Approximation Algorithms for Distributionally Robust Stochastic Optimization with Black-Box Distributions. STOC 2019.
Approximation Algorithms for Minimum Norm and Ordered Optimization Problems. STOC 2019.
Approximate Multi-Matroid Intersection via Iterative Refinement. IPCO 2019.
Algorithms for Inverse Optimization Problems. ESA 2018.
Minimizing Latency in Online Ride and Delivery Services. WWW 2018.
Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median. ICALP 2018.

Publications (in reverse chronological order)

Sampling Bounds and Algorithms for Distributionally Robust Stochastic Optimization with Arbitrary Black-Box Distributions (with Andre Linhares).

Combinatorial Algorithms for Rooted Prize-Collecting Walks and Applications to Orienteering and Minimum-Latency Problems (with Sina Dezfuli, Zachary Friggstad, and Ian Post).
IPCO 2022.

A Simple Approximation Algorithm for Vector Scheduling and Applications to Stochastic Min-Norm Load Balancing (with Sharat Ibrahimpur).
SOSA 2022.

Minimum-Norm Load Balancing Is (Almost) as Easy as Minimizing Makespan (with Sharat Ibrahimpur).
ICALP 2021.

Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-polynomial Time (with Zachary Friggstad).
ICALP 2021.

Approximation Algorithms for Stochastic Minimum Norm Combinatorial Optimization (with Sharat Ibrahimpur).
FOCS 2020.

A Constant-Factor Approximation for Directed Latency in Quasi-polynomial Time (with Zachary Friggstad).
Journal of Computer and System Sciences 2022. Special issue devoted to selected papers from ESA 2020.

Simpler and Better Algorithms for Minimum-Norm Load Balancing (with Deeparnab Chakrabarty).
ESA 2019,

Approximation Algorithms for Distributionally Robust Stochastic Optimization with Black-Box Distributions (with Andre Linhares).
STOC 2019.

Approximation Algorithms for Minimum Norm and Ordered Optimization Problems (with Deeparnab Chakrabarty).
STOC 2019.

Approximate Multi-Matroid Intersection via Iterative Refinement (with Andre Linhares, Neil Olver, and Rico Zenklusen).
Mathematical Programming 2021. Special issue devoted to papers from IPCO 2019.

Algorithms for Inverse Optimization Problems (with Sara Ahmadian, Umang Bhaskar, and Laura Sanita).
ESA 2018.

Minimizing Latency in Online Ride and Delivery Services (with Abhimanyu Das, Sreenivas Gollapudi, Anthony Kim, and Debmalya Penigrahi).
WWW 2018.
Received the honorable mention research paper citation.

Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median (with Deeparnab Chakrabarty).
Proceedings of ICALP 2018, pages 29:1-29:14.
Detailed version posted on the CS arXiv, November 2017.
Detailed vresion ps, pdf or conference version pdf.

On the Integrality Gap of the Prize-Collecting Steiner Forest LP (with Jochen Koenemann, Neil Olver, Kanstantsin Pashkovich, R. Ravi, and Jens Vygen).
Proceedings of APPROX 2017, pages 17:1-17:13.
Detailed version posted on the CS arXiv, June 2017.
Detailed version pdf or conference version pdf.

Orienteering Algorithms for Generating Travel Itineraries (with Zachary Friggstad, Sreenivas Gollapudi, Kostas Kollias, Tamas Sarlos, and Andrew Tomkins).
To appear in Proceedings of the ACM International Conference on Web Search and Data Mining (WSDM) 2018. pdf.

Improved Algorithms for MST and Metric-TSP Interdiction (with Andre Linhares).
Proceedings of ICALP 2017, pages 32:1-32:14.
Detailed version posted on the CS arXiv, June 2017.
Detailed version ps, pdf or conference version pdf.
Slides: Short version (ppt).

Presented at Banff Workshop on Approximation Algorithms and Hardness of Approximation, November 2017 (video).

Compact, Provably-Good LPs for Orienteering and Regret-Bounded Vehicle Routing (with Zachary Friggstad).
Proceedings of IPCO 2017, pages 199-211.
Detailed version posted on the CS arXiv, August 2017.
Detailed version pdf or conference version pdf.
Slides: Short version (ppt).

Presented at Algorithms and Uncertainty Seminar, Simons Institute, UC Berkeley, December 2016; IPCO, July 2017; Simons Workshop on "Discrete Optimization via Continuous Relaxation", September 2017 (video);

Min-Max Theorems for Packing and Covering Odd (u, v)-Trails (with Sharat Ibrahimpur).
Proceedings of IPCO 2017, pages 279-291.
Detailed version posted on the CS arXiv, August 2017.
Detailed version pdf or conference version pdf.

Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games (with Umang Bhaskar, Yu Cheng and Young Kun Ko).
Proceedings of EC 2016, pages 479-496. ps or pdf.
Slides: Short version (ppt).

Presented at Tutte seminar at the University of Waterloo, January 2016; HIM Game Theory Workshop, Bonn, December 2016 (video).

Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers (with Sara Ahmadian).
Proceedings of ICALP 2016, pages 69:1-69:15.
Detailed version posted on the CS arXiv, August 2016.
Detailed version pdf or conference version pdf.

Approximating Min-Cost Chain-Constrained Spanning Trees: A Reduction from Weighted to Unweighted Problems (with Andre Linhares).
Mathematical Programming, 172(1-2):17-34, 2018.
Preliminary version in Proceedings of IPCO 2016, pages 38-49.
Journal version ps, pdf or conference version ps, pdf.
Slides: Long version (ppt).

Presented at 6th Cargese Workshop on Combinatorial Optimization, September 2015; INFORMS Annual Meeting (invited talk), November 2016; CMS Winter Meeting (invited talk), December 2016.

Learning Arbitrary Statistical Mixtures of Discrete Distributions (with Jian Li, Yuval Rabani and Leonard Schulman).
Proceedings of STOC 2015, pages 743-752.
Detailed version posted on the CS arXiv, Apr 2015.
Detailed version ps, pdf or conference version ps, pdf.

Linear-Programming based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems (with Ian Post).
Proceedings of SODA 2015, pages 512-531.
Detailed version posted on the CS arXiv, November 2014.
Detailed version ps, pdf or conference version ps, pdf.
Slides: Long version (ppt) or short version (ppt).

Presented at 7th Workshop on Flexible Network Design, Lugano, August 2014; Tutte seminar at the University of Waterloo, October 2014; SODA, January 2015.

Improved Region-Growing and Combinatorial Algorithms for k-Route Cut Problems (with Guru Guruganesh and Laura Sanita).
Proceedings of SODA 2015, pages 676-695.
Also posted on the CS arXiv, October 2014.
ArXiv version pdf, or conference version pdf.
Slides: Short version (ppt).

Presented at Banff Workshop on Approximation Algorithms and Hardness of Approximation, August 2014 (video); Bridging Discrete and Continuous Optimization Seminar, Simons Institute, UC Berkeley, October 2017.

Achieving Target Equilibria in Network Routing Games without Knowing the Latency Functions (with Umang Bhaskar, Katrina Ligett, and Leonard Schulman).
Invited to a special issue of Games and Economic Behavior devoted to selected papers from SODA, FOCS, STOC 2014.
Preliminary version in Proceedings of FOCS 2014, pages 31-40.
Detailed version pdf or conference version ps, pdf.

Approximation Algorithms for Minimum-Load k-Facility Location (with Sara Ahmadian, Babak Behsaz, Zachary Friggstad, Amin Jorati, and Mohammad Salavatipour).
Transactions on Algorithms, 14(2):article 16, 2018.
Preliminary version in Proceedings of APPROX 2014, pages 17-33.
Journal version pdf or conference version pdf.

Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications.
ACM Transactions on Algorithms, 12(4), article no. 49, 2016.
Preliminary version in Proceedings of APPROX 2014, pages 403-418.
Journal version ps, pdf, or conference version pdf.
Slides: Short version (ppt).

Presented at APPROX, August 2014.

Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications to Distance-Constrained Vehicle Routing (with Zachary Friggstad).
Proceedings of STOC 2014, pages 744-753.
Detailed version posted on the CS arXiv, November 2013.
Detailed version pdf or conference version ps or pdf.
Slides: Long version (ppt) or a (slightly) shorter version (ppt).

Presented at STOC, June 2014; ISMP (invited talk), July 2015; Google, Mountain View, December 2016.

Welfare Maximization and Truthfulness in Mechanism Design with Ordinal Preferences (with Deeparnab Chakrabarty).
Proceedings of ITCS 2014, pages 105-120.
Also posted on the CS arXiv, December 2013.
ArXiv version ps, pdf, or conference version ps, pdf.
Slides: Long version (ppt) or short version (ppt).

Presented at CORS-INFORMS International Meeting (invited talk), May 2014; Bellairs Workshop on Algorithmic Game Theory, April 2014; ITCS, January 2014.

Learning Mixtures of Arbitrary Distributions over Large Discrete Domains (with Yuval Rabani and Leonard Schulman).
Proceedings of ITCS 2014, pages 207-224.
Also posted on the CS arXiv, September 2012.
ArXiv version ps, pdf, or conference version ps, pdf.
Slides: Short version (ppt).

Presented at ITCS, January 2014.

Near-Optimal and Robust Mechanism Design for Covering Problems with Correlated Players (with Hadi Minooei).
ACM Transactions on Economics and Computation, 3(4), article no. 19, 2015. Special issue devoted to selected papers from WINE 2013.
Preliminary version in Proceedings of WINE 2013, pages 377-390.
Journal version ps or pdf.

Note: The journal version has some significant differences with the conference version. It better elucidates the differences between covering- and packing mechanism design, and corrects a few errors in the conference version; you are therefore encouraged to consult the journal version. The key differences between the conference and journal versions are: (a) The IC and IR notion we propose are denoted support-based (IC, IR) in the journal version instead of robust-(BIC, IR). (b) Additive types are defined more accurately in the journal version; these correspond to additive valuations for combinatorial auctions. (c) Approximation algorithms for the SWM problem are leveraged for revenue-maximization only for single-dimensional domains. (This proceeds in a simple and standard way and does not run into any of the difficulties encountered for covering problems.)

Local-Search based Approximation Algorithms for Mobile Facility Location Problems (with Sara Ahmadian and Zachary Friggstad).
Proceedings of SODA 2013, pages 1607-1621.
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 448-461.
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 hop-distance 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 minor-closed 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.

Black-Box Reductions for Cost-Sharing 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 896-913.
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 Lower-Bounded Facility Location (with Sara Ahmadian).
Proceedings of WAOA 2012, pages 257-271.
Detailed version posted on the CS arXiv, August 2012.
Detailed version ps, pdf or conference version ps, 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 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: Linear-Programming based Techniques for Minimum-Latency Problems (with Deeparnab Chakrabarty).
Mathematics of Operations Research, 41(3):865-883, 2016.
Preliminary version in Proceedings of IPCO 2011, pages 92-103.
Journal 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.

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.

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.

Approximability of the Firefighter Problem: Computing Cuts over Time (with Elliot Anshelevich, Deeparnab Chakrabarty and Ameya Hate).
Algorithmica, 62(1-2):520-536, 2012.
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.
ACM Transactions on Algorithms, 8(4):36, 2012.
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).
Journal of the ACM, 59(6):28, 2012.
Preliminary version appeared in Proceedings of FOCS 2006, pages 165-174.
Journal 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).
Journal of the ACM, 58(6):25, 2011.
Preliminary version appeared in Proceedings of FOCS 2005, pages 595-604.
Journal 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).
SIAM Journal on Computing, 41(4):975-1004, 2012.
Preliminary version appeared in Proceedings of FOCS 2005, pages 357-366.
Journal 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.

Note: On the last page, the paper incorrectly claims that the Goemans-Williamson primal-dual algorithm for PCST yields a 2-approximation algorithm for PCST with submodular penalties. In fact, this only yields a 3-approximation 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):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).
Mathematical Programming, 131(1-2):365-379, 2012.
Preliminary version appeared in Proceedings of IPCO 2004, pages 206-218.
Journal 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, 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.

Created September 2006.
Updated August 2022.