Moses Charikar's Publications


Topics

Approximation:
SDP

Approximation: Clustering

Approximation:
Network Design

Approximation: TSP and Routing

Other Approximation 

Sketching, Streaming and Similarity Search

Finite Metrics

Online Algorithms

Other Publications


Recent Papers

Approximation Algorithms: Semidefinite Programming

  • Near-Optimal Algorithms for Unique Games
    with Konstantin Makarychev and Yury Makarychev,
    in Proceedings of the 38th ACM Symposium on Theory of Computing (2006).
  • New Approximation Guarantees for Chromatic Number
    with Sanjeev Arora and Eden Chlamtac,
    in Proceedings of the 38th ACM Symposium on Theory of Computing (2006).
  • l22 spreading metrics for vertex ordering problems
    with MohammadTaghi Hajiaghayi, Howard Karloff and Satish Rao

    in Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (2006).
  • O(sqrt{log n}) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems
    with Amit Agarwal, Konstantin Makarychev, Yury Makarychev,
    in Proceedings of the 37th ACM Symposium on Theory of Computing (2005).
  • Maximizing quadratic programs: extending Grothendieck's inequality
    with Anthony Wirth,
    in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (2004).
  • On Semidefinite Programming Relaxations for Graph Coloring and Vertex Cover,
    in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, (2002).

Approximation Algorithms: Clustering Problems

Approximation Algorithms: Network Design

Approximation Algorithms: TSP and Routing

Other Approximation Algorithms

Sketching, Streaming and Similarity Search

Finite Metrics

  • Directed Metrics and Directed Graph Partitioning Problems
    with Konstantin Makarychev and Yury Makarychev

    in Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (2006).
  • Fitting tree metrics: Hierarchical Clustering and Phylogeny
    with Nir Ailon,
    in Proceedings of the 46th
    Annual IEEE Symposium on Foundations of Computer Science (2005).
  • A Tight Threshold for Metric Ramsey Phenomena
    with Adriana Karagiozova,
    in Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (2005).
  • On the Impossibility of Dimension Reduction in l1
    with B. Brinkman, 
    in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (2003),
    best paper award.
  • Dimension Reduction in the l1 norm,
    with A. Sahai,
    in Proceedings of the 43rd Annual IEEE Conference on Foundations of Computer Science (2002).
  • 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).

On-line Algorithms

Other Publications

  • Minimum Outage Transmission over Fading Channels with Delay Constraint,
    with R. Negi and J. Cioffi,
    in Proceedings of the IEEE International Conference on Communication, (2000).
  • 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).
  • 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).