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 study the unit-demand capacitated vehicle routing problem in the randomsetting of the Euclidean plane. The objective is to visit $n$ random terminalsin a square using a set of tours of minimum total length, such that each tourvisits the depot and at most $k$ terminals.  We design an elegant algorithm combining the classical sweep heuristic andArora's framework for the Euclidean traveling salesman problem [Journal of theACM 1998]. We show that our algorithm is a polynomial-time approximation ofratio at most $1.55$ asymptotically almost surely. This improves on previousapproximation ratios of $1.995$ due to Bompadre, Dror, and Orlin [Journal ofApplied Probability 2007] and $1.915$ due to Mathieu and Zhou [RandomStructures and Algorithms 2022]. In addition, we conjecture that, for any$\varepsilon>0$, our algorithm is a $(1+\varepsilon)$-approximationasymptotically almost surely.

Euclidean Capacitated Vehicle Routing in Random Setting: A $1.55$-Approximation Algorithm