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

We present an approximation algorithm for $\{0,1\}$-instances of thetravelling salesman problem which performs well with respect to combinatorialdominance. More precisely, we give a polynomial-time algorithm which hasdomination ratio $1-n^{-1/29}$. In other words, given a$\{0,1\}$-edge-weighting of the complete graph $K_n$ on $n$ vertices, ouralgorithm outputs a Hamilton cycle $H^*$ of $K_n$ with the following property:the proportion of Hamilton cycles of $K_n$ whose weight is smaller than that of$H^*$ is at most $n^{-1/29}$. Our analysis is based on a martingale approach.Previously, the best result in this direction was a polynomial-time algorithmwith domination ratio $1/2-o(1)$ for arbitrary edge-weights. We also prove ahardness result showing that, if the Exponential Time Hypothesis holds, thereexists a constant $C$ such that $n^{-1/29}$ cannot be replaced by $\exp(-(\logn)^C)$ in the result above.

A domination algorithm for $\{0,1\}$-instances of the travelling salesman problem