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

Multiple TSP ($\mathrm{mTSP}$) is a important variant of $\mathrm{TSP}$ wherea set of $k$ salesperson together visit a set of $n$ cities. The$\mathrm{mTSP}$ problem has applications to many real life applications such asvehicle routing. Rothkopf introduced another variant of $\mathrm{TSP}$ calledmany-visits TSP ($\mathrm{MV\mbox{-}TSP}$) where a request $r(v)\in\mathbb{Z}_+$ is given for each city $v$ and a single salesperson needs tovisit each city $r(v)$ times and return back to his starting point. Acombination of $\mathrm{mTSP}$ and $\mathrm{MV\mbox{-}TSP}$ called many-visitsmultiple TSP $(\mathrm{MV\mbox{-}mTSP})$ was studied by B\'erczi, Mnich, andVincze where the authors give approximation algorithms for various variants of$\mathrm{MV\mbox{-}mTSP}$.  In this work, we show a simple linear programming (LP) based reduction thatconverts a $\mathrm{mTSP}$ LP-based algorithm to a LP-based algorithm for$\mathrm{MV\mbox{-}mTSP}$ with the same approximation factor. We apply thisreduction to improve or match the current best approximation factors of severalvariants of the $\mathrm{MV\mbox{-}mTSP}$. Our reduction shows that theaddition of visit requests $r(v)$ to $\mathrm{mTSP}$ does $\textit{not}$ makethe problem harder to approximate even when $r(v)$ is exponential in number ofvertices.  To apply our reduction, we either use existing LP-based algorithms for$\mathrm{mTSP}$ variants or show that several existing combinatorial algorithmsfor $\mathrm{mTSP}$ variants can be interpreted as LP-based algorithms. Thisallows us to apply our reduction to these combinatorial algorithms as wellachieving the improved guarantees.

Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems