 | 2010 |
|---|
| 99 |       | Moses Charikar,
Mohammad Taghi Hajiaghayi,
Howard J. Karloff,
Satish Rao:
l22 Spreading Metrics for Vertex Ordering Problems.
Algorithmica 56(4): 577-604 (2010) |
| 98 | | Aditya Bhaskara,
Moses Charikar,
Eden Chlamtac,
Uriel Feige,
Aravindan Vijayaraghavan:
Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph
CoRR abs/1001.2891: (2010) |
| 97 | | Prahladh Harsha,
Moses Charikar,
Matthew Andrews,
Sanjeev Arora,
Subhash Khot,
Dana Moshkovitz,
Lisa Zhang,
Ashkan Aazami,
Dev Desai,
Igor Gorodezky,
Geetha Jagannathan,
Alexander S. Kulikov,
Darakhshan J. Mir,
Alantha Newman,
Aleksandar Nikolov,
David Pritchard,
Gwen Spencer:
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
CoRR abs/1002.3864: (2010) |
| 2009 |
|---|
| 96 | | Moses Charikar,
MohammadTaghi Hajiaghayi,
Howard J. Karloff:
Improved Approximation Algorithms for Label Cover Problems.
ESA 2009: 23-34 |
| 95 | | Moses Charikar,
Venkatesan Guruswami,
Rajsekar Manokaran:
Every Permutation CSP of arity 3 is Approximation Resistant.
IEEE Conference on Computational Complexity 2009: 62-73 |
| 94 | | Moses Charikar,
Konstantin Makarychev,
Yury Makarychev:
Integrality gaps for Sherali-Adams relaxations.
STOC 2009: 283-292 |
| 93 | | MohammadHossein Bateni,
Moses Charikar,
Venkatesan Guruswami:
MaxMin allocation via degree lower-bounded arborescences.
STOC 2009: 543-552 |
| 92 | | Moses Charikar,
Konstantin Makarychev,
Yury Makarychev:
Near-optimal algorithms for maximum constraint satisfaction problems.
ACM Transactions on Algorithms 5(3): (2009) |
| 2008 |
|---|
| 91 | | Wei Dong,
Zhe Wang,
Moses Charikar,
Kai Li:
Efficiently matching sets of features with random histograms.
ACM Multimedia 2008: 179-188 |
| 90 | | Wei Dong,
Zhe Wang,
William Josephson,
Moses Charikar,
Kai Li:
Modeling LSH for performance tuning.
CIKM 2008: 669-678 |
| 89 | | Wei Dong,
Moses Charikar,
Kai Li:
Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces.
SIGIR 2008: 123-130 |
| 88 | | Moses Charikar,
Howard J. Karloff,
Claire Mathieu,
Joseph Naor,
Michael E. Saks:
Online multicast with egalitarian cost sharing.
SPAA 2008: 70-76 |
| 87 | | Nir Ailon,
Moses Charikar,
Alantha Newman:
Aggregating inconsistent information: Ranking and clustering.
J. ACM 55(5): (2008) |
| 2007 |
|---|
| 86 |  | Moses Charikar,
Klaus Jansen,
Omer Reingold,
José D. P. Rolim:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings
Springer 2007 |
| 85 | | Zhe Wang,
William K. Josephson,
Qin Lv,
Moses Charikar,
Kai Li:
Filtering Image Spam with Near-Duplicate Detection.
CEAS 2007 |
| 84 | | Moses Charikar,
Konstantin Makarychev,
Yury Makarychev:
On the Advantage over Random for Maximum Acyclic Subgraph.
FOCS 2007: 625-633 |
| 83 | | Moses Charikar,
Konstantin Makarychev,
Yury Makarychev:
Local Global Tradeoffs in Metric Embeddings.
FOCS 2007: 713-723 |
| 82 | | Zhe Wang,
Wei Dong,
William Josephson,
Qin Lv,
Moses Charikar,
Kai Li:
Sizing sketches: a rank-based analysis for similarity search.
SIGMETRICS 2007: 157-168 |
| 81 | | Moses Charikar,
Konstantin Makarychev,
Yury Makarychev:
A divide and conquer algorithm for d-dimensional arrangement.
SODA 2007: 541-546 |
| 80 | | Moses Charikar,
Konstantin Makarychev,
Yury Makarychev:
Near-optimal algorithms for maximum constraint satisfaction problems.
SODA 2007: 62-68 |
| 79 | | Amit Agarwal,
Noga Alon,
Moses Charikar:
Improved approximation for directed cut problems.
STOC 2007: 671-680 |
| 78 | | Qin Lv,
William Josephson,
Zhe Wang,
Moses Charikar,
Kai Li:
Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search .
VLDB 2007: 950-961 |
| 77 | | Moses Charikar,
Konstantin Makarychev,
Yury Makarychev:
On the Advantage over Random for Maximum Acyclic Subgraph.
Electronic Colloquium on Computational Complexity (ECCC) 14(104): (2007) |
| 76 | | Moses Charikar,
Konstantin Makarychev,
Yury Makarychev:
Local Global Tradeoffs in Metric Embeddings.
Electronic Colloquium on Computational Complexity (ECCC) 14(108): (2007) |
| 2006 |
|---|
| 75 | | Qin Lv,
William Josephson,
Zhe Wang,
Moses Charikar,
Kai Li:
Ferret: a toolkit for content-based similarity search of feature-rich data.
EuroSys 2006: 317-330 |
| 74 | | Qin Lv,
William Josephson,
Zhe Wang,
Moses Charikar,
Kai Li:
Efficient filtering with sketches in the ferret toolkit.
Multimedia Information Retrieval 2006: 279-288 |
| 73 | | Moses Charikar,
Mohammad Taghi Hajiaghayi,
Howard J. Karloff,
Satish Rao:
l22 spreading metrics for vertex ordering problems.
SODA 2006: 1018-1027 |
| 72 | | Moses Charikar,
Samir Khuller:
A robust maximum completion time measure for scheduling.
SODA 2006: 324-333 |
| 71 | | Moses Charikar,
Konstantin Makarychev,
Yury Makarychev:
Directed metrics and directed graph partitioning problems.
SODA 2006: 51-60 |
| 70 | | Moses Charikar,
Konstantin Makarychev,
Yury Makarychev:
Near-optimal algorithms for unique games.
STOC 2006: 205-214 |
| 69 | | Moses Charikar,
Konstantin Makarychev,
Yury Makarychev:
Approximation Algorithm for the Max k-CSP Problem.
Electronic Colloquium on Computational Complexity (ECCC) 13(063): (2006) |
| 68 | | Moses Charikar,
Konstantin Makarychev,
Yury Makarychev:
Note on MAX 2SAT.
Electronic Colloquium on Computational Complexity (ECCC) 13(064): (2006) |
| 67 | | Moses Charikar:
Guest editor's foreword.
J. Comput. Syst. Sci. 72(5): 785 (2006) |
| 66 | | Moses Charikar,
Michel X. Goemans,
Howard J. Karloff:
On the Integrality Ratio for the Asymmetric Traveling Salesman Problem.
Math. Oper. Res. 31(2): 245-252 (2006) |
| 65 | | Moses Charikar,
Robert Krauthgamer:
Embedding the Ulam metric into l1.
Theory of Computing 2(1): 207-224 (2006) |
| 2005 |
|---|
| 64 | | Moses Charikar,
Chandra Chekuri,
Martin Pál:
Sampling Bounds for Stochastic Optimization.
APPROX-RANDOM 2005: 257-269 |
| 63 | | Nir Ailon,
Moses Charikar:
Fitting tree metrics: Hierarchical clustering and Phylogeny.
FOCS 2005: 73-82 |
| 62 | | Moses Charikar,
Adriana Karagiozova:
A tight threshold for metric Ramsey phenomena.
SODA 2005: 129-136 |
| 61 | | Nikhil Bansal,
Moses Charikar,
Sanjeev Khanna,
Joseph Naor:
Approximating the average response time in broadcast scheduling.
SODA 2005: 215-221 |
| 60 | | Moses Charikar,
Adriana Karagiozova:
On non-uniform multicommodity buy-at-bulk network design.
STOC 2005: 176-182 |
| 59 | | Amit Agarwal,
Moses Charikar,
Konstantin Makarychev,
Yury Makarychev:
O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems.
STOC 2005: 573-581 |
| 58 | | Nir Ailon,
Moses Charikar,
Alantha Newman:
Aggregating inconsistent information: ranking and clustering.
STOC 2005: 684-693 |
| 57 | | Moses Charikar,
Eric Lehman,
Ding Liu,
Rina Panigrahy,
Manoj Prabhakaran,
Amit Sahai,
Abhi Shelat:
The smallest grammar problem.
IEEE Transactions on Information Theory 51(7): 2554-2576 (2005) |
| 56 | | Bo Brinkman,
Moses Charikar:
On the impossibility of dimension reduction in l1.
J. ACM 52(5): 766-788 (2005) |
| 55 | | Moses Charikar,
Venkatesan Guruswami,
Anthony Wirth:
Clustering with qualitative information.
J. Comput. Syst. Sci. 71(3): 360-383 (2005) |
| 54 | | Moses Charikar,
Sudipto Guha:
Improved Combinatorial Algorithms for Facility Location Problems.
SIAM J. Comput. 34(4): 803-824 (2005) |
| 2004 |
|---|
| 53 | | Qin Lv,
Moses Charikar,
Kai Li:
Image similarity search with compact data structures.
CIKM 2004: 208-217 |
| 52 | | Moses Charikar,
Michel X. Goemans,
Howard J. Karloff:
On the Integrality Ratio for Asymmetric TSP.
FOCS 2004: 101-107 |
| 51 | | Moses Charikar,
Anthony Wirth:
Maximizing Quadratic Programs: Extending Grothendieck's Inequality.
FOCS 2004: 54-60 |
| 50 | | Moses Charikar,
Joseph Naor,
Baruch Schieber:
Resource optimization in QoS multicast routing of real-time multimedia.
IEEE/ACM Trans. Netw. 12(2): 340-348 (2004) |
| 49 | | Moses Charikar,
Rina Panigrahy:
Clustering to minimize the sum of cluster diameters.
J. Comput. Syst. Sci. 68(2): 417-441 (2004) |
| 48 | | Moses Charikar,
Chandra Chekuri,
Tomás Feder,
Rajeev Motwani:
Incremental Clustering and Dynamic Information Retrieval.
SIAM J. Comput. 33(6): 1417-1440 (2004) |
| 47 | | Moses Charikar,
Jon M. Kleinberg,
Ravi Kumar,
Sridhar Rajagopalan,
Amit Sahai,
Andrew Tomkins:
Minimizing Wirelength in Zero and Bounded Skew Clock Trees.
SIAM J. Discrete Math. 17(4): 582-595 (2004) |
| 46 | | Moses Charikar,
Kevin Chen,
Martin Farach-Colton:
Finding frequent items in data streams.
Theor. Comput. Sci. 312(1): 3-15 (2004) |
| 2003 |
|---|
| 45 | | Bo Brinkman,
Moses Charikar:
On the Impossibility of Dimension Reduction in l1.
FOCS 2003: 514-523 |
| 44 | | Moses Charikar,
Venkatesan Guruswami,
Anthony Wirth:
Clustering with Qualitative Information.
FOCS 2003: 524-533 |
| 43 | | Moses Charikar,
Liadan O'Callaghan,
Rina Panigrahy:
Better streaming algorithms for clustering problems.
STOC 2003: 30-39 |
| 42 | | Andrei Z. Broder,
Moses Charikar,
Michael Mitzenmacher:
A derandomization using min-wise independent permutations.
J. Discrete Algorithms 1(1): 11-20 (2003) |
| 2002 |
|---|
| 41 | | Moses Charikar,
Amit Sahai:
Dimension Reduction in the \ell _1 Norm.
FOCS 2002: 551-560 |
| 40 | | Moses Charikar,
Piotr Indyk,
Rina Panigrahy:
New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems.
ICALP 2002: 451-462 |
| 39 | | Moses Charikar,
Kevin Chen,
Martin Farach-Colton:
Finding Frequent Items in Data Streams.
ICALP 2002: 693-703 |
| 38 | | Moses Charikar:
On semidefinite programming relaxations for graph coloring and vertex cover.
SODA 2002: 616-620 |
| 37 | | Moses Charikar:
Similarity estimation techniques from rounding algorithms.
STOC 2002: 380-388 |
| 36 | | Moses Charikar,
Eric Lehman,
Ding Liu,
Rina Panigrahy,
Manoj Prabhakaran,
April Rasala,
Amit Sahai,
Abhi Shelat:
Approximating the smallest grammar: Kolmogorov complexity in natural models.
STOC 2002: 792-801 |
| 35 | | Moses Charikar,
Ronald Fagin,
Venkatesan Guruswami,
Jon M. Kleinberg,
Prabhakar Raghavan,
Amit Sahai:
Query Strategies for Priced Information.
J. Comput. Syst. Sci. 64(4): 785-819 (2002) |
| 34 | | Moses Charikar,
Sudipto Guha,
Éva Tardos,
David B. Shmoys:
A Constant-Factor Approximation Algorithm for the k-Median Problem.
J. Comput. Syst. Sci. 65(1): 129-149 (2002) |
| 2001 |
|---|
| 33 | | Moses Charikar,
Samir Khuller,
David M. Mount,
Giri Narasimhan:
Algorithms for facility location problems with outliers.
SODA 2001: 642-651 |
| 32 | | Moses Charikar,
Rina Panigrahy:
Clustering to minimize the sum of cluster diameters.
STOC 2001: 1-10 |
| 31 | | Yair Bartal,
Moses Charikar,
Danny Raz:
Approximating min-sum k-clustering in metric spaces.
STOC 2001: 11-20 |
| 30 | | Susanne Albers,
Moses Charikar,
Michael Mitzenmacher:
Delayed Information and Action in On-Line Algorithms.
Inf. Comput. 170(2): 135-152 (2001) |
| 29 | | Moses Charikar,
Samir Khuller,
Balaji Raghavachari:
Algorithms for Capacitated Vehicle Routing.
SIAM J. Comput. 31(3): 665-682 (2001) |
| 28 | | Yair Bartal,
Moses Charikar,
Piotr Indyk:
On page migration and other relaxed task systems.
Theor. Comput. Sci. 268(1): 43-66 (2001) |
| 2000 |
|---|
| 27 | | Moses Charikar:
Greedy approximation algorithms for finding dense components in a graph.
APPROX 2000: 84-95 |
| 26 | | Moses Charikar,
Venkatesan Guruswami,
Ravi Kumar,
Sridhar Rajagopalan,
Amit Sahai:
Combinatorial feature selection problems.
FOCS 2000: 631-640 |
| 25 | | Rohit Negi,
Moses Charikar,
John M. Cioffi:
Minimum Outage Transmission over Fading Channels with Delay Constraint.
ICC (1) 2000: 282-286 |
| 24 | | Moses Charikar,
Joseph Naor,
Baruch Schieber:
Resource Optimization in QoS Multicast Routing of Real-Time Multimedia.
INFOCOM 2000: 1518-1527 |
| 23 | | Moses Charikar,
Surajit Chaudhuri,
Rajeev Motwani,
Vivek R. Narasayya:
Towards Estimation Error Guarantees for Distinct Values.
PODS 2000: 268-279 |
| 22 | | Moses Charikar,
Ronald Fagin,
Venkatesan Guruswami,
Jon M. Kleinberg,
Prabhakar Raghavan,
Amit Sahai:
Query strategies for priced information (extended abstract).
STOC 2000: 582-591 |
| 21 | | Piotr Berman,
Moses Charikar,
Marek Karpinski:
On-Line Load Balancing for Related Machines
Electronic Colloquium on Computational Complexity (ECCC) 7(1): (2000) |
| 20 | | Piotr Berman,
Moses Charikar,
Marek Karpinski:
On-Line Load Balancing for Related Machines.
J. Algorithms 35(1): 108-121 (2000) |
| 19 | | Andrei Z. Broder,
Moses Charikar,
Alan M. Frieze,
Michael Mitzenmacher:
Min-Wise Independent Permutations.
J. Comput. Syst. Sci. 60(3): 630-659 (2000) |
| 1999 |
|---|
| 18 | | Moses Charikar,
Sudipto Guha:
Improved Combinatorial Algorithms for the Facility Location and k-Median Problems.
FOCS 1999: 378-388 |
| 17 | | Moses Charikar,
Jon M. Kleinberg,
Ravi Kumar,
Sridhar Rajagopalan,
Amit Sahai,
Andrew Tomkins:
Minimizing Wirelength in Zero and Bounded Skew Clock Trees.
SODA 1999: 177-184 |
| 16 | | Moses Charikar,
Sudipto Guha,
Éva Tardos,
David B. Shmoys:
A Constant-Factor Approximation Algorithm for the k-Median Problem (Extended Abstract).
STOC 1999: 1-10 |
| 15 | | Moses Charikar,
Ravi Kumar,
Prabhakar Raghavan,
Sridhar Rajagopalan,
Andrew Tomkins:
On targeting Markov segments.
STOC 1999: 99-108 |
| 14 | | Moses Charikar,
Chandra Chekuri,
To-Yat Cheung,
Zuo Dai,
Ashish Goel,
Sudipto Guha,
Ming Li:
Approximation Algorithms for Directed Steiner Problems.
J. Algorithms 33(1): 73-91 (1999) |
| 1998 |
|---|
| 13 | | Moses Charikar,
Chandra Chekuri,
Ashish Goel,
Sudipto Guha,
Serge A. Plotkin:
Approximating a Finite Metric by a Small Number of Tree Metrics.
FOCS 1998: 379-388 |
| 12 | | Moses Charikar,
Balaji Raghavachari:
The Finite Capacity Dial-A-Ride Problem.
FOCS 1998: 458-467 |
| 11 | | Susanne Albers,
Moses Charikar,
Michael Mitzenmacher:
Delayed Information and Action in On-line Algorithms.
FOCS 1998: 71-81 |
| 10 | | Andrei Z. Broder,
Moses Charikar,
Michael Mitzenmacher:
A Derandomization Using Min-Wise Independent Permutations.
RANDOM 1998: 15-24 |
| 9 | | Moses Charikar,
Chandra Chekuri,
To-Yat Cheung,
Zuo Dai,
Ashish Goel,
Sudipto Guha,
Ming Li:
Approximation Algorithms for Directed Steiner Problems.
SODA 1998: 192-200 |
| 8 | | Moses Charikar,
Dan Halperin,
Rajeev Motwani:
The Dynamic Servers Problem.
SODA 1998: 410-419 |
| 7 | | Moses Charikar,
Chandra Chekuri,
Ashish Goel,
Sudipto Guha:
Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k-Median.
STOC 1998: 114-123 |
| 6 | | Andrei Z. Broder,
Moses Charikar,
Alan M. Frieze,
Michael Mitzenmacher:
Min-Wise Independent Permutations (Extended Abstract).
STOC 1998: 327-336 |
| 5 | | Moses Charikar,
Samir Khuller,
Balaji Raghavachari:
Algorithms for Capacitated Vehicle Routing.
STOC 1998: 349-358 |
| 1997 |
|---|
| 4 | | Yair Bartal,
Moses Charikar,
Piotr Indyk:
On Page Migration and Other Related Task Systems.
SODA 1997: 43-52 |
| 3 | | Moses Charikar,
Chandra Chekuri,
Tomás Feder,
Rajeev Motwani:
Incremental Clustering and Dynamic Information Retrieval.
STOC 1997: 626-635 |
| 2 | | Moses Charikar,
Rajeev Motwani,
Prabhakar Raghavan,
Craig Silverstein:
Constrained TSP and Low-Power Computing.
WADS 1997: 104-115 |
| 1 | | Piotr Berman,
Moses Charikar,
Marek Karpinski:
On-line Load Balancing for Related Machines.
WADS 1997: 116-125 |
