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/

Zendy Plus

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

Zendy Tools

Zendy Open

M\"omke and Svensson presented a beautiful new approach for the travelingsalesman problem on a graph metric (graph-TSP), which yields a$4/3$-approximation guarantee on subcubic graphs as well as a substantialimprovement over the $3/2$-approximation guarantee of Christofides' algorithmon general graphs. The crux of their approach is to compute an upper bound onthe minimum cost of a circulation in a particular network, $C(G,T)$, where $G$is the input graph and $T$ is a carefully chosen spanning tree. The cost ofthis circulation is directly related to the number of edges in a tour output bytheir algorithm. Mucha subsequently improved the analysis of the circulationcost, proving that M\"omke and Svensson's algorithm for graph-TSP has anapproximation ratio of at most $13/9$ on general graphs.  This analysis of the circulation is local, and vertices with degree four andfive can contribute the most to its cost. Thus, hypothetically, there couldexist a subquartic graph (a graph with degree at most four at each vertex) forwhich Mucha's analysis of the M\"omke-Svensson algorithm is tight. We show thatthis is not the case and that M\"omke and Svensson's algorithm for graph-TSPhas an approximation guarantee of at most $25/18$ on subquartic graphs. Toprove this, we present different methods to upper bound the minimum cost of acirculation on the network $C(G,T)$. Our approximation guarantee holds for allgraphs that have an optimal solution to a standard linear programmingrelaxation of graph-TSP with subquartic support.

An improved analysis of the M\"omke-Svensson algorithm for graph-TSP on subquartic graphs