Error Correction
- PDF / 207,021 Bytes
- 1 Pages / 547.087 x 737.008 pts Page_size
- 68 Downloads / 245 Views
7. Fredman, M., Tarjan, R.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596– 615 (1987) 8. Han, Y.: Improved fast integer sorting in linear space. Inf. Comput. 170(8), 81–94 (2001). Announced at STACS’00 and SODA’01 9. Han, Y.: Deterministic sorting in O(n log log n) time and linear space. J. Algorithms 50(1), 96–105 (2004). Announced at STOC’02 p 10. Han, Y., Thorup, M.: Integer sorting in O(n log log n) expected time and linear space. In: Proc. 43rd FOCS, 2002, pp. 135–144 11. Mendelson, R., Tarjan, R., Thorup, M., Zwick, U.: Melding priority queues. ACM TALG 2(4), 535–556 (2006). Announced at SODA’04 12. Pagh, A., Pagh, R., Thorup, M.: On adaptive integer sorting. In: Proc. 12th ESA, 2004, pp. 556–579 13. Thorup, M.: Faster deterministic sorting and priority queues in linear space. In: Proc. 9th SODA, 1998, pp. 550–555 14. Thorup, M.: On RAM priority queues. SIAM J. Comput. 30(1), 86–109 (2000). Announced at SODA’96 15. Thorup, M.: Equivalence between priority queues and sorting. In: Proc. 43rd FOCS, 2002, pp. 125–134 16. Thorup, M.: Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations. J. Algorithms 42(2), 205–230 (2002). Announced at SODA’97 17. Thorup, M.: Integer priority queues with decrease key in constant time and the single source shortest paths problem. J. Comput. Syst. Sci. (special issue on STOC’03) 69(3), 330–353 (2004) 18. Vollmer, H.: Introduction to circuit complexity: a uniform approach. Springer, New York (1999) 19. Willard, D.: Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree. SIAM J. Comput. 29(3), 1030–1049 (2000). Announced at SODA’92
Error-Control Codes, Reed–Muller Code Learning Heavy Fourier Coefficients of Boolean Functions
Error Correction Decoding Reed–Solomon Codes List Decoding near Capacity: Folded RS Codes LP Decoding
Euclidean Graphs and Trees Minimum Geometric Spanning Trees Minimum k-Connected Geometric Networks
E
Euclidean Traveling Salesperson Problem 1998; Arora ARTUR CZUMAJ DIMAP and Computer Science, University of Warwick, Coventry, UK
Keywords and Synonyms Euclidean TSP; Geometric TSP; Geometric traveling salesman problem
Problem Definition This entry considers geometric optimization N P -hard problems like the Euclidean Traveling Salesperson problem and the Euclidean Steiner Tree problem. These problems are geometric variants of standard graph optimization problems, and the restriction of the input instances to geometric or Euclidean case arise in numerous applications (see [1,2]). The main focus of this chapter is the Euclidean Traveling Salesperson problem.
Notation The Euclidean Traveling Salesperson Problem (TSP): For a given set S of n points in the Euclidean space Rd , find a path of minimum length that visits each point exactly once. The cost ı(x; y) of an edge connecting a pair of points x; y 2 Rd is equal to the Euclidean distance between q Pd 2 points x and y. That is, ı(x; y) = i=1
Data Loading...
