I den euklideiska TSP med stadsdelar (TSPN) får vi en samling av n regioner (grannar) och vi söker en kortaste tur som besöker varje region. Som en generalisering av den klassiska Euclidean TSP, är TSPN också NP-hård. I detta dokument presenterar vi nya approximativa resultat för TSPN, inklusive (1) en approximationsalgoritm med konstant faktor för fall av godtyckliga anslutna bostadsområden med jämförbara diametrar; och (2) en PTAS för det viktiga specialfallet av separata diskområden (eller nästan åtskilda diskenheter). Våra metoder ger också förbättrade approximationskvoter för olika speciella klasser av bostadsområden, som tidigare har studerats. Vidare ger vi en linjär tid O(1)-tillnärmning algoritm för fallet med stadsdelar som är (oändliga) raka linjer. En säljare vill träffa en uppsättning av n potentiella köpare. Varje köpare anger en ansluten region i planet, hans grannskap, inom vilken han är villig att träffa försäljaren. Till exempel kan kvarteren vara diskar centrerade på köparnas platser, och radien på varje disk anger det maximala avståndet en köpare är villig att resa till mötesplatsen. Försäljaren vill hitta en rundtur av kortaste längd som besöker alla köpares kvarter och slutligen återvänder till sin ursprungliga utgångspunkt. En variant av problemet, som vi kommer att ta upp i detta dokument, är den där ingen utgångspunkt anges, och bara en rundtur i kvarteren finns att hitta. Detta problem, som är känt som TSP med stadsdelar (TSPN), är en generalisering av den klassiska Euclidean Traveling Salesman Problem (TSP), där regionerna, eller "grannar", är enstaka punkter, och följaktligen är NP-hård [9, 21]. TSP har en lång och rik historia av forskning inom kombinatorisk optimering. Den har studerats ingående i många former, däribland geometriska fall; se [4, 13, 14, 20, 24]. Problemet är känt för att vara NP-hård, även för punkter i Euclidean planet [9, 21]. Det har * Detta arbete gjordes medan författaren var en besökande fakultetsmedlem vid Stony Brook University. † Delvis understödd av bidrag från HRT Laboratories, NASA Ames, National Science Foundation (CR-9732220), Northrop-Grumman Corporation, Sandia National Labs och Sun Microsystems. Arkin och Hassin [1] var de första som studerade approximationsalgoritmer för det geometriska TSPN. De gav O(1)-tillnärmning algoritmer för flera specialfall, inklusive parallella segment av lika längd, översätter en konvex region, översätter en ansluten region, och mer allmänt, för regioner som har diameter segment som är parallella med en gemensam riktning, och förhållandet mellan den längsta och den kortaste diametern begränsas av en konstant. För det allmänna fallet med anslutna polygonala regioner erhöll Mata och Mitchell [15] en O(log n)-tillnärmningsalgoritm, baserad på "giljotin rektangulära underavdelningar", med tidsbunden O(N 5 ), där N är den totala komplexiteten i n-regionerna. Gudmundsson och Levcopoulos [10] har nyligen fått en snabbare metod, som för alla fasta  till > 0, garanteras att utföra minst en av följande uppgifter 1: (1) det ger en tur av längd som mest O (log n) gånger optimal i tiden O(n log n + N ); (2) det ger en tur av längd som mest (1 +  på) gånger optimal i tiden O(N 3 ). Hittills är ingen polynom-tids approximationsalgoritm känd för allmänna anslutna regioner. Nyligen visades att TSPN är APX-hård och inte kan approximeras inom en faktor på 1,000374 om inte P=NP [5, 11]. I själva verket, den oprecisa faktorn för vertex täcka problemet i grafer med grad begränsas av 5, som anges i [7], och på vilken resultatet i [11] är baserat, innebär en faktor större än så. I tiden sedan denna tidning först dök upp, har det visats av de Berg et. al [5] att TSPN har en O(1)-tillnärmningsalgoritm i det fall att regionerna är de regioner som är anslutna, åtskilda, konvexa och fett. Dessutom har Schwartz och Safra [25] förbättrat de nedre gränserna för [5, 11] på hårdheten av approximation av flera varianter av TSPN-problemet, och Jonsson [12] har gett en O(n) tid ε 2- approximation algoritm för fallet med regioner som är linjer i planet; vår tidigare O(n) tid π/2- approximation algoritm visas i Avsnitt 5. I detta dokument får vi flera approximativa resultat på det geometriska TSPN, inklusive: (1) Vi utökar de tillvägagångssätt som initieras i [1] och få den första O(1)-approximation algoritm för TSPN som har anslutna regioner med samma eller liknande diameter. Detta löser bland annat det öppna problemet som finns i [1], att ge en konstant-faktor approximation algoritm för TSPN på segment av samma längd och godtycklig orientering.
I REF föreslås en algoritm för TSPN med icke-överlappande regioner.
Approximation algorithms for TSP with neighborhoods in the plane
{'venue': 'Journal of Algorithms, Volume 48, Issue 1, August 2003, Pages 135-159. (special issue for SODA 2001)', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}