Abstrakt. Modern algoritmteori innehåller många tekniker för att angripa svåra problem, såsom approximationsalgoritmer å ena sidan och parameteriserad komplexitet å andra sidan. Det är dock fortfarande ovanligt att använda dessa två tekniker samtidigt, vilket är olyckligt, eftersom det finns naturliga problem som inte kan lösas med någondera tekniken ensam, utan snarare väl om vi kombinerar dem. Problemet som ska studeras här är inte bara naturligt, men också praktiskt: Överväg TSP, generaliserade enligt följande. Vi inför tidsfrister för vissa av hörnen, vilket effektivt begränsar dem att besökas före en viss tidpunkt. Det resulterande problemet DLTSP (ett specialfall av den välkända TSP med tidsfönster) ärver sin hårdhet från klassisk TSP, som är både känd från praktiken och känd för att vara ett av de svåraste problemen när det gäller approximabilitet: Inom polynom tid, inte ens ett polynom approximationsförhållande (bara en konstant) kan uppnås (om inte P = NP). Vi kommer att visa att DLTSP är ännu svårare än klassisk TSP i följande mening. Klassisk TSP, trots sin hårdhet, medger god approximation algoritmer om begränsad till metriska (eller nästan metriska) ingångar. Inte så DLTSP (och därmed varken TSP med tidsfönster): Vi kommer att bevisa att även för metriska ingångar, kan inget konstant approximationsförhållande någonsin uppnås (om inte P = NP). Detta är där parameterisering blir avgörande: Genom att kombinera metoder från området approximation algoritmer med idéer från teorin om parameteriserad komplexitet, tillämpar vi begreppet parameteriserad approximation. Därmed fick vi * Detta arbete delvis stöd av SNF Grant 200021-109252/1. Joachim Kneis och Joachim Kupke bodde på ETH Zürich när detta arbete var gjort. H.-J. Böckenhauer, J. Hromkovič, J. Kneis, och J. Kupke få en 2.5- approximation algoritm för DLTSP med en körtid av k!· poly (eng), där k betecknar antalet deadlines. Dessutom bevisar vi att det inte finns någon fpt-algoritm med en approximativ garanti på 2 − ε för alla ε > 0, om inte P = NP. Slutligen visar vi att, till skillnad från TSP, DLTSP blir mycket svårare när avslappning triangeln ojämlikhet. Mer exakt, för en godtycklig liten överträdelse av triangeln ojämlikhet, DLTSP medger inte en fpt-algoritm med approximation garanti (((1 − ε)/2) och V  på alla ε > 0, om inte P = NP.
För allmänna mått visade REF att TSPTW inte medger en approximation med konstant faktor om inte P = NP.
The Parameterized Approximability of TSP with Deadlines
{'venue': 'Theory of Computing Systems', 'journal': 'Theory of Computing Systems', 'mag_field_of_study': ['Mathematics', 'Computer Science']}