Improving TSP Tours Using Dynamic Programming over Tree Decompositions

Thread View: gwene.acm.algorithms.transactions

1 messages

[T] Back to Threads [V] Tree View [G] Group Articles

1 total messages Started by unknown Fri, 04 Oct 2019 02:00

#445

Author: unknown
Date: Fri, 04 Oct 2019 02:00

1 lines
793 bytes

Marek Cygan, Łukasz Kowalik, Arkadiusz Socała<br /><br />Given a traveling salesman problem (TSP) tour H in graph G, a k-move is an operation that 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(nk). At ICALP’16, de Berg, Buchin, Jansen, and Woeginger showed an O(n⌊2k/3⌋+1)-time algorithm. We show an algorithm that runs in O(n(1/4+εk)k) time, where limk→ ∞ εk = 0.
<p><a href="http://dl.acm.org/citation.cfm?id341730">Link</a>

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads