# Publications

## 2019

Network Flow Algorithms
To be published by Cambridge University Press, Fall 2019.

Tight Bounds for Online Weighted Tree Augmentation
In Christel Baier, Ioannis Chatzigiannakis, Paola Flochinni, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) , 88:1-88:14, 2019.

Rank Aggregation: New Bounds for MCx
Discrete Applied Mathematics 262:28-36, 2019.

## 2017

Greedy Algorithms for the Single-Demand Facility Location Problem
Operations Research Letters 45:452-455, 2017.

Prize-Collecting TSP with a Budget Constraint
In Kirk Pruhs and Christian Soler, editors, Leibnitz International Proceedings in Informatics Number 87, 25th Annual European Symposium on Algorithms (ESA 2017), pages 62:1-62:14, 2017.

## 2016

An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
In Andrew V. Goldberg and Alexander S. Kulikov, editors, Lecture Notes in Computer Science Number 9685, Experimental Algorithms, 15th International Symposium, SEA 2016 pages 246-261, 2016

Simple Approximation Algorithms for Balanced MAX 2SAT
In Evangelos Kranakis, Gonzalo Navarro, and Edgar Chávez, editors, Lecture Notes in Computer Science Number 9644, LATIN 2016: Theoretical Informatics, pages 659-671, 2016.

## 2015

Assortment optimization over time.
Operations Research Letters 43:608-611, 2015

An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem
In Nikhil Bansal and Irene Finocchi, editors, Lecture Notes in Computer Science Number 9294, Algorithms – ESA 2015, pages 570-581, 2015.

On the Integrality Gap of the Subtour LP for the 1,2-TSP
Mathematical Programming 150:131-151, 2015.

The Online Prize-Collecting Facility Location Problem
Electronic Notes in Discrete Mathematics 50:151–156, 2015

## 2014

The Online Connected Facility Location Problem
In Alberto Pardo and Alfredo Viola, editors, Lecture Notes in Computer Science Number 8392, LATIN 2014: Theoretical Informatics , pages 574-585, 2014.

On Some Recent Approximation Algorithms for MAX SAT
In Alberto Pardo and Alfredo Viola, editors, Lecture Notes in Computer Science Number 8392, LATIN 2014: Theoretical Informatics , pages 589-609, 2014.

Popular ranking
Discrete Applied Mathematics 165:312-316, 2014.

## 2013

An Experimental Evaluation of Incremental and Hierarchical $k$-Median Algorithms
Journal of Experimental Algorithmics 18, Article 3.2. Special issue for the 2011 Symposium on Experimental Algorithms.

Maximizing a Submodular Function with Viability Constraints
In Hans L. Bodlaender and Giuseppe F. Italiano, editors, Lecture Notes in Computer Science , vol. 8125, Algorithms – ESA 2013 , pages 409-420, 2013.

Offline and Online Facility Leasing
Discrete Optimization 10:361–370, 2013.

## 2012

A dual-fitting 3/2-approximation algorithm for some minimum-cost graph problems
In Leah Epstein and Paolo Ferragina, editors, Lecture Notes in Computer Science, vol. 7501, Algorithms – ESA 2012 , pages 373–382, 2012.

On the integrality gap of the Subtour LP for the 1,2-TSP
In David Fernández-Baca, editor, Lecture Notes in Computer Science, vol. 7256, LATIN 2012: Theoretical Informatics, pages 606-617, 2012.

A proof of the Boyd-Carr conjecture
Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1477-1486, 2012.

## 2011

A note on the generalized min-sum set cover problem
Operations Research Letters 39:433-436, 2011.

An O(log n)-competitive algorithm for online constrained forest problems
In Luca Aceto, Monika Henzinger, and Jiří Sgall, editors, Lecture Notes in Computer Science, vol. 6755, Automata, Languages, and Programming, pages 37-48, 2011.

Popular ranking
In the Proceedings of the 10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2011).

An experimental evaluation of incremental and hierarchical $k$-median algorithms
In Panos M. Pardalos and Steffen Rebennack, editors, Lecture Notes in Computer Science, vol. 6630, Experimental Algorithms, pages 169–180, 2011.

The Design of Approximation Algorithms
Cambridge University Press, New York, NY, USA, 2011.

