Papers



Publications


Conference Proceedings

Minimizing Weighted Flow Time, with Nikhil Bansal. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003.

Non-Clairvoyant Scheduling for Mean Slowdown, with Nikhil Bansal, Jochen Konemann and Amitabh Sinha. In Proc. of 20th Intl. Symposium on Theoretical Aspects of Computer Science (STACS) 2003.

Scheduling for Flow-Time with Admission Control (or How to manage your to-do list), with Nikhil Bansal, Avrim Blum and Shuchi Chawla. In European Symposium on Algorithms (ESA), 2003.

Approximating average distortion for embeddings into line, with Anupam Gupta and R. Ravi. In Symposium on Theoretical Aspects of Computer Science (STACS) 2004.

WIC: A General-Purpose Algorithm for Monitoring Web Information Sources, with Sandeep Pandey and Chris Olston. In VLDB 2004.

Approximating additive distortion of line embeddings In RANDOM-APPROX 2004.

Finding (Recently) Frequently Items in Distributed Data Streams, with A. Manjhi, V Shkapenyuk, C. Olston. In ICDE 2005.

Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces, with M. Badoiu, A. Gupta, Y. Rabinovich, H. Raecke, R. Ravi, A. Sidiropoulos. In SODA 2005.

On Stochastic Minimum Spanning Tree, with R. Ravi and Mohit Singh. To appear in IPCO 2005.

Metric Embeddings with Relaxed Guarantees, with Ittai Abraham, Yair Bartal, T-H. Hubert Chan, Anupam Gupta, Jon Kleinberg, Ofer Neiman and Aleksandrs Slivkins. To appear in FOCS 2005.

How to Pay Come What May : Approximation Algorithms for Demand-Robust Covering Problems, with Vineet Goyal, R. Ravi and, Mohit Singh. To appear in FOCS 2005.

Improved Embeddings of Graph Metrics into Random Trees, with Anupam Gupta, Harald Raecke. To appear in SODA 2006.

Workshops

Scheduling for Flow-Time with Admission Control (or How to manage your to-do list), with Nikhil Bansal, Avrim Blum and Shuchi Chawla. In MAPSP 2003.

Comparison of the Haplotype Motif and Block Models using the Principle of Minimum Description, with S. Sridhar, Guy Blelloch, R. Ravi and R. Schwartz. To appear in The Workshop on Genomic Studies and the HapMap 2005.

Journals

Minimizing Weighted Flow Time, with Nikhil Bansal. Invited in Journal of Algorithms.

Non-Clairvoyant Scheduling for Mean Slowdown, with Nikhil Bansal, Jochen Konemann and Amitabh Sinha. Invited for Algorithmica.

Approximating average distortion for embeddings into line, with Anupam Gupta and R. Ravi. Invited to Theory of Computing Systems.

Talks