Yevgeniy Dodis
- 1.I. Althofer, G. Des, D. Dobkin, D. Joseph and J. Scares. On sparse spanners of weighted graphs. In Discrete and Computational Geometry, 9:81-100, 1993. Google Scholar
Digital Library
- 2.E. Amaldi and V. Kann. The complexity and approximability of finding maximum feasible subsystems of Iinear relations. Theoretical Computer Science, 147(1-2):181- 210, 1995. Google ScholarDigital Library
- 3.S. Arora, L. BabaJ, J. Stern and Z. Sweedyk. The hardhess of approximate optima in lattices, codes, and systems of linear equations. Journal of Computer and System Sciences, 54(2):317-331, /997. Google ScholarDigital Library
- 4.S. Arora and M. Sudan. Improved low degree testing and its applications. In Proc. of the ~gth A CM Symposium on Theory of Computing, pp. 485-495, 1997. Google ScholarDigital Library
- 5.B. Awerbuch, A. Baratz, and D. Peleg. Coat-sensitive analysis of communication protocols. In Proc. 9th Syrnp. on Principles of Dist. Comput., pp. 177-187, 1990. Google ScholarDigital Library
- 6.M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha and M. Li. Approximation algorithms for directed steiner problems. In Proc. 9th A CM-SIAM Symposium on Discrete Algorithms, pp. I92-200, 1998. Google ScholarDigital Library
- 7.E. Cohen. Fast Algorithms for constructing t-spanners and paths with stretch t (extended abstract). In Proc. 34th Syrup. on Foundation of Computer Science, pp. 648-658, 1993.Google Scholar
- 8.U. Feige. A theshold of In n for approximating set-cover. In Proc. 26th A CM Syrup. on the Theory of Computing, pp. 314-318, 1996. Google ScholarDigital Library
- 9.D. Hochbaum (Ed.). Approximation Algorithms for NP- Hard Problems. PWS Publishing Company, 1997. Google ScholarDigital Library
- 10.S. Khanna, M. Sudan and L. Trevisan. Constraint satisfaction: The approximability of minimization problems. In Proc. I~th Computational Complezity Conf., pp. 282- 296, 1997. Google ScholarDigital Library
- 11.S. Khuller, B. Raghavachari, and N. Young. Balancing minimum spanning and shortest path trees. In Proc. 4th Syrup. on Discrete Algorithms, pp. 243-250, 1993. Google ScholarDigital Library
- 12.G. Kortsarz. On the hardness of approximating spanners. In the First International Workshop on Approximation Algorithms for Combinatorial Optimization, 1998. Google ScholarDigital Library
- 13.G. Kortsarz and D. Peleg. Generating sparse 2-spanners. In LNC$, 621:73-83, 1992. Google ScholarDigital Library
- 14.G. Kortsarz and D. Peleg. Generating low-degree 2- spanners. In Proc. 5th A CM-SIAM Syrup. on Discrete Algorithms, pp. 556-563, 1994. Google ScholarDigital Library
- 15.G. Kortsarz and D. Peleg. Approximating shallow-light trees. In Proc. 8th A CM-SIAM Syrup. on Discrete Algorithms, pp. 103-110, 1997. Google ScholarDigital Library
- 16.E. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976.Google Scholar
- 17.C. Li, S. McCormick, and D. Simchi-Levi. On the Minimum-cardinality-bounded-diameter and Boundedcardinality-minimum-diameter Edge Addition Problems. In Operation Research Letters, 11:303-308, 1992.Google ScholarDigital Library
- 18.M. Marathe, R. Ravi, R. Sundaram, S. Ravi, D. Rosenkrantz, and H. Hunt III. Bicriteria network design problems. J. of Algorithms, 28(1):142-171, 1998. Google ScholarDigital Library
- 19.R. Ravi, M. Marathe, S. Ravi, D. Rosenkrantz, and H. Hunt III. Many birds with one stone: Multi-objective approximation algorithms. In Proc. of the 25th A CM Syrup. on the Theory of Computing, pp. 438-447, 1993. Google ScholarDigital Library
- 20.R. Ravi, R. Sundaram, M. Marathe, D. Rosenkrantz, and S. Ravi. Spanning trees short or small. In Proc. 5th A CM- SIAM Syrup. on Discrete Algorithms, pp. 546-555, 1994. Google ScholarDigital Library
- 21.R. Raz and S. Safra. A sub-constant error-probability Iow-degree test, and a sub-constant error-probability PCP characterization of NP. In Procexxtings of the 29th A CM Syrup. on Theory of Computing, pp. 475-484, 1997. Google ScholarDigital Library
Index Terms
- Design networks with bounded pairwise distance
Recommendations
Sparse Sourcewise and Pairwise Distance Preservers
We introduce and study the notions of pairwise and sourcewise preservers. Given an undirected N-vertex graph G = (V,E) and a set P of pairs of vertices, let G' = (V,H), H \subseteq E, be called a pairwise preserver of G with respect to P if for every ...
Sequence similarity measures based on bounded hamming distance
A growing number of measures of sequence similarity are being based on some underlying notion of relative compressibility. Within this paradigm, similar sequences are expected to share a large number of common substrings, or subsequences, or more ...
Error amplification for pairwise spanner lower bounds
SODA '16: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithmsA pairwise spanner of a graph G = (V, E) and a "pair set" P ⊆ V × V is a subgraph H that preserves all pairwise distances in P, up to some additive error term +β. When β = 0 the object is called a pairwise distance preserver.
A large and growing body of ...
Comments