caa a22 4500 467909741 CHVBK 20180406152846.0 cr unu---uuuuu 170328e20060301xx s 000 0 eng 10.1007/s00037-005-0200-3 doi (NATIONALLICENCE)springer-10.1007/s00037-005-0200-3 On the complexity of approximating tsp with neighborhoods and related problems [Elektronische Daten] [Shmuel Safra, Oded Schwartz] Abstract.: We prove that various geometric covering problems related to the Traveling Salesman Problem cannot be efficiently approximated to within any constant factor unless P = NP. This includes the Group-Traveling Salesman Problem (TSP with Neighborhoods) in the Euclidean plane, the Group-Steiner-Tree in the Euclidean plane and the Minimum Watchman Tour and Minimum Watchman Path in 3-D. Some inapproximability factors are also shown for special cases of the above problems, where the size of the sets is bounded. Group-TSP and Group-Steiner-Tree where each neighborhood is connected are also considered. It is shown that approximating these variants to within any constant factor smaller than 2 is NP-hard. For the Group-Traveling Salesman and Group-Steiner-Tree Problems in dimension d, we show an inapproximability factor of O(log(d−1)/dn) under a plausible conjecture regarding the hardness of Hyper-Graph Vertex-Cover. Birkhäuser Verlag, Basel, 2005 NP-optimization problems nationallicence approximation nationallicence hardness of approximation nationallicence inapproximability nationallicence TSP nationallicence TSP with neighborhoods nationallicence 68Q17 nationallicence 68Q25 nationallicence Safra Shmuel School of Computer Science, Tel-Aviv University, Tel-Aviv, 69978, Israel aut Schwartz Oded School of Computer Science, Tel-Aviv University, 69978, Tel-Aviv, Israel aut computational complexity Birkhäuser-Verlag; www.birkhauser.ch 14/4(2006-03-01), 281-307 1016-3328 14:4<281 2006 14 37 https://doi.org/10.1007/s00037-005-0200-3 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00037-005-0200-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Safra Shmuel School of Computer Science, Tel-Aviv University, Tel-Aviv, 69978, Israel aut NATIONALLICENCE 700 1- Schwartz Oded School of Computer Science, Tel-Aviv University, 69978, Tel-Aviv, Israel aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag; www.birkhauser.ch 14/4(2006-03-01), 281-307 1016-3328 14:4<281 2006 14 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer