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

In the Asymmetric Traveling Salesperson Problem (ATSP) the goal is to find aclosed walk of minimum cost in a directed graph visiting every vertex. Weconsider the approximability of ATSP on topologically restricted graphs. It hasbeen shown by [Oveis Gharan and Saberi 2011] that there exists polynomial-timeconstant-factor approximations on planar graphs and more generally graphs ofconstant orientable genus. This result was extended to non-orientable genus by[Erickson and Sidiropoulos 2014].  We show that for any class of \emph{nearly-embeddable} graphs, ATSP admits apolynomial-time constant-factor approximation. More precisely, we show that forany fixed $k\geq 0$, there exist $\alpha, \beta>0$, such that ATSP on$n$-vertex $k$-nearly-embeddable graphs admits a $\alpha$-approximation in time$O(n^\beta)$. The class of $k$-nearly-embeddable graphs contains graphs with atmost $k$ apices, $k$ vortices of width at most $k$, and an underlying surfaceof either orientable or non-orientable genus at most $k$. Prior to our work,even the case of graphs with a single apex was open. Our algorithm combinestools from rounding the Held-Karp LP via thin trees with dynamic programming.  We complement our upper bounds by showing that solving ATSP exactly on graphsof pathwidth $k$ (and hence on $k$-nearly embeddable graphs) requires time$n^{\Omega(k)}$, assuming the Exponential-Time Hypothesis (ETH). This issurprising in light of the fact that both TSP on undirected graphs and MinimumCost Hamiltonian Cycle on directed graphs are FPT parameterized by treewidth.

Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs