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

• Tight Hardness Results for Minimizing Discrepancy
  with Alantha Newman and Aleksander Nikolov,
  to appear in Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (2011).
• Vertex Sparsifiers and Abstract Rounding Algorithms
  with Tom Leighton, Shi Li and Ankur Moitra,
  in Proceedings of the 51st Annual IEEE Conference on Foundations of Computer Science (2010).
• Detecting high log-densities: an O(n^1/4) approximation for densest k-subgraph
  with Aditya Bhaskara, Eden Chlamtac, Uri Feige and Aravindan Vijayaraghavan,
  in Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (2010).
• Improved Approximation Algorithms for Label Cover Problems
  with MohammadTaghi Hajiaghayi and Howard Karloff,
  in Proceedings of the 17th Annual European Symposium on Algorithms (ESA) (2009).
• Every Permutation CSP of arity 3 is Approximation Resistant
  with Venkat Guruswami and Rajsekar Manokaran,
  in Proceedings of the 24th IEEE Conference on Computational Complexity (CCC) (2009).
• Integrality Gaps for Sherali-Adams Relaxations
  with Konstantin Makarychev and Yury Makarychev,
  in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (2009).
• MaxMin Allocation via Degree Lower-Bounded Arborescences
  with MohammadHossein Bateni and Venkat Guruswami,
  in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (2009).
• Efficiently matching sets of features with random histograms
  with Wei Dong, Zhe Wang and Kai Li,
  in Proceedings of the 16th International ACM Conference on Multimedia (2008).
• Modeling LSH for performance tuning
  with Wei Dong, Zhe Wang, William Josephson and Kai Li,
  in Proceedings of the 17th ACM Conference on Information and Knowledge Management (CIKM) (2008).
• Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces
  with Wei Dong and Kai Li,
  in Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (2008).
• Online multicast with egalitarian cost sharing
  with Howard Karloff, Claire Mathieu, Joseph (Seffi) Naor and Mike Saks,
  in Proceedings of the 20th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA) (2008).
• Local Global Tradeoffs in Metric Embeddings
  with Konstantin Makarychev and Yury Makarychev,
  in Proceedings of the 48th Annual IEEE Conference on Foundations of Computer Science (2007).
• On the Advantage over Random for Maximum Acyclic Subgraph
  with Konstantin Makarychev and Yury Makarychev,
  in Proceedings of the 48th Annual IEEE Conference on Foundations of Computer Science (2007).
• Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search
  with Qin Lv, William Josephson, Zhe Wang and Kai Li,
  in Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB) (2007).
• Sizing sketches: a rank-based analysis for similarity search
  with Zhe Wang, Wei Dong, William Josephson, Qin Lv, and Kai Li,
  ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (2007).
• Improved approximation for directed cut problems
  with Amit Agarwal and Noga Alon,
  in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (2007).
• Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems
  with Konstantin Makarychev and Yury Makarychev,
  in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (2007).
• A Divide and Conquer Algorithm for d-Dimensional Arrangement
  with Konstantin Makarychev and Yury Makarychev,
  in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (2007).
• 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).
  
• 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).
  

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).
• 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).
• 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

• Aggregating Inconsistent Information: Ranking and Clustering
  with Nir Ailon and Alantha Newman,
  in Proceedings of the 37th ACM Symposium on Theory of Computing (2005).
• Clustering with Qualitative Information,
  with V. Guruswami and A. Wirth,
  in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (2003).
  
• 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).
  
• 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.
  

Approximation Algorithms: Network Design

• On Non-uniform Multicommodity Buy-at-Bulk Network Design
  with Adriana Karagiozova,
  in Proceedings of the 37th ACM Symposium on Theory of Computing (2005).
• On the Advantage of Network Coding for Improving Network Throughput 
  with Amit Agarwal,
  in Proceedings of the IEEE Information Theory Workshop (2004).
• 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).
  
• 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.
• 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).
  
• 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).

Approximation Algorithms: TSP and Routing

• 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).
• The Finite Capacity Dial-A-Ride Problem,
  with B. Raghavachari,
  in Proceedings of the 39th Annual IEEE Conference on Foundations of Computer Science (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).
  

Other Approximation Algorithms

• A Robust Maximum Completion Time Measure for Scheduling
  with Samir Khuller,
  in Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (2006).
  
• Sampling Bounds for Stochastic Optimization
  with Chandra Chekuri and Martin Pal,
  in Proceedings of APPROX-RANDOM (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).
• 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).
  
• 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).
  
• Greedy Approximation Algorithms for Finding Dense Components in Graphs,
  in Proceedings of APPROX, (2000).
  
• 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).

Sketching, Streaming and Similarity Search

• 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).
• 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).
  
• 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).
  
• 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).
• 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).
• Similarity Estimation Techniques from Rounding Algorithms,
  in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, (2002).
  
• 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),
  

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 l₁
  with B. Brinkman, 
  in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (2003), best paper award.
  
• Dimension Reduction in the l₁ 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

• 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), to appear in special issue of JCSS for STOC 2000. 
  
• 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).
  
• 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 Journal of Algorithms, vol. 35(1), pp. 108-121, (2000), preliminary version 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 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).
  

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).