Vi återbesöker den resande säljare problem med stadsdelar (TSPN) och presentera den första konstant-ratio approximation för diskar i planet: Med tanke på en uppsättning n diskar i planet, en TSP turné vars längd är som mest O(1) gånger den optimala kan beräknas i tid som är polynom i n. Vårt resultat är den första konstant-ratio approximation för en klass av planar konvexa kroppar av godtycklig storlek och godtyckliga korsningar. För att uppnå en O(1)-uppskattning, minskar vi den resande försäljare problem med diskar, upp till konstanta faktorer, till en minimal vikt slå set problem i en geometrisk hypergraf. Kopplingen mellan TSPN och träffuppsättningar i geometriska hypergrafer, som fastställs här, kommer sannolikt att ha framtida tillämpningar. Relaterat arbete. Arkin och Hassin [2] gav konstant-faktor approximationer för översättningar av en ansluten region, och mer allmänt, för områden med parvis parallella diametrar, där förhållandet mellan den längsta och den kortaste diametern begränsas av en konstant. Dumitrescu och Mitchell [16] utvidgade ovanstående resultat till anslutna bostadsområden med jämförbara diametrar. Bodlaender m.fl. [8] beskrev en PTAS för TSPN med separata fett kvarter av ungefär samma storlek i R d, där d är konstant (detta inkluderar fallet med separata enheter diskar i planet). Tidigare föreslog Dumitrescu och Mitchell [16] ett PTAS för TSPN med feta områden av ungefär samma storlek och avgränsade djup i planet, där Spirkl [42] nyligen rapporterade och fyllde en lucka; se även en uppföljningsnot i [34]. Mata och Mitchell [28] approximerade O(log n) för TSPN med n anslutna och godtyckligt korsande områden i planet; se även [7]. Elbassioni m.fl. [19] och Gudmundsson och Levcopolos [23] förbättrade algoritmens körtid. O(log n)-uppskattningen bygger på följande tidiga resultat av Levcopoulos och Lingas [27]: Varje (enkel) rektilinjär polygon P med n hörn, r av vilka är reflex, kan delas upp i O (n log n) tid i rektanglar vars totala omkrets är log r gånger omkretsen av P. Använda en approximationsalgoritm på grund av Slavik [41] för Euclidean grupp TSP, de Berg et al. [6] erhållna approximationer med konstant faktor för olika fettkonvexa regioner (av godtyckliga diametrar) i planet. Därefter Elbassioni et al. [19] gav konstanta approximationer för godtyckligt skärande fettkonvexa regioner av jämförbar storlek. Mitchells preliminära arbete [32] gav ett PTAS för plana områden med avgränsat djup och godtycklig storlek, särskilt för separata fettregioner. Chan och Jiang [12] gav en PTAS för fett, svagt åtskilda regioner i metriska utrymmen med konstant dubbleringsdimension (som kombinerar en tidigare QPTAS av Chan och Elbassioni [11] med en PTAS för TSP i dubbleringsmått av Bartal et al. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Dissar och bollar är utan tvekan bland de enklaste kvarterstyperna [2, 16, 24]. TSPN för diskar är NP-hård, och det förblir så för kongruenta diskar, eftersom när diskcentra är fast och radien tenderar att noll, problemet minskar till TSP för poäng. När det gäller approximationer, är fallet med kongruenta bollar relativt väl förstådd: Med tanke på en uppsättning n kongruent (säg, enhet) bollar i R d, en TSP tur vars längd är som mest O(1) gånger den optimala kan beräknas i polynom tid, när d är konstant [18]. För diskar med godtyckliga radier och skärningspunkter var dock ingen approximation av konstant ratio känd. Några av svårigheterna med diskar av godtyckliga radier i planet som avslöjades i [17]. Den senaste tidens arbete av Dumitrescu och Tóth [18] inriktades på gränslösa områden, såsom linjer eller hyperplan: De gav en konstant-faktor approximation för TSPN med n hyperplan i R d i O(n) tid, och en O(log 3 n)- approximation för n linjer i R d i tid polynom i n, där d är konstant. I motsats till det aktuella dokumentet överväger TSPN med godtyckliga diskar i R 2, som kräver helt andra approximation tekniker och nya idéer.
Sedan i REF hittades en konstant faktor approximation som kan hantera godtyckliga (eventuellt olika storlek och skärande) diskar i planet.
Constant-Factor Approximation for TSP with Disks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}