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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We give a new, strongly polynomial-time algorithm and improved analysis forthe metric $s-t$ path TSP. It finds a tour of cost less than 1.53 times theoptimum of the subtour elimination LP, while known examples show that 1.5 is alower bound for the integrality gap.  A key new idea is the deletion of some edges of Christofides' trees, which isthen accompanied by novel arguments of the analysis: edge-deletion disconnectsthe trees, which are then partly reconnected by `parity correction'. We showthat the arising `connectivity correction' can be achieved for a minor extracost.  On the one hand this algorithm and analysis extend previous tools such as thebest-of-many Christofides algorithm. On the other hand, powerful new tools aresolicited, such as a flow problem for analyzing the reconnection cost, and theconstruction of a set of more and more restrictive spanning trees, each ofwhich can still be found by the greedy algorithm. We show that these trees canreplace the convex combination of spanning trees in the best-of-mayChristofides algorithm.  These new methods lead to improving the integrality ratio and approximationguarantee below 1.53, as it is already sketched in the preliminary shortenedversion of this article that appeared in FOCS 2016. The algorithm and analysishave been significantly simplified in the current article, and details ofproofs and explanations have been added.

The Salesman's Improved Paths: 3/2+1/34 Integrality Gap and Approximation Ratio