Leírás
Az Út TSP a klasszikus utazó ügynök probléma egy változata, ahol minimális
költségű Hamilton-kör helyett Hamilton-utat keresünk egy megadott s és t
csúcs között. Bármilyen közelítő algoritmus az Út esetre triviális módon
ad egy ugyanolyan arányú közelítést a hagyományos esetre is. Cserébe
viszont Christofides közismert algoritmusának a természetes kiterjesztése az
Út változatra csupán 5/3-approximációt eredményez, és 2011-ig ez is volt
az ismert legjobb. 2011 és 2018 között több cikk is megjelent, ami javított
ezen az arányon, mind kihasználva az eredményt, miszerint a Held-Karp
relaxáció megoldására tekintve kevesebb, mint 2 értékű vágások láncot
alkotnak. Az előadásban szereplő cikk megmutatja, hogy elég a kevesebb,
mint 3 értékű vágásokat vizsgálni (annak ellenére, hogy kevésbé
struktúráltak), és ezzel elérhető a 3/2-közelítés.