Copyright Notice: Since most of these papers are published, the copyright has been transferred to the respective publishers. Therefore, the papers cannot be duplicated for commercial purposes. The following is ACM's copyright notice; other publishers have similar ones.

Copyright © 199x by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.

The papers are in roughly reverse chronological order.

• A Constant Factor Approximation for the Single-Sink Edge Installation Problem (with A. Meyerson and K. Munagala)
  To appear in ACM Symposium on Theory of Computing , 2001.
• Improved Approximation Algorithms for Fault-tolerant Facility Location (with A. Meyerson and K. Munagala)
  To appear in ACM-SIAM Symposium on Discrete Algorithms , 2001.
• Hierarchical Placement and Network Design Problems (with A. Meyerson and K. Munagala)
  To appear in IEEE Foundations of Computer Science , 2000.
• Clustering Data Streams (with N. Mishra, R. Motwani, and L. O'callahan)
  To appear in IEEE Foundations of Computer Science , 2000.
• Nested Graph Dissection and Approximation Algorithms
  To appear in IEEE Foundations of Computer Science , 2000.
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas (with G. Even and B. Schieber)
  In Proceedings of ACM Symposium on Theory of Computing, 2000, extended version.
• Improved Combinatorial Algorithms for Facility Location and K-Median Problems (with M. Charikar)
  In Proceedings of IEEE Foundations of Computer Science, 1999, extended version.


• A Constant Factor Approximation for the K-Median Problem (with M. Charikar, E. Tardos and D. Shmoys)
  In Proceedings of ACM Symposium on Theory of Computing, 1999, conference version.


• Approximating the Throughput of Real-time Multiple Machine Scheduling (with A. Bar-noy, J. Naor and B. Schieber)
  In Proceedings of ACM Symposium on Theory of Computing, 1999, conference version.


• Efficient Recovery from Power Outage (with A. Moss, J. Naor and B. Schieber)
  In Proceedings of ACM Symposium on Theory of Computing, 1999, extended version.


• Approximating a finite metric by small number of trees (with M. Charikar, C. Chekuri, A. Goel, and S. Plotkin)
  In Proceedings of IEEE Foundations of Computer Science, 1998, conference version.


• Multicasting in Heterogeneous Networks (with A. Bar-noy, J. Naor and B. Schieber)
  In Proceedings of ACM Symposium on Theory of Computing, 1998, extended version, to appear in SIAM Journal of Computing .


• Rounding via trees : Deterministic approximation algorithms for Group Steiner trees and k - median (with M. Charikar, C. Chekuri, and A. Goel)
  In Proceedings of ACM Symposium on Theory of Computing, 1998, conference version.


• Greedy strikes back: Improved Facility Location Algorithms. (with Samir Khuller)
  In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 1998, extended version in Journal of Algorithms .


• Approximation Algorithms for Directed Steiner Trees. (with M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel and M. Li)
  In Proceedings of ACM-Siam Symposium on Discrete Algorithms, 1998, extended version to appear in Journal of Algorithms .


• ROCK - A Robust Clustering Algorithm for Categorical Attributes, (with R. Rastogi, and K. Shim)
  In Proceedings of IEEE International Conference on Data Engineering, 1999.


• CURE - An Efficient Clustering Algorithm for Large Databases, (with R. Rastogi, and K. Shim)
  In Proceedings of ACM-SIGMOD International Conference on Management of Data, 1998.


• Facility Location with Dynamic Distance Functions (with R. Bhatia, S. Khuller and Y. Sussmann)
  In Journal of Combinatorial Optimization, 1998.


• Approximation Algorithms for Connected Dominating Sets. (with Samir Khuller)
  In Proceedings of European Symposium on Algorithms 1996, extended version in Algorithmica 1998, vol 20.


• Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets. (with Samir Khuller)
  To appear in Information and Computation


• Connected Facility Location Problems (with S. Khuller)
  In proceedings of DIMACS Workshop on Network Design: Connectivity and Facilities Location, 1998. Unavailable.