If you would like to receive a copy of a paper not available here, you can email me at my three initials at cs dot dartmouth dot edu.
I work in design and analysis of algorithms for problems in algorithmic game theory and economics, network routing and design, combinatorial optimization, linear and integer programming. My research focusses on both exact algorithms and approximation algorithms.
Papers organized by topic (with a few repetitions to reflect topic overlap):
Simple Sybil Proof Mechanisms for Multi-Level Marketing (with Fabio Drucker)
Online Mixed Packing and Covering (with Umang Bhaskar). Submitted.
When the Cut Condition is Enough: A Complete Characterization for
Series-Parallel Graphs
(with Amit Chakrabarti and Christophe Weibel). Submitted.
Approximately Optimal Auctions for Selling Privacy when Costs
are Correlated with Data
(with Yu-Han Lyu). Submitted.
Lower Bound for Envy-free and Truthful Makespan Approximation on
Related Machines
(with Zhenghui Wang) SAGT, October 2011.
full version
A Stackelberg Strategy for Routing Flows Over Time
(with Umang Bhaskar and Elliot Anshelevich) SODA, January 2011.
pdf
full version
Also, check out our related
SIGecom Exchanges
article.
The Price of Collusion in Series Parallel Networks
(with Umang Bhaskar and Chien-Chung Huang) IPCO, June 2010.
pdf
Preference-Constrained Oriented Matching
(with Zoya Svitkina) ANALCO, January 2010.
pdf
Ordering by Weighted Number of Wins Gives a Good Ranking for
Weighted Tournaments
(with D. Coppersmith and A. Rudra).
Transactions on Algorithms 6(3) 2010.
Journal version of SODA 2006 paper. pdf.
Equilibria of Atomic Flow Games are not Unique
(with Umang Bhaskar, Darrell Hoy, Chien-Chung Huang)
SODA, January 2009.
pdf.
A Fast and Simple Algorithm for Computing Market Equilibria
(with Rahul Garg, Sanjiv Kapoor, Rohit Khandekar, Amin Saberi)
WINE, December 2008.
pdf.
Fast-Converging Tatonnement Algorithms for One-Time and Ongoing Market Problems
(with Richard Cole) STOC, May 2008.
pdf.
Prompt Mechanisms for Online Auctions
(with Richard Cole and Shahar Dobzinski) Symposium on Algorithmic Game Theory,
April 2008.
pdf.
Tolls for Heterogeneous Selfish Users in Multicommodity Networks and
Generalized Congestion Games
(with K. Jain and M. Mahdian).
45th Annual Symposium of the Foundations of Computer Science (FOCS),
October, 2004, 277-285. ps.gz,
pdf.
Linear Tolls Suffice: New Bounds and Algorithms for Tolls in
Single Source Networks
Theoretical Computer Sci. 348:2-3 (2005), 217-225.
Special issue devoted to ICALP 2004.
ps.gz.
pdf.
Tight Approximation Algorithms for Maximizing General
Assignment Problems
(with M. Goemans, V. Mirrokni, and M. Sviridenko).
Math. Oper. Res. 36:3 (2011), 416-431.
pdf.
(An extended abstract appeared in SODA 2006.)
Data Center Scheduling, Generalized Flows, and Submodularity
ANALCO, January 2010.
pdf
Quickest Flows Over Time
(with M. Skutella). SIAM J. Computing 36 :6 (2007), 1600-1630.
pdf
Combined journal version of SODA 2003 and IPCO 2002 extended abstracts listed
below.
Efficient Algorithms for Separated Continuous Linear Programs:
the Multicommodity Flow Problem with Holding Costs and Extensions.
(with Jay Sethuraman).
Math. of Operations Research 30:4 (2005), 916-938.
pdf
Extended, improved version of SODA 2003 extended abstract:
Approximating Optimal Control of Fluid Networks
Further Improvements in Competitive Guarantees for QoS Buffering
(with N. Bansal, T. Kimbrel, M. Mahdian, B. Schieber, M. Sviridenko).
31st Annual Colloquium on Autonomata, Languages, and Programming (ICALP)
July 2004, 196-207.
ps.gz.
pdf.
Minimum Cost Flows Over Time without Intermediate Storage
(with Martin Skutella).
35th ACM/SIAM Symp. on Discrete Algorithms (SODA),
January 2003, 66-75. pdf
This extended abstract contains a section not in the above SICOMP paper.
The Quickest Multicommodity Flow Problem
(with Martin Skutella).
Integer Programming and Combinatorial Optimization (IPCO)
Conference Proceedings , LNCS 2337, May 2002, 36-53.
ps.gz
Universally Maximum Flow with Piece-wise
Constant Capacity Functions
Networks , 38 (2001), no. 3, 1-11.
(Extended abstract appeared in Proceedings of IPCO 1999.)
Optimal Rounding of Instantaneous Fractional Flows Over Time
(with James B. Orlin). SIAM J. on Discrete Math.
13 (2000), no.2, 145-153.
ps.gz
Faster Algorithms for the Quickest Transshipment Problem.
SIAM J. on Optimization 12 (2001), no. 1, 18-35.
(This is a revision of extended abstract in SODA 1998.)
Efficient Continuous-Time Dynamic Network Flow Algorithms
(with Eva Tardos), Operations Research Letters 23
(1998) pp. 71-80.
Scheduling Parallelizable Tasks to Minimize Average Response Time
(with J. Turek, W. Ludwig, J. L. Wolf, P. Tiwari, J. Glasgow,
U. Schweigelshohn, P. S. Yu), ACM Symposium on Parallel Algorithms
and Architectures (SPAA) Cape May, 1994.
Submodular Approximation: Sampling-based Algorithms and Lower Bounds
(with Zoya Svitkina) SIAM J. Computing 40:6 (2011) 1715-1737.
pdf.
(An extended abstract appeared in FOCS 2008.)
Data Center Scheduling, Generalized Flows, and Submodularity
ANALCO, January 2010.
pdf
A Push-Relabel Framework for Submodular Function Minimization
and Applications to Parametric Optimization
(with Satoru Iwata)
Discrete Applied Mathematics , 131 (2003) 311-322.
Special issue on submodularity.
ps.gz.
pdf
A Combinatorial, Strongly Polynomial-Time Algorithm
for Minimizing Submodular Functions
(with Satoru Iwata and Satoru Fujishige),
Journal of the ACM 48 (2001), no. 4, 761-777.
ps.gz.
pdf
(An extended abstract appeared in STOC 2000.)
Improved Algorithms for Submodular Function Minimization and Submodular
Flow
(with Satoru Iwata)
Proceedings of the 32nd ACM Symposium on Theory of Computing ,
May, 2000.
A Faster Capacity Scaling Algorithm for Minimum Cost Submodular Flow
(with Satoru Iwata and S. Thomas McCormick)
Math. Programming 92 (2002), no. 1, 119-139.
ps.gz.
pdf
Recent Progress in Submodular Function Minimization
OPTIMA: Mathematical Programming Society Newsletter ,
September 2000, no.64, 1-11.
Efficient Algorithms for Separated Continuous Linear Programs:
the Multicommodity Flow Problem with Holding Costs and Extensions.
(with Jay Sethuraman).
Math. of Operations Research . 30:4 (2005), 916-938.
pdf
Extended, improved version of SODA 2003 extended abstract:
Approximating Optimal Control of Fluid Networks
Fast Approximation Algorithms for Fractional Covering Problems
with Box Constraints
Proceedings of the 36th ACM/SIAM Symposium on Discrete Algorithms ,
January 2004. Journal version: ps.gz.
pdf
A Scalable Algorithm for the Minimum Expected Cost, Restorable Flow Problem
,
(with Adam Meyerson, Iraj Saniee, Bruce Shepherd, and Aravind Srinivasan)
Presented at DIMACS
Mini-Workshop on Quality of Services Issues on the
Internet, February, 2001, as
Fast and efficient bandwith reservation for robust routing.
Preliminary version available as
CORC
technical report TR-2003-10. February 2004 version:
ps.gz.
pdf.
Approximating Fractional Multicommodity Flows Independent of
the Number of Commodities ,
SIAM J. Discrete Math. 13 (2000), no. 4, 505-520.
ps.gz.
pdf.
(This is a revision of extended abstract in FOCS 1999.)
Fast and Simple Approximation Schemes for Generalized Flow
(with Kevin D. Wayne).
Math. Programming 91 (2002), no 2, 215-238.
ps.gz.
pdf.
(This is a generalization of an extended abstract in SODA 1999.)
Strict Cost-Sharing Schemes for Steiner Forest
(with J. Konemann, S. Leonardi, and G. Schaefer)
SIAM J. Computing 39 (8): 3616-3632 (2010).
Simple Cost-Sharing Schemes for Multicommodity Rent-or-Buy and Stochastic
Steiner Tree
(with J. Konemann, S. Leonardi, and G. Schaefer) STOC, May 2006.
pdf.
Iterative Rounding 2-Approximation Algorithms for Minimum-Cost
Vertex Connectivity Problems
(with K. Jain and D. P. Williamson)
Journal Comput. System Sci. 72 (2006) 832--867.
Special issue devoted to FOCS 2001.
(Combines FOCS 2001 paper and IPCO 2001 paper listed below.)
ps.gz.
pdf
An Iterative Rounding 2-Approximation Algorithm for the Element
Connectivity Problem
(with Kamal Jain and David Williamson).
42nd Annual Symposium of the Foundations of Computer Science ,
(October 2001), 339-347.
A 2-approximation for Minimum Cost {0,1,2} Vertex Connectivity .
Proceedings of Integer Programming and Combinatorial Optimization
(June 2001), 115-129.
Strengthening Integrality Gaps for Capacitated Network Design and
Covering Problems
(with Robert D. Carr, Vitus J. Leung, and Cynthia A. Phillips)
Proceedings of the 11th ACM/SIAM Symposium on Discrete Algorithms,
January 2000.
ps.gz.
pdf
Polynomial-Time Separation of a Superclass of Simple Comb Inequalities
(with A. Letchford and A. Lodi)
Math. of Operations Research 31 : 4 (2006), 696--713.
ps.gz.
pdf
Separating Maximally Violated Combs in Planar Graphs
(with Eva Tardos),
Mathematics of Operations Research 24 :1
(1999) pp. 130-148. (This is a revision
of extended abstract in IPCO 1996.)
Building Chain and Cactus Representations of All Minimum Cuts
from Hao-Orlin in the Same Asymptotic Run Time.
Journal of Algorithms 33 (1999) no. 1, 51-72.
(This is revision of extended abstract in IPCO 1998.)
On Identifying Strongly Connected Components in Parallel
(with Bruce Hendrickson and Ali Pinar)
Proceedings of IRREGULAR 2000, LNCS 1800, 505-511.
Simplified version also with Don Coppersmith available
as IBM Research Report RC23744:
pdf