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 of algorithms for problems in network routing and design, game theory, combinatorial optimization, linear and integer programming. My research focusses on both exact algorithms and approximation algorithms.
Some recent papers:
Fast-Converging Tatonnement Algorithms for One-Time and Ongoing Market Problems
(with Richard Cole) To appear in STOC, May 2008. A version with 2 fewer typos:
pdf.
Prompt Mechanisms for Online Auctions
(with Richard Cole and Shahar Dobzinski) To appear in SAGT, April 2008.
pdf.
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.
Ordering by Weighted Number of Wins Gives a Good Ranking for
Weighted Tournaments
(with D. Coppersmith and A. Rudra).
17th Annual Symposium on Discrete Algorithms (SODA),
January, 2006. pdf.
Tight Approximation Algorithms for Maximizing General
Assignment Problems
(with M. Goemans, V. Mirrokni, and M. Sviridenko).
17th Annual Symposium on Discrete Algorithms (SODA),
January 2006. 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.
Quickest Flows Over Time
(with M. Skutella). To appear in SIAM J. Computing .
pdf
Journal version combining parts of a SODA 2003 paper
and an IPCO 2002 paper (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.
Polynomial-Time Separation of a Superclass of Simple Comb Inequalities
(with A. Letchford and A. Lodi)
To appear in Math. of Operations Research
ps.gz.
pdf
Iterative Rounding 2-Approximation Algorithms for Minimum-Cost
Vertex Connectivity Problems
(with K. Jain and D. P. Williamson)
To appear in Journal Comput. System Sci. special issue
devoted to FOCS 2001.
(Combines FOCS 2001 paper and IPCO 2001 paper listed below.)
ps.gz.
pdf
Some other papers organized by topic:
Minimum Cost Flows Over Time without Intermediate Storage (with Martin Skutella). 35th ACM/SIAM Symp. on Discrete Algorithms (SODA), January 2003, 66-75. pdf 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.
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.
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.)
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
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