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