## 2009

Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems.
Mathematics of Operations Research 34:594-620, 2009.

## 2008

Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements.
In E. Bampis and M. Skutella, editors, Lecture Notes in Computer Science, vol. 5426, Approximation and Online Algorithms, pages 174-187, 2008.

Offline and Online Facility Leasing.
In A. Lodi, A. Paconesi, and G. Rinaldi, editors, Lecture Notes in Computer Science, vol. 5035, Integer Programming and Combinatorial Optimization, pages 303-315, 2008.

## 2007

Lecture Notes on Network Flow, Spring 2004.
Cornell School of Operations Research and Information Engineering Technical Report 1460.

Approximation algorithms for prize collecting forest problems with submodular penalty functions.
Proceedings of the 18th annual ACM-SIAM Symposium on Discrete Algorithms, pages 1275-1284, 2007.

## 2006

An adaptive algorithm for selecting profitable keywords for search-based advertising services.
Proceedings of the 7th ACM Conference on Electronic Commerce, pages 260-269, 2006.

## 2005

Improved approximation algorithms for capacitated facility location problems
Mathematical Programming 102:207-222, 2005.

## 2003

Searching the workplace web.
Proceedings of the 12th International World Wide Web Conference, pages 366-375, 2003.

Faster approximation algorithms for the minimum latency problem
Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms, pages 88-96, 2003.

## 2002

The Primal-Dual Method for Approximation Algorithms.
Mathematical Programming 91:447-478, 2002.

Improved approximation algorithms for MAX SAT.
Journal of Algorithms 42:173-202, 2002.

## 2001

The Approximability of Constraint Satisfaction Problems.
SIAM Journal on Computing 30:1863-1920, 2001.

Journal of the ACM 48:13-38, 2001.

## 2000

Gadgets, Approximation, and Linear Programming.
SIAM Journal on Computing 29:2074-2097, 2000.

Two-dimensional Gantt charts and a scheduling algorithm of Lawler.
SIAM Journal on Discrete Mathematics 13:281-294, 2000.

Node Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout.
SIAM Journal on Computing 29:1321-1333, 2000.

## 1999

Lecture Notes in Approximation Algorithms, Fall 1998.
IBM Research Report RC 21409, 1999.

## 1998

Lecture Notes in Approximation Algorithms, Spring 1998.
IBM Research Report RC 21273, 1998.

## 1997

Approximation Algorithms.
Proceedings of the National Academy of Sciences 94:12734–12735, 1997.

An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems.
Algorithmica 18:21-43, 1997. See also Erratum in Algorithmica 34:98-107.

Short shop schedules.
Operations Research 45:288-294, 1997.

## 1996

On the Number of Small Cuts in a Graph.
Information Processing Letters 59:41-44, 1996.

The primal-dual method for approximation algorithms and its application to network design problems.
In Approximation Algorithms for NP-hard Problems , Dorit S. Hochbaum, editor. PWS Publishing Company, Boston, MA, USA, 1996.

## 1995

Scheduling parallel machines on-line.
SIAM Journal on Computing 24:1313-1331, 1995.

A general approximation technique for constrained forest problems.
SIAM Journal on Computing 24:296–317, 1995.

## 1994

New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem.
SIAM Journal on Discrete Mathematics 7:656-666, 1994.

Approximating minimum-cost graph problems with spanning tree edges.
Operations Research Letters 16:183-189, 1994.

Improved approximation algorithms for network design problems.
Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms , pages 223-232, 1994.

## 1993

On the design of approximation algorithms for a class of graph problems.
Ph.D. thesis, MIT, Cambridge, MA, USA, September 1993.

A note on the prize-collecting traveling salesman problem.
Mathematical Programming 59:413-420, 1993.

## 1992

Analysis of the Held-Karp lower bound for the asymmetric TSP.
Operations Research Letters 12:83-88, 1992.

## 1991

Permutation vs. non-permutation flow shop schedules.
Operations Research Letters 10:281-284, 1991.

## 1990

Analysis of the Held-Karp heuristic for the traveling salesman problem.
Master’s thesis, MIT, Cambridge, MA, USA, June 1990. Also appears as MIT LCS Technical Report TR-479.