Artykuł w czasopiśmie
Brak miniatury
Licencja
Dostęp zamkniętyImproving TSP Tours Using Dynamic Programming over Tree Decompositions
| cris.lastimport.scopus | 2024-02-12T20:03:32Z |
| dc.abstract.en | Given a traveling salesman problem (TSP) tour H in graph G, a k-move is an operation which removes k edges from H, and adds k edges of G so that a new tour H' is formed. The popular k-opt heuristic for TSP finds a local optimum by starting from an arbitrary tour H and then improving it by a sequence of k-moves. Until 2016, the only known algorithm to find an improving k-move for a given tour was the naive solution in time O(n^k). At ICALP'16 de Berg, Buchin, Jansen and Woeginger showed an O(n^{floor(2/3k)+1})-time algorithm. We show an algorithm which runs in O(n^{(1/4 + epsilon_k)k}) time, where lim_{k -> infinity} epsilon_k = 0. It improves over the state of the art for every k >= 5. For the most practically relevant case k=5 we provide a slightly refined algorithm running in O(n^{3.4}) time. We also show that for the k=4 case, improving over the O(n^3)-time algorithm of de Berg et al. would be a major breakthrough: an O(n^{3 - epsilon})-time algorithm for any epsilon > 0 would imply an O(n^{3 - delta})-time algorithm for the All Pairs Shortest Paths problem, for some delta>0. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.conference.country | Austria |
| dc.conference.datefinish | 2017-09-06 |
| dc.conference.datestart | 2017-09-04 |
| dc.conference.place | Vienna |
| dc.conference.series | European Symposium on Algorithms |
| dc.conference.series | European Symposium on Algorithms |
| dc.conference.seriesshortcut | ESA |
| dc.conference.shortcut | ESA 2017 |
| dc.conference.weblink | https://algo2017.ac.tuwien.ac.at/esa/ |
| dc.contributor.author | Socała, Arkadiusz |
| dc.contributor.author | Cygan, Marek |
| dc.contributor.author | Kowalik, Łukasz |
| dc.date.accessioned | 2024-01-25T03:59:05Z |
| dc.date.available | 2024-01-25T03:59:05Z |
| dc.date.issued | 2017 |
| dc.description.finance | Nie dotyczy |
| dc.identifier.doi | 10.4230/LIPICS.ESA.2017.30 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/109123 |
| dc.identifier.weblink | https://drops.dagstuhl.de/opus/volltexte/2017/7853/ |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.pages | 30:1--30:14 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.title | Improving TSP Tours Using Dynamic Programming over Tree Decompositions |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |