## Moses Charikar's Publications

Approximation Algorithms for Min-Sum Clustering,

*
in preparation.
*

Clustering Problems with Excluded Outliers,

*
in preparation.
*

Efficiently Finding Dense Components in Graphs,

*
in preparation.
*

Combinatorial Feature Selection Problems,

with V. Guruswami, S. Rajagopalan, S. Ravikumar and A. Sahai,

*
manuscript.
*

Minimum Outage Transmission over Fading Channels with Delay Constraint,

with R. Negi and J. Cioffi,

*
to appear in Proceedings of the IEEE International Conference on
Communications (ICC), 2000.
*

Towards Estimation Error Guarantees for Distinct Values

with S. Chaudhuri, R. Motwani and V. Narasayya,

*
to appear in Proceedings of the 19th ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems (PODS) 2000.
*

Query Strategies for Priced Information,

with R. Fagin, V. Guruswami, J. Kleinberg, P. Raghavan and A. Sahai

*
to appear in Proceedings of the 32nd Annual ACM Symposium on Theory of
Computing (2000).
*

Resource Optimization in QoS Multicast Routing of Real-Time Multimedia

with J. Naor and B. Schieber,

*
to appear in Proceedings of the 19th Annual IEEE INFOCOM (2000).
*

Improved Combinatorial Algorithms for the Facility Location and *k*-Median
Problems

with S. Guha,

*
in Proceedings of the 40th Annual IEEE Conference on Foundations of
Computer Science (1999),
*
extended version.

A Constant Factor Approximation Algorithm for the *k*-Median Problem

with S. Guha, E. Tardos and D. Shmoys,

*
in Proceedings of the 31st Annual ACM Symposium on Theory of
Computing (1999),
*

invited to special issue of JCSS for STOC '99.

On Targeting Markov Segments,

with P. Raghavan, S. Rajagopalan, S. Ravikumar, and A. Tomkins,

*
in Proceedings of the 31st Annual ACM Symposium on Theory of
Computing (1999),
*

invited to special issue of JCSS on Web algorithms.

Approximating Wire Length in Zero and Bounded Skew Clock Trees

with J. Kleinberg, S. Rajagopalan, S. Ravikumar, A. Sahai and A. Tomkins,

*
in Proceedings of the 10th Annual ACM-SIAM Symp. on Discrete Algorithms (1999),
*
extended version.

A Derandomization Using Min-Wise Independent Permutations,

with A. Broder and M. Mitzenmacher,

*
in Proceedings of the 2nd International Workshop on Randomization and
Approximation Techniques in Computer Science (1998).
*

Approximating a Finite Metric by a Small Number of Tree Metrics,

with C. Chekuri, A. Goel, S. Guha and S. Plotkin,

*
in Proceedings of the 39th Annual IEEE Conference on Foundations of
Computer Science (1998).
*

Delayed Information and Action in On-Line Algorithms,

with S. Albers and M. Mitzenmacher,

*
in Proceedings of the 39th Annual IEEE Conference on Foundations of
Computer Science (1998),
*
journal version.

The Finite Capacity Dial-A-Ride Problem,

with B. Raghavachari,

*
in Proceedings of the 39th Annual IEEE Conference on Foundations of
Computer Science (1998)
*

Min-Wise Independent Permutations,

with A. Broder, A. Frieze and M. Mitzenmacher,

*
in Proceedings of the 30th Annual ACM Symposium on Theory of
Computing (1998),
*

to appear in special issue of JCSS for STOC '98,
journal version.

Rounding Via Trees: Deterministic Approximation Algorithms for Group
Steiner Trees and *k*-Median,

with C. Chekuri, A. Goel and S. Guha,

*
in Proceedings of the 30th Annual ACM Symposium on Theory of
Computing (1998).
*

Algorithms for Capacitated Vehicle Routing

with S. Khuller and B. Raghavachari,

*
in Proceedings of the 30th Annual ACM Symposium on Theory of
Computing (1998).
*

Approximation Algorithms for Directed Steiner Tree Problems,

with C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha and M. Li,

*
in Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (1998),
*

to appear in Journal of Algorithms.

The Dynamic Servers Problem,
with D. Halperin and R. Motwani,

*
in Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (1998).
*

On-line Load Balancing for Related Machines,

with P. Berman and M. Karpinski,

*
in Proceedings of Workshop on Algorithms and Data Structures (WADS), (1997),
*

to appear in Journal of Algorithms,
journal version.

Constrained TSP and Low Power Computing,

with C. Silverstein, R. Motwani and P. Raghavan,

*
in Proceedings of Workshop on Algorithms and Data Structures (WADS), (1997).
*

Incremental Clustering and Dynamic Information Retrieval,
with C. Chekuri, T. Feder and R. Motwani,

*
in Proceedings of the 29th Annual ACM Symposium on Theory of Computing (1997).
*

On Page Migration and Other Relaxed Task Systems,
with Y. Bartal and P. Indyk,

*
in Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (1997),
*

to appear in special issue of TCS for OLA '98.

Moses Charikar
Last modified: Tue Dec 21 04:56:03 PST 1999