English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The $k$-Opt and Lin-Kernighan algorithm are two of the most important localsearch approaches for the Metric TSP. Both start with an arbitrary tour andmake local improvements in each step to get a shorter tour. We show that forany fixed $k\geq 3$ the approximation ratio of the $k$-Opt algorithm for MetricTSP is $O(\sqrt[k]{n})$. Assuming the Erd\H{o}s girth conjecture, we prove amatching lower bound of $\Omega(\sqrt[k]{n})$. Unconditionally, we obtainmatching bounds for $k=3,4,6$ and a lower bound of$\Omega(n^{\frac{2}{3k-3}})$. Our most general bounds depend on the values of afunction from extremal graph theory and are tight up to a factor logarithmic inthe number of vertices unconditionally. Moreover, all the upper bounds alsoapply to a parameterized version of the Lin-Kernighan algorithm withappropriate parameters. We also show that the approximation ratio of $k$-Optfor Graph TSP is $\Omega\left(\frac{\log(n)}{\log\log(n)}\right)$ and$O\left(\left(\frac{\log(n)}{\log\log(n)}\right)^{\log_2(9)+\epsilon}\right)$for all $\epsilon>0$. For the (1,2)-TSP we give a lower bound of$\frac{11}{10}$ on the approximation ratio of the $k$-improv and $k$-Optalgorithm for arbitrary fixed $k$.

On the Approximation Ratio of the $k$-Opt and Lin-Kernighan Algorithm