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 following is a ``very coarse" categorization; in each the papers are in roughly reverse chronological
order.

Asymmetric Kcenter is Omega(log* n) hard to approximate
(with J. Chuzhoy, E. Halperin, S. Khanna, G. Kortsarz, R. Krauthgamer, and J. Naor).

Improved Combinatorial Algorithms
for Facility Location Problems
(with M. Charikar)
The above contains a local search based facility location algorithm.
The previous version
also contained the full proof of the integrality gap
of the Kmedian problem being
at most 4.

A Constant Factor Approximation for the KMedian Problem
(with M. Charikar, E. Tardos and D. Shmoys)
The above is an extended version. The conference version also contained some
extra results on the capacitated problem.

A Constant Factor Approximation
Algorithm for the Faulttolerant Facility Location Problem
(with A. Meyerson and K. Munagala)

Improved Algorithms for the Data
Placement Problem
(with K. Munagala)

Generalized Clustering
(with K. Munagala)

ROCK  A Robust Clustering
Algorithm for Categorical Attributes,
(with R. Rastogi, and K. Shim)

Greedy strikes back: Improved
Facility Location Algorithms.
(with Samir Khuller)

CURE  An Efficient Clustering
Algorithm for Large Databases,
(with R. Rastogi, and K. Shim)

Facility Location with Dynamic
Distance Functions
(with R. Bhatia, S. Khuller and Y. Sussmann)

Machine minimization for scheduling jobs with interval constraints
(with J. Chuzhoy, S. Khanna, and J. Naor)

Approximating Steiner kcuts
(with C. Chekuri and J. Naor )

Throughput Maximization of RealTime Scheduling with Batching
(with A. Barnoy, Y. Katz, J. Naor, B. Schieber and H. Shachnai)

Capacitated Vertex Covering with
Applications
(with R. Hassin S. Khuller and E. Or)

A Constant Factor Approximation for
the SingleSink Edge Installation Problem
(with A. Meyerson and K. Munagala).

Hierarchical Placement and Network
Design Problems
(with A. Meyerson and K. Munagala).
See the above paper for the journal version.

Nested Graph Dissection and Approximation
Algorithms

Improved Approximations of Crossings in
Graph Drawings and VLSI Layout Areas
(with G. Even and B. Schieber)

Approximating the Throughput of
Realtime Multiple Machine Scheduling
(with A. Barnoy, J. Naor and B. Schieber)

Efficient Recovery from Power Outage
(with A. Moss, J. Naor and B. Schieber)

Approximating a finite
metric by small number of trees
(with M. Charikar, C. Chekuri, A. Goel, and S. Plotkin)

Multicasting in Heterogeneous
Networks
(with A. Barnoy, J. Naor and B. Schieber)

Rounding via trees :
Deterministic approximation algorithms for
Group Steiner trees and k 
median
(with M. Charikar, C. Chekuri, and A. Goel)

Approximation Algorithms for
Directed Steiner Trees.
(with M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel and M. Li)

Improved Methods for
Approximating Node Weighted Steiner Trees and
Connected Dominating Sets.
(with S. Khuller)

Approximation Algorithms for Connected Dominating Sets.
(with S. Khuller)

Improving the Performance of List Intersection.
(with D. Tsirogiannis and N. Koudas).

Learning to create data integrating queries
(with P. Talukdar, M. Jacob, M. Mehmood, K. Crammer, Z. Ives, and F. Pereira)

Adhoc aggregations of ranked lists in the presence of hierarchies
(with N. Bansal, and N. Koudas)

Approximate XML Joins
(with H. Jagadish, N. Koudas, D. Srivastava, and T. Yu)

Merging the Results of Approximate Match Operations
(with N. Koudas, A. Marathe, and D. Srivastava)

Efficient Approximation of Optimization
Queries Under Parametric Aggregation Constraints
(with D. Gunopoulos, N. Koudas, D. Srivastava, and M. Vlachos)

Fast Algorithms For Hierarchical Range Histogram Construction
(with N. Koudas, and D. Srivastava)