I den här artikeln studerar vi ungefärligheten av det metriska reseförsäljarproblemet (TSP) och visar på nya tydliga omätbarhetsgränser för detta problem. Den bästa till nu kända hårdheten hos approximationsgränserna var 185/184 för det symmetriska fallet (på grund av Lampis) och 117/116 för det asymmetriska fallet (på grund av Papadimitriou och Vempala). Vi konstruerar här två nya begränsade förekomst CSP minskningar som förbättrar dessa gränser till 123/122 respektive 75/74, respektive. Den senare gränsen är den första förbättringen på mer än ett decennium för det asymmetriska TSP. Ett av våra viktigaste verktyg, som kan vara av oberoende intresse, är en ny konstruktion av en begränsad hjulförstärkare som används för att bevisa våra resultat.
Innehåller den metriska Traveling Salesman Problem som ett specialfall, är RPP APX-hård REF.
New Inapproximability Bounds for TSP
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}