The Traveling Salesman Problem for Lines, Balls, and Planes
ACM Transactions on Algorithms · 15.06.2016 · 12 (3) · 1-29
DOI: 10.1145/2850418 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 25.04.2016. Verfasst von Adrian Dumitrescu und 1 weiteren Autor:innen. Die Arbeit wurde bisher 18-mal zitiert (Crossref) und nennt 51 Literaturangaben. Gefördert von: NSF, NSERC.
Abstract (Originalsprache)
We revisit the traveling salesman problem with neighborhoods (TSPN) and propose several new approximation algorithms. These constitute either first approximations (for hyperplanes, lines, and balls in R d , for d ⩾ 3) or improvements over previous approximations achievable in comparable times (for unit disks in the plane). (I) Given a set of n hyperplanes in R d , a traveling salesman problem (TSP) tour whose length is at most O (1) times the optimal can be computed in O ( n ) time when d is constant. (II) Given a set of n lines in R d , a TSP tour whose length is at most O (log 3 n ) times the optimal can be computed in polynomial time for all d . (III) Given a set of n unit balls in R d , a TSP tour whose length is at most O (1) times the optimal can be computed in polynomial time when d is constant.
Förderung
- NSF
- NSERC
Zitieren
APA
Dumitrescu, A., & Tóth, C. D. (2016). The Traveling Salesman Problem for Lines, Balls, and Planes. ACM Transactions on Algorithms, 12(3), 1-29. https://doi.org/10.1145/2850418
Vancouver
Dumitrescu A, Tóth CD. The Traveling Salesman Problem for Lines, Balls, and Planes. ACM Transactions on Algorithms. 2016;12(3):1-29. doi:10.1145/2850418
BibTeX
@article{Dumitrescu2016,
author = {Dumitrescu, Adrian and Tóth, Csaba D.},
title = {The Traveling Salesman Problem for Lines, Balls, and Planes},
journal = {ACM Transactions on Algorithms},
year = {2016},
volume = {12},
number = {3},
pages = {1--29},
doi = {10.1145/2850418}
}
EUVIMED