2009 | ||
---|---|---|
55 | EE | Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen: Approximate line nearest neighbor in high dimensions. SODA 2009: 293-301 |
54 | EE | Elad Hazan, Robert Krauthgamer: How hard is it to approximate the best Nash equilibrium? SODA 2009: 720-727 |
53 | EE | Alexandr Andoni, Piotr Indyk, Robert Krauthgamer: Overcoming the l1 non-embeddability barrier: algorithms for product metrics. SODA 2009: 865-874 |
52 | EE | Robert Krauthgamer, Joseph Naor, Roy Schwartz: Partitioning graphs into balanced components. SODA 2009: 942-949 |
51 | EE | Robert Krauthgamer, Yuval Rabani: Improved Lower Bounds for Embeddings intoL1$. SIAM J. Comput. 38(6): 2487-2498 (2009) |
2008 | ||
50 | EE | Alexandr Andoni, Robert Krauthgamer: The Smoothed Complexity of Edit Distance. ICALP (1) 2008: 357-369 |
49 | EE | Robert Krauthgamer, Aranyak Mehta, Vijayshankar Raman, Atri Rudra: Greedy List Intersection. ICDE 2008: 1033-1042 |
48 | EE | Alexandr Andoni, Piotr Indyk, Robert Krauthgamer: Earth mover distance over high-dimensional spaces. SODA 2008: 343-352 |
47 | EE | Robert Krauthgamer, Tim Roughgarden: Metric clustering via consistent labeling. SODA 2008: 809-818 |
46 | EE | Robert Krauthgamer: Minimum Bisection. Encyclopedia of Algorithms 2008 |
2007 | ||
45 | EE | Alexandr Andoni, Robert Krauthgamer: The Computational Hardness of Estimating Edit Distance [Extended Abstract]. FOCS 2007: 724-734 |
44 | EE | Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, Ravi Kumar: Estimating the sortedness of a data stream. SODA 2007: 318-327 |
43 | EE | Robert Krauthgamer: On triangulation of simple networks. SPAA 2007: 8-15 |
42 | EE | Robert Krauthgamer, Aranyak Mehta, Atri Rudra: Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations. WAOA 2007: 1-14 |
41 | EE | Alexandr Andoni, Piotr Indyk, Robert Krauthgamer: Earth Mover Distance over High-Dimensional Spaces. Electronic Colloquium on Computational Complexity (ECCC) 14(048): (2007) |
40 | EE | Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang: Integrality Ratio for Group Steiner Trees and Directed Steiner Trees. SIAM J. Comput. 36(5): 1494-1511 (2007) |
2006 | ||
39 | EE | Robert Krauthgamer, James R. Lee: Algorithms on negatively curved spaces. FOCS 2006: 119-132 |
38 | EE | Robert Krauthgamer, Yuval Rabani: Improved lower bounds for embeddings into L1. SODA 2006: 1010-1017 |
37 | EE | Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar: On the Hardness of Approximating Multicut and Sparsest-Cut. Computational Complexity 15(2): 94-114 (2006) |
36 | EE | Moses Charikar, Robert Krauthgamer: Embedding the Ulam metric into l1. Theory of Computing 2(1): 207-224 (2006) |
2005 | ||
35 | EE | Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar: On the Hardness of Approximating Multicut and Sparsest-Cut. IEEE Conference on Computational Complexity 2005: 144-153 |
34 | EE | Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor: Asymmetric k-center is log* n-hard to approximate. J. ACM 52(4): 538-551 (2005) |
33 | EE | Robert Krauthgamer, James R. Lee: The black-box complexity of nearest-neighbor search. Theor. Comput. Sci. 348(2-3): 262-276 (2005) |
2004 | ||
32 | EE | Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar: The Sketching Complexity of Pattern Matching. APPROX-RANDOM 2004: 261-272 |
31 | EE | Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor: Measured Descent: A New Embedding Method for Finite Metrics. FOCS 2004: 434-443 |
30 | EE | Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar: Approximating Edit Distance Efficiently. FOCS 2004: 550-559 |
29 | EE | Robert Krauthgamer, James R. Lee: The Black-Box Complexity of Nearest Neighbor Search. ICALP 2004: 858-869 |
28 | EE | Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, Éva Tardos: Approximate classification via earthmover metrics. SODA 2004: 1079-1087 |
27 | EE | Robert Krauthgamer, James R. Lee: Navigating nets: simple algorithms for proximity search. SODA 2004: 798-807 |
26 | EE | Kirsten Hildrum, Robert Krauthgamer, John Kubiatowicz: Object location in realistic networks. SPAA 2004: 25-35 |
25 | EE | Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor: Measured descent: A new embedding method for finite metrics CoRR abs/cs/0412008: (2004) |
24 | EE | Robert Krauthgamer, Nathan Linial, Avner Magen: Metric Embeddings--Beyond One-Dimensional Distortion. Discrete & Computational Geometry 31(3): 339-356 (2004) |
23 | EE | Guy Kortsarz, Robert Krauthgamer, James R. Lee: Hardness of Approximation for Vertex-Connectivity Network Design Problems. SIAM J. Comput. 33(3): 704-720 (2004) |
2003 | ||
22 | EE | Anupam Gupta, Robert Krauthgamer, James R. Lee: Bounded Geometries, Fractals, and Low-Distortion Embeddings. FOCS 2003: 534-543 |
21 | EE | Eran Halperin, Jeremy Buhler, Richard M. Karp, Robert Krauthgamer, Ben Westover: Detecting protein sequence conservation via metric embeddings. ISMB (Supplement of Bioinformatics) 2003: 122-129 |
20 | EE | Robert Krauthgamer, Ori Sasson: Property testing of data dimensionality. SODA 2003: 18-27 |
19 | EE | Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang: Integrality ratio for group Steiner trees and directed steiner trees. SODA 2003: 275-284 |
18 | EE | Robert Krauthgamer, James R. Lee: The intrinsic dimensionality of graphs. STOC 2003: 438-447 |
17 | EE | Eran Halperin, Robert Krauthgamer: Polylogarithmic inapproximability. STOC 2003: 585-594 |
16 | EE | Eyal Amir, Robert Krauthgamer, Satish Rao: Constant factor approximation of vertex-cuts in planar graphs. STOC 2003: 90-99 |
15 | EE | Uriel Feige, Robert Krauthgamer, Kobbi Nissim: On Cutting a Few Vertices from a Graph. Discrete Applied Mathematics 127(3): 643-649 (2003) |
14 | EE | Eran Halperin, Guy Kortsarz, Robert Krauthgamer: Tight lower bounds for the asymmetric k-center problem Electronic Colloquium on Computational Complexity (ECCC) 10(035): (2003) |
13 | EE | Uriel Feige, Robert Krauthgamer: The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set. SIAM J. Comput. 32(2): 345-370 (2003) |
2002 | ||
12 | EE | Guy Kortsarz, Robert Krauthgamer, James R. Lee: Hardness of Approximation for Vertex-Connectivity Network-Design Problems. APPROX 2002: 185-199 |
11 | EE | Uriel Feige, Robert Krauthgamer: A Polylogarithmic Approximation of the Minimum Bisection. SIAM J. Comput. 31(4): 1090-1118 (2002) |
2001 | ||
10 | EE | Guy Kortsarz, Robert Krauthgamer: On approximating the achromatic number. SODA 2001: 309-318 |
9 | EE | T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber, Maxim Sviridenko: Online server allocation in a server farm via benefit task systems. STOC 2001: 540-549 |
8 | EE | Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim: Private approximation of NP-hard functions. STOC 2001: 550-559 |
7 | EE | Guy Kortsarz, Robert Krauthgamer: On Approximating the Achromatic Number. SIAM J. Discrete Math. 14(3): 408-422 (2001) |
2000 | ||
6 | Uriel Feige, Robert Krauthgamer: A polylogarithmic approximation of the minimum bisection. FOCS 2000: 105-115 | |
5 | EE | Andrei Z. Broder, Robert Krauthgamer, Michael Mitzenmacher: Improved classification via connectivity information. SODA 2000: 576-585 |
4 | EE | Uriel Feige, Robert Krauthgamer, Kobbi Nissim: Approximating the minimum bisection size (extended abstract). STOC 2000: 530-536 |
3 | EE | Uriel Feige, Robert Krauthgamer: Networks on Which Hot-Potato Routing Does Not Livelock. Distributed Computing 13(1): 53-58 (2000) |
2 | Uriel Feige, Robert Krauthgamer: Finding and certifying a large hidden clique in a semirandom graph. Random Struct. Algorithms 16(2): 195-208 (2000) | |
1997 | ||
1 | EE | Uriel Feige, Robert Krauthgamer: Stereoscopic families of permutations, and their applications. ISTCS 1997: 85-95 |