Conference

Better algorithms for minimizing average flow-time on related machines.
33rd International Colloquium on Automata, Languages and Programming
(with Amit Kumar)

Minimizing average flow-time on related machines.
35th Annual ACM Symposium on Theory of Computing, 2006
(with Amit Kumar)

Price of Anarchy, Locality Gap, and a Network Service Game.
1st Workshop on Internet and Network Economics, 2005:1046-1055.
(with N. Devanur, R. Khandekar, V. Pandit, A. Saberi and V. Vazirani)

Heuristic improvements for computing max multicommodity flow and min multicut.
13th European Symposium on Algorithms, 2005:35-46.
(with G. Batra and G. Gupta)

Saving an epsilon: a 2-approximation for the k-MST problem in graphs. 
34th Annual ACM Symposium on Theory of Computing, 2005:396-402.

Improved approximation for universal facility location.
16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005:959-960.
(with R. Khandekar and V. Pandit)

Fractional covering with upper bounds on the variables: Solving LPs with negative entries.
12th European Symposium on Algorithms, 2004:371-382
(with R. Khandekar) [ps]

Covering graphs using stars and trees.
6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2003:24-35. 
(with G. Even, J. Konemann, R. Ravi and A. Sinha)[citeseer][ps]

Bandwidth maximization in multicasting.
11th European Symposium on Algorithms, 2003:242-253
(with R. Khandekar, K. Kunal and V. Pandit) [citeseer]

On-line end-to-end congestion control.
43rd Annual IEEE Symposium on Foundations of Computer Science, 2002:303-312 
(with N. Young) [citeseer][ps]

Local Search Heuristics for k-median and facility location problems. 
33rd Annual ACM Symposium on Theory of Computing, 2001:21-29. 
(with V. Arya, R. Khandekar, K. Munagala, A. Meyerson and V. Pandit) [citeseer]

On the Integrality Gap of a Natural Formulation of the Single-Sink Buy-at-bulk Network Design Problem.
Integer Programming and Combinatorial Optimization, 2001:170-184.  
(with R. Khandekar, G. Konjevod, R. Ravi, F.S. Salman and A. Sinha) [citeseer]

A randomized algorithm for flow-shop scheduling.
19th International Conference on Foundations of Software Technology and Theoretical Computer Science, 1999:213-218.
(with S. Jain and C. Swamy) [citeseer][ps]

On the single-source unsplittable flow problem.
39th Annual IEEE Symposium on Foundations of Computer Science, 1998:290-299.
(with Y. Dinitz and M.X. Goemans) [citeseer]

Faster and simpler algorithms for multicommodity flow and other fractional packing problems.
39th Annual IEEE Symposium on Foundations of Computer Science, 1998:253-259.
(with J. Konemann) [citeseer][citeseer]

Minimizing stall time in single and parallel disk systems.
30th Annual ACM Symposium on Theory of Computing, 1998:454-462.
(with S. Albers and S. Leonardi) [citeseer]

A polylogarithmic approximation algorithm for the group steiner tree problem. 
9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998:253-259. 
(with G. Konjevod and R. Ravi) [citeseer]

Distributed List Coloring: How to Dynamically Allocate Frequencies to Mobile Base Stations. 
8th IEEE Symposium on Parallel and Distributed Processing, 1996:18-25.
(with M. Papatriantafilou and P. Tsigas) [citeseer]

A 3-approximation algorithm for the minimum tree spanning k vertices. 
37th Annual IEEE Symposium on Foundations of Computer Science, 1996:302-309.[citeseer][ps]

Finding separator cuts in planar graphs within twice the optimal.
35th Annual IEEE Symposium on Foundations of Computer Science, 1994:14-23.
(with H. Saran and V.V. Vazirani) [citeseer]

Multiway cuts in directed and node weighted graphs.
21st International Colloquium on Automata, Languages and Programming,1994:487-498.
(with V.V. Vazirani, and M. Yannakakis) [citeseer]

An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane.
26th Annual ACM Symposium on Theory of Computing, 1994:432-438.
(with D.S. Hochbaum) [citeseer][ps]

A scaling technique for better network design.
5th Annual ACM-SIAM Symposium on Discrete Algorithms, 1994:233-240.
(with M. Aggarwal) [citeseer][ps]

Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover.
20th International Colloquium on Automata, Languages and Programming, 1993:64-75.
(with V.V. Vazirani, and M. Yannakakis) [citeseer][ps]

Approximate max-flow min-(multi)cut theorems and their applications.
25th Annual ACM Symposium on Theory of Computing, 1993:698-707.
(with V.V. Vazirani, and M. Yannakakis][citeseer][citeseer]

A polyhedron with all s--t cuts as vertices, and adjacency of cuts.
3rd Integer Programming and Combinatorial Optimization Conference, 1993:281-289.
(with V.V. Vazirani) [citeseer]