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

The Capacitated Vehicle Routing Problem (CVRP) is one of the most extensivelystudied problems in combinatorial optimization. According to the property ofthe demand of customers, we distinguish three variants of CVRP: unit-demand,splittable and unsplittable. We consider $k$-CVRP in general metrics andgeneral graphs, where $k$ is the capacity of the vehicle and all the threeversions are APX-hard for each fixed $k\geq 3$. In this paper, we give a$(5/2-\Theta(\sqrt{1/k}))$-approximation algorithm for splittable andunit-demand $k$-CVRP and a $(5/2+\ln2-\Theta(\sqrt{1/k}))$-approximationalgorithm for unsplittable $k$-CVRP. Our approximation ratio is better than allprevious results for $k$ smaller than a sufficiently large value, say $k\leq1.7\times 10^7$. For small $k$, we also design independent elegant algorithmswith further improvements. For the splittable and unit-demand cases, we improvethe ratio from $1.792$ to $1.500$ for $k=3$, and from $1.750$ to $1.500$ for$k=4$ too. For the unsplittable case, we improve the ratio from $1.792$ to$1.500$ for $k=3$, from $2.051$ to $1.750$ for $k=4$, and from $2.249$ to$2.157$ for $k=5$. The approximation ratio for $k=3$ also surprisingly achievethe same ratio for the splittable case. Note that for small $k$ such as $3$,$4$ and $5$, some previous results have also been kept for decades. Ourtechniques, such as the EX-ITP method -- an extension of the classic ITPmethod, has potential to improve algorithms for more routing problems.

Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity