Moses Charikar's Publications

Publications grouped by topic

• Near-Optimal Algorithms for Unique Games
  with Konstantin Makarychev and Yury Makarychev,
  to appear in Proceedings of the 38th ACM Symposium on Theory of Computing (2006).
• New Approximation Guarantees for Chromatic Number
  with Sanjeev Arora and Eden Chlamtac,
  to appear in Proceedings of the 38th ACM Symposium on Theory of Computing (2006).
  
• Ferret: A Toolkit for Content-Based Similarity Search
  with Christine Lv, William Josephson, Zhe Wang and Kai Li,
  to appear in Proceedings of ACM SIGOS EuroSys Conference (2006).
  
• l₂² 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).
  
• 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).
  
• A Robust Maximum Completion Time Measure for Scheduling
  with Samir Khuller,
  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).
• Sampling Bounds for Stochastic Optimization
  with Chandra Chekuri and Martin Pal,
  in Proceedings of APPROX-RANDOM (2005).
• 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).
  
• Aggregating Inconsistent Information: Ranking and Clustering
  with Nir Ailon and Alantha Newman,
  in Proceedings of the 37th ACM Symposium on Theory of Computing (2005).
  
• On Non-uniform Multicommodity Buy-at-Bulk Network Design
  with Adriana Karagiozova,
  in Proceedings of the 37th ACM Symposium on Theory of Computing (2005).
  
• A Tight Threshold for Metric Ramsey Phenomena
  with Adriana Karagiozova,
  in Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (2005).
  
• Approximation the Average Response Time in Broadcast Scheduling
  with Nikhil Bansal, Sanjeev Khanna and Seffi Naor,
  in Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (2005).
  
• Image Similarity Search with Compact Data Structures
  with Qin Lv and Kai Li,
  in Proceedings of the ACM Conference on Information and Knowledge Management (CIKM 2004).
  
• On the Advantage of Network Coding for Improving Network Throughput 
  with Amit Agarwal,
  in Proceedings of the IEEE Information Theory Workshop (2004).
  
• 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 the Integrality Ratio for Asymmetric TSP
  with Michel X. Goemans and Howard Karloff,
  in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (2004).
  
• On the Impossibility of Dimension Reduction in l₁
  with Bo Brinkman, 
  in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (2003), best paper award.
  
• Clustering with Qualitative Information,
  with Venkatesan Guruswami and Anthony Wirth,
  in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (2003).
  
• Better Streaming Algorithms for Clustering Problems,
  with L. O'Callaghan and R. Panigrahy,
  in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, (2003).
  
• Dimension Reduction in the l₁ norm,
  with A. Sahai,
  in Proceedings of the 43rd Annual IEEE Conference on Foundations of Computer Science (2002).
  
• New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching and Related Problems,
  with P. Indyk and R. Panigrahy,
  in Proceedings of the 29th International Colloquium on Automata Languages and Programming, (2002).
  
• Finding Frequent Items in Data Streams,
  with K. Chen and M. Farach-Colton,
  in Proceedings of the 29th International Colloquium on Automata Languages and Programming, (2002).
  
• Similarity Estimation Techniques from Rounding Algorithms,
  in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, (2002).
  
• Approximating The Smallest Grammar: Kolmogorov Complexity in Natural Models,
  with E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Rasala, A. Sahai, and A. Shelat,
  in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, (2002).
  
• On Semidefinite Programming Relaxations for Graph Coloring and Vertex Cover,
  in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, (2002).
  
• Clustering to Minimize the Sum of Cluster Diameters,
  with R. Panigrahy,
  in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, (2001).
  
• Approximating Min-Sum k-Clustering in Metric Spaces,
  with Y. Bartal and D. Raz,
  in Proceedings of the 33rd Annual ACM Symposium on Theory of  Computing, (2001).
  
• Algorithms for Facility Location with Outliers,
  with S. Khuller, D. Mount and G. Narasimhan,
  in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, (2001).
  
• Combinatorial Feature Selection Problems,
  with V. Guruswami, S. Rajagopalan, S. Ravikumar and A. Sahai,
  in Proceedings of the 41st Annual IEEE Conference on Foundations of Computer Science, (2000).
  
• Resource Optimization in QoS Multicast Routing of Real-Time Multimedia
  with J. Naor and B. Schieber,
  in Proceedings of the 19th Annual IEEE INFOCOM (2000).
  
• Greedy Approximation Algorithms for Finding Dense Components in Graphs,
  in Proceedings of APPROX, (2000).
  
• 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).
  
• Query Strategies for Priced Information,
  with R. Fagin, V. Guruswami, J. Kleinberg, P. Raghavan and A. Sahai,
  in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (2000), in special issue of JCSS for STOC 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).
  
• 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 Symposium on Discrete Algorithms (1999), extended version.
  
• 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).
  
• The Finite Capacity Dial-A-Ride Problem,
  with B. Raghavachari,
  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 Information and Computation, vol 170, pp. 135-152 (2001), preliminary version in Proceedings of the 39th Annual IEEE Conference on Foundations of Computer Science (1998).
  
• 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).
  
• Min-Wise Independent Permutations,
  with A. Broder, A. Frieze and M. Mitzenmacher,
  in Journal of Computer Systems and Sciences, vol. 60(3), pp. 630-659 (2000) (special issue for STOC '98), preliminary version in Proceedings of the 30th Annual ACM Symposium on Theory of Computing (1998),
  
• 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 Journal of Algorithms, vol. 33, pp. 73-91 (1999), preliminary version in Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (1998).
  
• The Dynamic Servers Problem, 
  with D. Halperin and R. Motwani,
  in Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (1998).
  
• 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-line Load Balancing for Related Machines,
  with P. Berman and M. Karpinski,
  in Journal of Algorithms, vol. 35(1), pp. 108-121, (2000), preliminary version in Proceedings of Workshop on Algorithms and Data Structures (WADS), (1997).
  
• 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).
  
• On Page Migration and Other Relaxed Task Systems, 
  with Y. Bartal and P. Indyk,
  in Theoretical Computer Science, vol. 268(1), pp. 43-66 (2001), preliminary version in Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (1997).