Traveling Salesman Problem (TSP) är bland de mest kända NP-hårda optimeringsproblem. Vi designar för detta problem en randomiserad polynom-tid algoritm som beräknar en (1 + ε)- tillnärmning till den optimala turen, för alla fasta ε > 0, i TSP fall som bildar en godtycklig metriska utrymme med avgränsade inneboende dimension. De berömda resultaten av Arora [Aro98] och Mitchell [Mit99] bevisar att ovanstående resultat håller i det speciella fallet med TSP i ett fast-dimensionellt Euclidean utrymme. Därför visar vår algoritm att den algoritmiska dragbarheten hos metrisk TSP beror på rummets dimensionalitet och inte på dess specifika geometri. Detta resultat löser ett problem som har varit öppet sedan den kvasi-polynomiska tidsalgoritmen i Talwar [Tal04].
Bartal m.fl. visade algoritmisk dragbarhet av denmetriska TSP beror på dimensionaliteten i utrymmet och inte på dess specifika geometri REF.
The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}