# Improved Approximation Algorithms for Multidepot Capacitated Vehicle Routing

Jingyang Zhao111University of Electronic Science and Technology of China.
Email<EMAIL_ADDRESS>Mingyu Xiao222University of Electronic
Science and Technology of China. Email<EMAIL_ADDRESS>
###### Abstract

The Multidepot Capacitated Vehicle Routing Problem (MCVRP) is a well-known
variant of the classic Capacitated Vehicle Routing Problem (CVRP), where we
need to route capacitated vehicles located in multiple depots to serve
customers’ demand such that each vehicle must return to the depot it starts,
and the total traveling distance is minimized. There are three variants of
MCVRP according to the property of the demand: unit-demand, splittable and
unsplittable. We study approximation algorithms for $k$-MCVRP in metric graphs
where $k$ is the capacity of each vehicle, and all three versions are APX-hard
for any constant $k\geq 3$. Previously, Li and Simchi-Levi proposed a
$(2\alpha+1-\alpha/k)$-approximation algorithm for splittable and unit-demand
$k$-MCVRP and a $(2\alpha+2-2\alpha/k)$-approximation algorithm for
unsplittable $k$-MCVRP, where $\alpha=3/2-10^{-36}$ is the current best
approximation ratio for metric TSP. Harks _et al._ further improved the ratio
to 4 for the unsplittable case. We give a $(4-1/1500)$-approximation algorithm
for unit-demand and splittable $k$-MCVRP, and a $(4-1/50000)$-approximation
algorithm for unsplittable $k$-MCVRP. Furthermore, we give a $(3+\ln
2-\max\\{\Theta(1/\sqrt{k}),1/9000\\})$-approximation algorithm for splittable
and unit-demand $k$-MCVRP, and a $(3+\ln 2-\Theta(1/\sqrt{k}))$-approximation
algorithm for unsplittable $k$-MCVRP under the assumption that the capacity
$k$ is a fixed constant. Our results are based on recent progress in
approximating CVRP.

Keywords: Capacitated Vehicle Routing, Multidepot, Approximation Algorithms

##  1 Introduction

In the Multidepot Capacitated Vehicle Routing Problem (MCVRP), we are given a
complete undirected graph $G=(V\cup D,E)$ with an edge weight $w$ satisfying
the symmetric and triangle inequality properties. The $n$ nodes in
$V=\\{v_{1},\dots,v_{n}\\}$ represent $n$ customers and each customer $v\in V$
has a demand $d(v)\in\mathbb{Z}_{\geq 1}$. The $m$ nodes in
$D=\\{u_{1},\dots,u_{m}\\}$ represent $m$ depots, with each containing an
infinite number of vehicles with a capacity of $k\in\mathbb{Z}_{\geq 1}$ (we
can also think that each depot contains only one vehicle, which can be used
many times). A tour is a walk that begins and ends at the same depot and the
sum of deliveries to all customers in it is at most $k$. The traveling
distance of a tour is the sum of the weights of edges in the tour. In MCVRP,
we wish to find a set of tours to satisfy every customer’s demand with a
minimum total distance of all the tours. In the _unsplittable_ version of the
problem, each customer’s demand can only be delivered by a single tour. In the
_splittable_ version, each customer’s demand can be delivered by more than one
tour. Moreover, if each customer’s demand is a unit, it is called the _unit-
demand_ version.

In logistics, MCVRP is an important model that has been studied extensively in
the literature (see [19] for a survey). If there is only one depot, MCVRP is
known as the famous Capacitated Vehicle Routing Problem (CVRP). Since $k$-CVRP
is APX-hard for any fixed $k\geq 3$ [3], it also holds for $k$-MCVRP.

Consider approximation algorithms for $k$-CVRP. Haimovich and Kan proposed
[11] a well-known algorithm based on a given Hamiltonian cycle, called
_Iterated Tour Partitioning (ITP)_. Given an $\alpha$-approximation algorithm
for metric TSP, for splittable and unit-demand $k$-CVRP, ITP can achieve a
ratio of $\alpha+1-\alpha/k$ [11]. For unsplittable $k$-CVRP, Altinkemer and
Gavish [1] proposed a modification of ITP, called UITP, that can achieve a
ratio of $\alpha+2-2\alpha/k$ for even $k$. When $k$ is arbitrarily large,
$k$-CVRP becomes metric TSP. For metric TSP, there is a well-known
$3/2$-approximation algorithm [6, 21], and currently Karlin _et al._ [15, 16]
has slightly improved the ratio to $3/2-10^{-36}$. Recently, some progress has
been made in approximating $k$-CVRP. Blauth _et al._ [4] improved the ratio to
$\alpha+1-\varepsilon$ for splittable and unit-demand $k$-CVRP and to
$\alpha+2-2\varepsilon$ for unsplittable $k$-CVRP, where $\varepsilon$ is a
value related to $\alpha$ and satisfies $\varepsilon\approx 1/3000$ when
$\alpha=3/2$. Then, for unsplittable $k$-CVRP, Friggstad _et al._ [9] further
improved the ratio to $\alpha+1+\ln 2-\varepsilon$ based on an LP rounding
method, where $\varepsilon\approx 1/3000$ is the improvement based on the
method in [4]. There are other improvements for the case that the capacity $k$
is a small fixed constant. Bompadre _et al._ [5] improved the classic ratios
by a term of ${\Omega}(1/k^{3})$ for all three versions. Zhao and Xiao [27]
proposed a $(5/2-\Theta(1/\sqrt{k}))$-approximation algorithm for splittable
and unit-demand $k$-CVRP and a $(5/2+\ln 2-\Theta(1/\sqrt{k}))$-approximation
algorithm for unsplittable $k$-CVRP, where the improvement
$\Theta(1/\sqrt{k})$ is larger than $1/3000$ for any $k\leq 10^{7}$.

Consider approximation algorithms for $k$-MCVRP. Few results are available in
the literature. Note that $\alpha\approx 3/2$. Based on a modification of ITP,
Li and Simchi-Levi [18] proposed a cycle-partition algorithm, which achieves a
ratio of $2\alpha+1-\alpha/k\approx 4-\Theta(1/k)$ for splittable and unit-
demand $k$-MCVRP and a ratio of $2\alpha+2-2\alpha/k\approx 5-\Theta(1/k)$ for
unsplittable $k$-MCVRP. The only known improvement was made by Harks _et al._
[12], where they proposed a tree-partition algorithm with an improved
4-approximation ratio for unsplittable $k$-MCVRP. Note that their algorithm
also implies a 4.38-approximation ratio for a more general problem, called
_Capacitated Location Routing_ , where we need to open some depots (with some
cost) first and then satisfy customers using vehicles in the opened depots.
When $k$ is arbitrarily large, $k$-MCVRP becomes metric $m$-depot TSP. For
metric $m$-depot TSP, Rathinam  _et al._ [20] proposed a simple
2-approximation algorithm, and Xu  _et al._ [25] proposed an improved
$(2-1/m)$-approximation algorithm. Then, based on an edge exchange algorithm,
Xu and Rodrigues [24] obtained an improved $3/2$-approximation algorithm for
any fixed $m$. Traub  _et al._ [22] further improved the ratio to
$\alpha+\varepsilon$ for any fixed $m$.

If the capacity $k$ is fixed, we will see that splittable $k$-MCVRP is
equivalent to unit-demand $k$-MCVRP. Moreover, both unit-demand and
unsplittable $k$-MCVRP can be reduced to the _minimum weight $k$-set cover
problem_. In minimum weight $k$-set cover, we are given a set of elements
(called _universe_), a set system with each set in it having a weight and at
most $k$ elements, and we need to find a collection of sets in the set system
with a minimum total weight that covers the universe. In the reduction,
customers can be seen as the elements. There are at most $mn^{O(k)}$ feasible
tours, and each tour can be seen as a set containing all customers in the tour
with a weight of the tour. When $k$ is fixed, the reduction is polynomial. It
is well-known [7] that the minimum weight $k$-set cover problem admits an
approximation ratio of $H_{k}$, where $H_{k}\coloneqq 1+1/2+\cdots+1/k$ is the
$k$-th harmonic number. Hassin and Levin [13] improved the ratio to
$H_{k}-\Theta(1/k)$. Recently, using a non-obvious local search method, Gupta
_et al._ [10] improved the ratio to $H_{k}-\Theta(\ln^{2}k/k)$, which is
better than 4 for any fixed $k\leq 30$. So, for some $k\leq 30$, the best
ratios of $k$-MCVRP are $H_{k}-\Theta(\ln^{2}k/k)$.

Note that each vehicle must return to the depot it starts in our setting,
which is also known as the _fixed-destination_ property [18]. Li and Simchi-
Levi [18] also considered a non-fixed-destination version where each vehicle
may terminate at any depot. The non-fixed-destination MCVRP can be reduced to
CVRP easily with the approximation ratio preserved since one can regard all
depots as a single super-depot and let the distance between a customer and the
super-depot be the minimum weight of the edges between the customer and the
depots.

Recently, Lai  _et al._ [17] studied a variant of MCVRP, called _$m$ -Depot
Split Delivery Vehicle Routing_, where the number of depots is still $m$, but
the number of vehicles in each depot is limited and each vehicle can be used
for at most one tour (one can also think that each depot contains only one
vehicle, which can be used a limited number of times). When $m$ is fixed, they
obtained a $(6-4/m)$-approximation algorithm. Carrasco Heine  _et al._ [14]
considered a bifactor approximation algorithm for a variant of Capacitated
Location Routing, where each depot has a capacity as well.

###  1.1 Our Contributions

Motivated by recent progress in approximating $k$-CVRP, we design improved
approximation algorithms for $k$-MCVRP. For the sake of presentation, we
assume that $\alpha=3/2$. The contributions are shown as follows.

Firstly, we review the cycle-partition algorithm in [18] and then propose a
refined tree-partition algorithm based on the idea in [12]. Note that the
previous tree-partition algorithm in [12] contains a fixable flaw (see
Appendix A) and our refined algorithm has a better approximation ratio for
fixed $k$. For splittable and unit-demand $k$-MCVRP, both of them are
4-approximation algorithms. By making a trade-off between them and further
using the result in [4], we obtain an improved $(4-1/1500)$-approximation
algorithm. Note that the cycle-partition algorithm itself may only lead to a
$(4-1/3000)$-approximation ratio.

Secondly, using the LP-rounding method in [9], we obtain an LP-based cycle-
partition algorithm that can achieve a $(4+\ln 2+\delta)$-approximation ratio
for unsplittable $k$-MCVRP with any constant $\delta>0$. By making a trade-off
between the LP-based cycle-partition algorithm and the tree-partition
algorithm and further using the result in [4], we obtain an improved
$(4-1/50000)$-approximation algorithm.

At last, we propose an LP-based tree-partition algorithm, which works for
fixed $k$. Using the lower bounds of $k$-CVRP in [27], we obtain an improved
$(3+\ln 2-\Theta(1/\sqrt{k}))$-approximation algorithm for all three versions
of $k$-MCVRP, which is better than the current-best ratios for any $k>11$.
Moreover, by making a trade-off between the LP-based tree-partition algorithm
and the cycle-partition algorithm and further using the result in [4], we show
that the approximation ratio can be improved to $3+\ln
2-\max\\{\Theta(1/\sqrt{k}),1/9000\\}$ for splittable and unit-demand
$k$-MCVRP.

##  2 Preliminaries

###  2.1 Definitions

In MCVRP, we let $G=(V\cup D,E)$ denote the input complete graph, where
vertices in $V$ represent customers and vertices in $D$ represent depots.
There is a non-negative weight function $w:E\to\mathbb{R}_{\geq 0}$ on the
edges in $E$. We often write $w(u,v)$ to mean the weight of edge $uv$, instead
of $w(uv)$. Note that $w(u,v)$ would be the same as the distance between $u$
and $v$. The weight function $w$ is a semi-metric function, i.e., it is
symmetric and satisfies the triangle inequality. For any weight function
$w:X\to\mathbb{R}_{\geq 0}$, we extend it to subsets of $X$, i.e., we define
$w(Y)=\sum_{x\in Y}w(x)$ for $Y\subseteq X$. There is also a demand function
$d$: $V\rightarrow\mathbb{N}_{\geq 1}$, where $d(v)$ is the demand required by
customer $v\in V$. In the following, we let $\Delta=\sum_{v\in V}\min_{u\in
D}d(v)w(u,v)$. For a component $S$, we simply use $v\in S$ (resp., $e\in S$)
to denote a vertex (resp., an edge) of $S$, and let $w(S)\coloneqq\sum_{e\in
S}w(e)$ and $d(S)\coloneqq\sum_{v\in S}d(v)$.

A _walk_ in a graph is a succession of edges in the graph, where an edge may
appear more than once. We will use a sequence of vertices to denote a walk.
For example, $v_{1}v_{2}v_{3}\dots v_{l}$ means a walk with edges
$v_{1}v_{2}$, $v_{2}v_{3}$, and so on. A _path_ in a graph is a walk such that
no vertex appears more than once in the sequence, and a _cycle_ is a walk such
that only the first and the last vertices are the same. A cycle containing $l$
edges is called an _$l$ -cycle_ and the _length_ of it is $l$. A _spanning
forest_ in a graph is a forest that spans all vertices in the graph. A
_constrained spanning forest_ in graph $G$ is a spanning forest where each
tree contains only one depot.

An _itinerary_ $I$ is a walk that starts and ends at the same depot and does
not pass through any other depot. It is called an _empty itinerary_ and denote
it by $I=\emptyset$ if there are no customer vertices on $I$, and a _non-empty
itinerary_ otherwise. A non-empty itinerary can be split into several minimal
cycles containing only one depot, and each such cycle is called a _tour_. The
Multidepot Capacitated Vehicle Routing Problem ($k$-MCVRP) can be described as
follows.

######  Definition 1 ($k$-MCVRP).

An instance $(G=(V\cup D,E),w,d,k)$ consists of:

  * •

a complete graph $G$, where $V=\\{v_{1},\dots,v_{n}\\}$ represents the $n$
customers and $D=\\{u_{1},\dots,u_{m}\\}$ represents the $m$ depots,

  * •

a semi-metric weight function $w$: $(V\cup D)\times(V\cup
D)\rightarrow\mathbb{R}_{\geq 0}$, which represents the distances,

  * •

a demand function $d$: $V\rightarrow\mathbb{N}_{\geq 1}$, where $d(v)$ is the
demand required by customer $v\in V$,

  * •

the capacity $k\in\mathbb{Z}_{\geq 1}$ of vehicles that initially stays at
each depot.

A feasible solution is a set of $m$ itineraries, with each containing one
different depot:

  * •

each tour delivers at most $k$ of the demand to customers on the tour,

  * •

the union of tours over all itineraries meets every customer’s demand.

Specifically, the goal is to find a set of itineraries
$\mathcal{I}=\\{I_{1},\dots,I_{m}\\}$ where $I_{i}$ contains depot $u_{i}$,
minimizing the total weight of the succession of edges in the walks in
$\mathcal{I}$, i.e.,
$w(\mathcal{I})\coloneqq\sum_{I\in\mathcal{I}}w(I)=\sum_{I\in\mathcal{I}}\sum_{e\in
I}w(e)$.

According to the property of the demand, we define three well-known versions.
If each customer’s demand must be delivered in one tour, we call it
_unsplittable $k$-MCVRP_. If a customer’s demand can be split into several
tours, we call it _splittable $k$-MCVRP_. If each customer’s demand is a unit,
we call it _unit-demand $k$-MCVRP_.

In the following, we use CVRP to denote MCVRP with $m=1$, i.e., only one
depot. Unless otherwise specified, we think that $k$-MCVRP satisfies the
fixed-destination property. Moreover, if it holds the non-fixed-destination
property, we called it _non-fixed $k$-MCVRP_.

###  2.2 Assumptions

Note that in our problem the demand $d(v)$ may be very large since the
capacity $k$ may be arbitrarily larger than $n$. For the sake of analysis, we
make several assumptions that can be guaranteed by some simple observations or
polynomial-time reductions.

######  Assumption 2.

For splittable and unsplittable $k$-MCVRP, each customer’s demand is at most
$k$.

Assumption 2 can be guaranteed by polynomial-time reductions. Clearly, it
holds for unsplittable $k$-MCVRP; otherwise, the problem has no feasible
solution. For the splittable case, Dror and Trudeau [8] proved that two tours
in $k$-CVRP sharing two common customers can be modified into two better
tours, which clearly also holds for $k$-MCVRP. A _trivial tour_ is a tour that
contains only one depot and only one customer. Consider a customer $v\in V$
and an optimal solution with no two tours sharing two common customers. Since
there are $m$ depots and each tour contains one depot, there are at most
$m(n-1)$ non-trivial tours containing $v$ that deliver at most $m(n-1)(k-1)$
demand to $v$. So, if $d(v)>m(n-1)(k-1)$, there exists an optimal solution
that contains at least $l\coloneqq\lceil\frac{d(v)-m(n-1)(k-1)}{k}\rceil$
trivial tours. Note that there are $m$ kinds of trivial tours for $v$, and we
can directly assign $l$ of the cheapest one. After doing these for all
customers, every customer has a demand of at most $m(n-1)(k-1)$. Then, for
each customer $v\in V$ such that $d(v)>k$, we can replace it with $O(mn)$
customers with zero inter-distance and each has a demand of at most $k$. The
new instance is equivalent to the old one, and its size increases from
$O(m+n)$ to $O(mn^{2})$.

######  Assumption 3.

For splittable $k$-MCVRP with fixed $k$, each customer’s demand is a unit.

By Assumption 2, each customer’s demand is at most $k$. Under the case that
$k$ is fixed, we can further replace each customer $v$ with $d(v)$ unit-demand
customers with zero inter-distance. The size of the instance increases at most
$O(nk)$. So, Assumption 3 can be guaranteed by polynomial-time reductions. It
states that splittable $k$-MCVRP with fixed $k$ can be reduced to unit-demand
$k$-MCVRP in polynomial time with the approximation ratio preserved.

######  Assumption 4.

For unsplittable, splittable, and unit-demand $k$-MCVRP, there exists an
optimal solution where each tour delivers an integer amount of demand to each
customer in the tour.

Assumption 4 is a simple observation since in our problem both customers’
demand and vehicles’ capacity are integers. Note that it can be proved by a
similar exchanging argument in [27]. So, in the following, we may only
consider a tour that delivers an integer amount of demand to each customer in
the tour.

Based on Assumption 4, we know that for unit-demand $k$-MCVRP, there is an
optimal solution consisting of a set of cycles, which intersect only at the
depot.

##  3 Lower Bounds

To connect approximation algorithms for $k$-MCVRP with $k$-CVRP, it is
convenient to consider non-fixed $k$-MCVRP. The first reason is that non-fixed
$k$-MCVRP is a relaxation of $k$-MCVRP, and then an optimal solution of the
former one provides a lower bound for the latter. Let OPT (resp.,
$\mbox{OPT}^{\prime}$) denote the weight of an optimal solution for $k$-MCVRP
(resp., $k$-CVRP). Then, we have $\mbox{OPT}^{\prime}\leq\mbox{OPT}$. The
second is that non-fixed $k$-MCVRP is equivalent to $k$-CVRP. The reduction is
shown as follows.

Given $G=(V\cup D,E)$, we obtain a new undirected complete graph
$H=(V\cup\\{o\\},F)$ by replacing the $m$ depots in $D$ with a new single
depot, denoted by $o$. There is a weight function $c:F\to\mathbb{R}_{\geq 0}$
on the edges in $F$. Moreover, it holds that $c(o,v)=\min_{u\in D}w(u,v)$ and
$c(v,v^{\prime})=\min\\{c(o,v)+c(o,v^{\prime}),w(v,v^{\prime})\\}$ for all
$v,v^{\prime}\in V$. We can verify that the weight function $c$ is a semi-
metric function. Note that $\Delta=\sum_{v\in V}d(v)c(o,v)$. Clearly, any
feasible solution of $k$-CVRP in $H$ corresponds to a feasible solution for
non-fixed $k$-MCVRP in $G$ with the same weight. Note that an edge
$vv^{\prime}$ in $E$ with $w(v,v^{\prime})>c(o,v)+c(o,v^{\prime})$ was also
called a “dummy” edge in [18]. Any tour using a dummy edge $vv^{\prime}$ can
be transformed into two tours with a smaller weight by replacing $vv^{\prime}$
with two edges $uv$ and $u^{\prime}v^{\prime}$ incident to depots such that
$c(o,v)=w(u,v)$ and $c(o,v^{\prime})=w(u^{\prime},v^{\prime})$. So, any
feasible solution of non-fixed $k$-MCVRP in $G$ can also be modified into a
feasible solution for $k$-CVRP in $H$ with a non-increasing weight.

A _Hamiltonian cycle_ in a graph is a cycle that contains all vertices in the
graph exactly once. Let $C^{*}$ be a minimum cost Hamiltonian cycle in graph
$H$.

We mention three following lower bounds for $k$-CVRP, which also works for
$k$-MCVRP.

######  Lemma 5 ([11]).

It holds that $\mbox{OPT}\geq\mbox{OPT}^{\prime}\geq c(C^{*})$.

###### Proof.

In an optimal solution of $k$-CVRP, it is easy to see that each vertex has an
even degree. We can obtain an Euler tour and then get a Hamiltonian cycle in
graph $H$ by shortcutting. The Hamiltonian cycle has at least the cost of
$C^{*}$. So, the lemma holds. ∎

######  Lemma 6 ([11]).

It holds that $\mbox{OPT}\geq\mbox{OPT}^{\prime}\geq(2/k)\Delta$.

###### Proof.

Consider a tour $C=ov_{1}\dots v_{i}o$ in an optimal solution of $k$-CVRP. By
the triangle inequality, we have $c(C)\geq 2c(o,v)$ for each $v\in C$. Since
each tour has a capacity of at most $k$, we have $c(C)\geq(1/k)\sum_{v\in
C}d(v)c(C)\geq(2/k)\sum_{v\in C}d(v)c(o,v)$. Each vertex $v\in V$ must be
contained in a tour. So, $\mbox{OPT}^{\prime}\geq(2/k)\sum_{v\in
V}d(v)c(o,v)=(2/k)\Delta$. ∎

Let $T^{*}$ denote an optimal spanning tree in graph $H$. Clearly, its cost is
a lower bound of an optimal Hamiltonian cycle in $H$. By Lemma 5, we have the
following lemma.

######  Lemma 7.

It holds that $\mbox{OPT}\geq\mbox{OPT}^{\prime}\geq c(T^{*})$.

##  4 Review of the Previous Algorithms

In this section, we review the cycle-partition algorithm in [18] and the tree-
partition algorithm in [12] for $k$-MCVRP.

###  4.1 The Cycle-Partition Algorithm

The main idea of the cycle-partition algorithm [18] is to construct a solution
for non-fixed $k$-MCVRP based on the ITP or UITP algorithm for $k$-CVRP, and
then modify the solution into a solution for $k$-MCVRP.

The ITP and UITP algorithms. For splittable and unit-demand $k$-CVRP, given a
Hamiltonian cycle $C$ in graph $H$, the ITP algorithm is to split the cycle
into segments in a good way, with each containing at most $k$ of demand, and
for each segment assign two edges between the new depot $o$ and endpoints of
the segment. The solution has a weight of at most $(2/k)\Delta+c(C)$ [11, 2].
For unsplittable $k$-CVRP, the UITP algorithm is to use the ITP algorithm with
a capacity of $k/2$ to obtain a solution for splittable and unit-demand
$k$-CVRP, and then modify the solution into a feasible solution for
unsplittable $k$-CVRP. Altinkemer and Gavish proved [1] that the modification
does not take any additional cost.

######  Lemma 8 ([11, 2, 1]).

Given a Hamiltonian cycle $C$ in graph $H$, for splittable and unit-demand
$k$-CVRP, the ITP algorithm can use polynomial time to output a solution of
cost at most $(2/k)\Delta+c(C)$; for unsplittable $k$-CVRP, the bound improves
to $(4/k)\Delta+c(C)$.

The cycle-partition algorithm. For $k$-MCVRP, the cycle-partition algorithm is
to use the ITP or UITP algorithm to obtain a feasible solution for non-fixed
$k$-MCVRP, and then modify the solution into a feasible solution for $k$-MCVRP
using some additional cost. Li and Simchi-Levi [18] proved that the additional
cost is exactly the cost of the Hamiltonian cycle used.

######  Lemma 9 ([18]).

Given a Hamiltonian cycle $C$ in graph $H$, for splittable and unit-demand
$k$-MCVRP, there is a polynomial-time algorithm to output a solution of cost
at most $(2/k)\Delta+2c(C)$; for unsplittable $k$-MCVRP, the bound improves to
$(4/k)\Delta+2c(C)$.

Using the $3/2$-approximate Hamiltonian cycle [6, 21], by Lemmas 5 and 6, the
cycle-partition algorithm achieves a 4-approximation ratio for splittable and
unit-demand $k$-MCVRP and a 5-approximation ratio for unsplittable $k$-MCVRP.

###  4.2 The Tree-Partition Algorithm

The tree-partition algorithm is based on an optimal spanning tree in graph
$H$. Note that an optimal spanning tree in $H$ corresponds to an optimal
constrained spanning forest in $G$. The algorithm is to split the
corresponding constrained spanning forest into small components in a good way
such that each component has a demand of at most $k$, and moreover each that
contains no depots in it has a demand of at least $k/2$. Note that each
component that contains one depot can be transformed into a tour by doubling
all edges in it and then shortcutting. For each component that contains no
depots, the algorithm will add one edge with minimized weight connecting one
depot to it. Then, it can be transformed into a tour by the same method:
doubling and shortcutting. Note that this algorithm works for unsplittable,
splittable, and unit-demand $k$-MCVRP at the same time.

######  Lemma 10 ([12]).

For unsplittable, splittable, and unit-demand $k$-MCVRP, there is a
polynomial-time algorithm to output a solution of cost at most
$(4/k)\Delta+2c(T^{*})$.

By Lemmas 6 and 7, the tree-partition algorithm achieves a 4-approximation
ratio for unsplittable, splittable, and unit-demand $k$-MCVRP.

##  5 An Improvement for Splittable MCVRP

In this section, we first propose a refined tree-partition algorithm based on
the idea in [12]. The previous algorithm in [12] contains a fixable flaw (see
Appendix A). Our algorithm and its analysis are simpler due to the previous
assumptions. Moreover, our algorithm has a better approximation ratio for the
case that the capacity $k$ is fixed. Then, based on recent progress in
approximating $k$-CVRP [4], we obtain an improved $(4-1/1500)$-approximation
algorithm for splittable and unit-demand $k$-MCVRP.

###  5.1 A Refined Tree-Partition Algorithm

In our algorithm, we first assign a single cheapest trivial tour for each
$v\in V$ with $d(v)>\lfloor k/2\rfloor$ since each customer’s demand is at
most $k$ by Assumption 2. Let $V^{\prime}$ denote the rest customers. To
satisfy customers in $V^{\prime}$, we find an optimal spanning tree
$T^{\prime*}$ in graph $H[V^{\prime}\cup\\{o\\}]$. Note that $T^{\prime*}$
corresponds to a constrained spanning forest in $G[V^{\prime}\cup D]$, denoted
by $\mathcal{F}$. Consider a tree $T_{u}\in\mathcal{F}$ that is rooted at the
depot $u\in D$. Then, we will generate tours based on splitting $T_{u}$, like
Hark _et al._ did in [12]. For each $v\in T_{u}$, we denote the sub-tree
rooted at $v$ and the children set of $v$ by $T_{v}$ and $Q_{v}$, and let
$d(T_{v})=\sum_{v^{\prime}\in T_{v}}d(v^{\prime})$.

  * •

If $d(T_{u})\leq k$, it can be directly transformed into a tour by doubling
and shortcutting.

  * •

Otherwise, we can do the following repeatedly until it satisfies that
$d(T_{u})\leq k$. We can find a customer $v\in T_{u}$ such that $d(T_{v})>k$
and $d(T_{v^{\prime}})\leq k$ for every children $v^{\prime}\in Q_{v}$.
Consider the sub-trees $\mathcal{T}_{v}\coloneqq\\{T_{v^{\prime}}\mid
v^{\prime}\in Q_{v}\\}$. We can greedily partition them into $l$ sets
$\mathcal{T}_{1},\dots,\mathcal{T}_{l}$ such that $\lfloor
k/2\rfloor<d(\mathcal{T}_{i})\leq k$ for each $i\in\\{2,\dots,l\\}$. For each
such set, saying $\mathcal{T}_{2}$, we can combine them into a component $S$
by adding $v$ with edges joining $v$ and each tree in $\mathcal{T}_{2}$. Note
that $S$ is a sub-tree of $T_{v}$. Then, we find an edge $e_{S}$ with
minimized weight connecting one depot to one vertex in $S$. By doubling
$e_{S}$ with the edges in $S$ and shortcutting (note that we also need to
shortcut $v$), we obtain a tour satisfying all customers in trees of
$\mathcal{T}_{2}$. After handling $\mathcal{T}_{i}$ for each
$i\in\\{2,\dots,l\\}$, we only have $\mathcal{T}_{1}$. If
$d(\mathcal{T}_{1})>\lfloor k/2\rfloor$, we can handle it like
$\mathcal{T}_{i}$ with $i>1$. Otherwise, we have
$d(\mathcal{T}_{1})\leq\lfloor k/2\rfloor$. The remaining tree is denoted by
$T^{\prime}_{u}$. Note that $d(\mathcal{T}_{1})+d(v)\leq k$ since
$d(v)\leq\lfloor k/2\rfloor$. So, in $T^{\prime}_{u}$ the condition
$d(T^{\prime}_{v})>k$ and $d(T^{\prime}_{v^{\prime}})\leq k$ for every
children $v^{\prime}\in Q^{\prime}_{v}$ will not hold: the algorithm will
terminate.

The algorithm is shown in Algorithm 1.

Algorithm 1 A refined tree-partition algorithm for $k$-MCVRP

Input: Two undirected complete graphs: $G=(V\cup D,E)$ and
$H=(V\cup\\{o\\},F)$.
Output: A solution for $k$-MCVRP.

1:For each customer $v\in V$ with $d(v)>\lfloor k/2\rfloor$, assign a trivial
tour from $v$ to its nearest depot.

2:Find an optimal spanning tree $T^{\prime*}$ in graph
$H[V^{\prime}\cup\\{o\\}]$.

3:Obtain the constrained spanning forest $\mathcal{F}$ in $G[V^{\prime}\cup
D]$ with respect to $T^{\prime*}$.

4:for every tree $T_{u}\in\mathcal{F}$ do $\triangleright$ $T_{u}$ is rooted
at the depot $u$

5: while $d(T_{u})>k$ do

6: Find $v\in T_{u}$ such that $d(T_{v})>k$ and $d(T_{v^{\prime}})\leq k$ for
each $v^{\prime}\in Q_{v}$. $\triangleright$ $Q_{v}$ is the children set of
$v$

7: Greedily partition trees in $\mathcal{T}_{v}\coloneqq\\{T_{v^{\prime}}\mid
v^{\prime}\in Q_{v}\\}$ into $l$ sets $\mathcal{T}_{1},\dots,\mathcal{T}_{l}$
such that $\lfloor k/2\rfloor<d(\mathcal{T}_{i})\leq k$ for each
$i\in\\{2,\dots,l\\}$.

8: Initialize $\mbox{Index}\coloneqq\\{2,\dots,l\\}$.

9: if $d(\mathcal{T}_{1})>\lfloor k/2\rfloor$ then

10: $\mbox{Index}\coloneqq\mbox{Index}\cup\\{1\\}$.

11: end if

12: for $i\in\mbox{Index}$ do

13: Combine trees in $\mathcal{T}_{i}$ into a component $S$ by adding $v$ with
edges joining $v$ and each tree in $\mathcal{T}_{i}$.

14: Find an edge $e_{S}$ with minimized weight connecting one depot to one
vertex in $S$.

15: Obtain a tour satisfying all customers in trees of $\mathcal{T}_{i}$ by
doubling $e_{S}$ with the edges in $S$ and shortcutting.

16: Update $T_{u}$ by removing the component $S$ from $T_{u}$.

17: end for

18: end while

19: Obtain a tour satisfying all customers in $\mathcal{T}_{u}$ by doubling
and shortcutting.

20:end for

######  Theorem 11.

For unsplittable, splittable, and unit-demand $k$-MCVRP, the refined tree-
partition algorithm can use polynomial time to output a solution of cost at
most $\frac{2}{\lfloor k/2\rfloor+1}\Delta+2c(T^{\prime*})$.

###### Proof.

To show that the algorithm takes polynomial time, we need to prove that it
will not get stuck in Step 5. In the first loop, we assume that it finds $v$
satisfying the condition in Step 6. As mentioned, we will have $d(T_{v})\leq
k$ at the end of this loop. So, the number of loops in Step 5 is bounded by
the number of customers in $T_{u}$, and hence the algorithm takes polynomial
time.

Next, we show that the algorithm generates a feasible solution. Clearly, each
tour in Steps 1, 15, and 19 has a capacity of at most $k$. Note that after
assigning a tour in Step 15, the algorithm will remove all customers in the
tour in Step 16. So, each customer is satisfied using only one tour.

Next, we analyze the total cost of all tours.

Consider tours in Step 1. Let $\overline{V^{\prime}}=V\setminus V^{\prime}$.
Since we assign a trivial tour to each customer $v\in\overline{V^{\prime}}$,
the total cost of these tours is $\sum_{v\in\overline{V^{\prime}}}2c(o,v)$.
Note that we have $d(v)>\lfloor k/2\rfloor$ for every
$v\in\overline{V^{\prime}}$. So, the cost is
$\sum_{v\in\overline{V^{\prime}}}2c(o,v)\leq\frac{2}{\lfloor
k/2\rfloor+1}\sum_{v\in\overline{V^{\prime}}}d(v)c(o,v)$.

Consider tours in Step 15. By definition, we have
$w(e_{S})=\min_{v^{\prime}\in
S}c(o,v^{\prime})\leq\min_{v^{\prime}\in\mathcal{T}_{i}}c(o,v^{\prime})$.
Since $\sum_{v^{\prime}\in\mathcal{T}_{i}}d(v^{\prime})>\lfloor k/2\rfloor$,
we have
$\min_{v^{\prime}\in\mathcal{T}_{i}}c(o,v^{\prime})\leq\sum_{v^{\prime}\in\mathcal{T}_{i}}\frac{d(v^{\prime})}{\sum_{v^{\prime}\in\mathcal{T}_{i}}d(v^{\prime})}c(o,v^{\prime})\leq\frac{1}{\lfloor
k/2\rfloor+1}\sum_{v^{\prime}\in\mathcal{T}_{i}}d(v^{\prime})c(o,v^{\prime})$.
So, $w(e_{S})\leq\frac{1}{\lfloor
k/2\rfloor+1}\sum_{v^{\prime}\in\mathcal{T}_{i}}d(v^{\prime})c(o,v^{\prime})$.
Recall that each customer is contained in only one tour. The cost of these
tours on $e_{S}$ is $\sum_{\mathcal{T}_{i}}2w(e_{S})\leq\frac{2}{\lfloor
k/2\rfloor+1}\sum_{\mathcal{T}_{i}}\sum_{v^{\prime}\in\mathcal{T}_{i}}d(v^{\prime})c(o,v^{\prime})\leq\frac{2}{\lfloor
k/2\rfloor+1}\sum_{v^{\prime}\in V^{\prime}}c(o,v^{\prime})$. Moreover, the
cost of these tours on the edges of $S$ is $\sum_{S}2w(S)$.

Consider tours in Step 19. The cost of these tours is exactly twice the weight
of the left edges after moving all components in Step 15 from each tree of
$\mathcal{F}$. So, the cost is $2w(\mathcal{F})-\sum_{S}2w(S)$.

Therefore, the total cost is $\frac{2}{\lfloor k/2\rfloor+1}\sum_{v\in
V}d(v)c(o,v)+2c(T^{\prime*})=\frac{2}{\lfloor
k/2\rfloor+1}\Delta+2c(T^{\prime*})$. ∎

######  Lemma 12.

It holds that $c(C^{*})\geq c(T^{\prime*})$.

###### Proof.

Let $C^{\prime*}$ denote an optimal Hamiltonian cycle in graph
$H[V^{\prime}\cup\\{o\\}]$. By the proof of Lemma 7, we have
$c(C^{\prime*})\geq c(T^{\prime*})$. Note that we can obtain a Hamiltonian
cycle in $H[V^{\prime}\cup\\{o\\}]$ by shortcutting the optimal Hamiltonian
cycle $C^{*}$ in $H$. By the triangle inequality, we have $c(C^{*})\geq
c(C^{\prime*})$. ∎

By Theorem 11 and Lemmas 5 and 12, the refined tree-partition algorithm has an
approximation ratio of $\frac{k}{\lfloor k/2\rfloor+1}+2=4-\Theta(1/k)$, which
is better than 4 for the case that the capacity $k$ is fixed. Next, we
consider the improvement for general $k$.

###  5.2 The Improvement

Recently, Blauth  _et al._ [4] made a significant progress in approximating
$k$-CVRP. We show that it can be applied to $k$-MCVRP to obtain a
$(4-1/1500)$-approximation algorithm for splittable and unit-demand $k$-MCVRP.

Recall that $\mbox{OPT}^{\prime}$ is the cost of an optimal solution of
$k$-CVRP in graph $H$. Fix a constant $\varepsilon>0$. Clearly, one can obtain
an improvement using this better lower bound:
$(1-\varepsilon)\cdot\mbox{OPT}^{\prime}\geq(2/k)\Delta$. Their main result
showed that if $(1-\varepsilon)\cdot\mbox{OPT}^{\prime}<(2/k)\Delta$ one can
find a Hamiltonian cycle $C$ such that $\lim_{\varepsilon\rightarrow
0}c(C)=c(C^{*})$.

######  Lemma 13 ([4]).

If $(1-\varepsilon)\cdot\mbox{OPT}^{\prime}<(2/k)\Delta$, there is a function
$f:\mathbb{R}_{>0}\rightarrow\mathbb{R}_{>0}$ with
$\lim_{\begin{subarray}{c}\varepsilon\rightarrow
0\end{subarray}}f(\varepsilon)=0$ and a polynomial-time algorithm to get a
Hamiltonian cycle $C$ in $H$ with
$c(C)\leq(1+f(\varepsilon))\cdot\mbox{OPT}^{\prime}$.

The details of the function $f(\cdot)$ in [4] are put in Appendix D.

######  Theorem 14.

For splittable and unit-demand $k$-MCVRP, there is a polynomial-time
$(4-1/1500)$-approximation algorithm.

###### Proof.

If $(1-\varepsilon)\cdot\mbox{OPT}^{\prime}\geq(2/k)\Delta$, we call the
refined tree-partition algorithm. By Theorem 11, it has a weight of at most
$\frac{2}{\lfloor
k/2\rfloor+1}\Delta+2c(T^{\prime*})\leq\frac{4}{k}\Delta+2c(T^{\prime*})$.
Recall that $\mbox{OPT}\geq\mbox{OPT}^{\prime}$. Then, by Lemmas 5 and 12, it
has an approximation ratio of $2(1-\varepsilon)+2=4-2\varepsilon$. Otherwise,
we use the Hamiltonian $C$ in Lemma 13 to call the cycle-partition algorithm.
By Lemma 9, it has a weight of at most $(2/k)\Delta+2c(C)$. Then, by Lemma 6,
it has an approximation ratio of $1+2(1+f(\varepsilon))=3+2f(\varepsilon)$.

Therefore, the combined algorithm admits an approximation ratio of
$\min_{\varepsilon}\max\\{4-2\varepsilon,3+2f(\varepsilon)\\}$. By the
calculation, the best choice for $\varepsilon$ is $1/3000$. So, the
approximation ratio is $4-1/1500$. ∎

Note that the result in Theorem 14 is obtained by making a trade-off between
the cycle-partition algorithm and the refined tree-partition algorithm. If we
only use the cycle-partition algorithm, i.e., we also use it with a
$3/2$-approximate Hamiltonian cycle for the case that
$(1-\varepsilon)\cdot\mbox{OPT}^{\prime}\geq(2/k)\Delta$, we can merely get a
$(4-1/3000)$-approximation algorithm.

##  6 An Improvement for Unsplittable MCVRP

In this section, we study unsplittable $k$-MCVRP. Recently, Friggstad  _et
al._ [9] proposed an improved LP-based approximation algorithm for
unsplittable $k$-CVRP. We show that it can be used to obtain an LP-based
cycle-partition algorithm for unsplittable $k$-MCVRP. Moreover, it achieves an
improved $(4-1/50000)$-approximation ratio.

###  6.1 An LP-Based Cycle-Partition Algorithm

Recall that unsplittable $k$-CVRP can be reduced to the minimum weight $k$-set
cover problem if $k$ is fixed: customers can be seen as the elements, and each
tour can be seen as a set containing all customers in the tour with a weight
of the tour. Since there are $n^{O(k)}$ feasible tours, the reduction is not
polynomial when $k$ is general. The main idea of the LP-based approximation
algorithm in [9] is that fixing a constant $0<\delta<1$ they build an LP (in
the form of set cover) only for customers $v$ with $d(v)\geq\delta k$. Then,
the number of feasible tours is $n^{O(1/\delta)}$ which is polynomially
bounded. Using the well-known randomized LP-rounding method (see [23]), they
obtain a set of tours that forms a partial solution with a cost of $\ln
2\cdot\mbox{OPT}$. Then, they design tours to satisfy the left customers based
on a variant of the UITP algorithm with an excepted cost of
$\frac{1}{1-\delta}\cdot(2/k)\Delta+c(C)$, where $C$ is a given Hamiltonian
cycle in graph $H$. Letting $\delta$ be a small constant, we have the
following lemma.

######  Lemma 15 ([9]).

Given a Hamiltonian cycle $C$ in graph $H$, for unsplittable $k$-CVRP with any
constant $\delta>0$, there is a polynomial-time algorithm to output a solution
of cost at most $(\ln 2+\delta)\cdot\mbox{OPT}^{\prime}+(2/k)\Delta+c(C)$.

For unsplittable $k$-MCVRP, we can use the same idea (details are put in
Appendix B). Fixing a constant $0<\delta<1$, we build an LP (in the form of
set cover) only for customers $v$ with $d(v)\geq\delta k$. A partial solution
based on randomized LP-rounding has a weight of $\ln 2\cdot\mbox{OPT}$. For
left customers, we obtain a solution for $k$-CVRP in $H$ with an excepted cost
of $\frac{1}{1-\delta}\cdot(2/k)\Delta+c(C)$. Since the latter is based on the
idea of the UITP algorithm, we can modify them into a set of feasible tours
for $k$-MCVRP using an additional cost of $c(H)$ like Lemma 9. So, we can get
the following theorem.

######  Theorem 16 (*).

Given a Hamiltonian cycle $C$ in graph $H$, for unsplittable $k$-MCVRP with
any constant $\delta>0$, the LP-based cycle-partition algorithm can use
polynomial time to output a solution of cost at most $(\ln
2+\delta)\cdot\mbox{OPT}+(2/k)\Delta+2c(C)$.

###  6.2 The Improvement

Note that using the LP-based cycle-partition algorithm with a
$3/2$-approximate Hamiltonian cycle, by Lemmas 5 and 6, we can obtain a
$(4+\ln 2+\delta)$-approximation ratio. The ratio is even worse than the
4-approximation ratio obtained by the tree-partition algorithm. But, the LP-
based cycle-partition algorithm can use the result in Lemma 13 since it is
based on a Hamiltonian cycle in $H$. Intuitively, if $(2/k)\Delta$ is close to
$\mbox{OPT}^{\prime}$, we can find an optimal Hamiltonian cycle by Lemma 13,
and then the LP-based cycle-partition algorithm achieves a $(3+\ln
2+\delta<4)$-approximation; otherwise, the tree-partition algorithm has a
better than 4-approximation ratio. We can make a trade-off.

######  Theorem 17.

For unsplittable $k$-MCVRP, there is a polynomial-time
$(4-1/50000)$-approximation algorithm.

###### Proof.

If $(1-\varepsilon)\cdot\mbox{OPT}^{\prime}\geq(2/k)\Delta$, by the proof of
Theorem 14, it has an approximation ratio of
$2(1-\varepsilon)+2=4-2\varepsilon$. Otherwise, we use the Hamiltonian $C$ in
Lemma 13 to call the cycle-partition algorithm. By Theorem 16, it has a weight
of at most $(\ln 2+\varepsilon)\cdot\mbox{OPT}^{\prime}+(2/k)\Delta+2c(C)$.
Then, by Lemma 6, it has an approximation ratio of $\ln
2+1+2(1+f(\varepsilon))+\delta=3+\ln 2+2f(\varepsilon)+\delta$.

So, the combined algorithm has an approximation ratio of
$\min_{\varepsilon}\max\\{4-2\varepsilon,3+\ln 2+2f(\varepsilon)+\delta\\}$.
By the calculation, the best choice for $\varepsilon$ is $1/100000$. So, the
approximation ratio is $4-1/50000$. ∎

##  7 An Improvement for $k$-MCVRP with Fixed Capacity

In this section, we consider further improvements for the case that the
capacity $k$ is fixed. We propose an LP-based tree-partition algorithm based
on the refined tree-partition algorithm with the LP-rounding method. The
algorithm admits an approximation ratio of $3+\ln 2-\Theta(1/\sqrt{k})$. Then,
by further using the result in Lemma 13, we also obtain a $(3+\ln
2-1/9000)$-approximation algorithm for splittable and unit-demand $k$-MCVRP.
Note that the former is better when $k$ is a fixed constant less than $3\times
10^{8}$.

###  7.1 An LP-Based Tree-Partition Algorithm

Recall that due to Assumption 4 we only consider a tour that delivers an
integer amount of demand to each customer in the tour. Since $k$ is fixed,
there are at most $mn^{O(k)}$ feasible tours for $k$-MCVRP. Note that for
splittable $k$-MCVRP each customer’s demand is a unit by Assumption 3. Denote
the set of feasible tours by $\mathcal{C}$, and define a variable $x_{C}$ for
each tour $C\in\mathcal{C}$. We have the following LP.

minimize $\displaystyle\sum_{C\in\mathcal{C}}w(C)\cdot x_{C}$ subject to
$\displaystyle\sum_{\begin{subarray}{c}C\in\mathcal{C}:\\\ v\in
C\end{subarray}}x_{C}\geq\ $ $\displaystyle 1,\quad$ $\displaystyle\forall\
v\in V,$ $\displaystyle x_{C}\geq\ $ $\displaystyle 0,\quad$
$\displaystyle\forall\ C\in\mathcal{C}.$

The LP-based tree-partition algorithm is shown in Algorithm 2.

Algorithm 2 An LP-based tree-partition algorithm for $k$-MCVRP

Input: Two undirected complete graphs: $G=(V\cup D,E)$ and
$H=(V\cup\\{o\\},F)$, and a constant $\gamma\geq 0$.
Output: A solution for $k$-MCVRP.

1:Solve the LP in $mn^{O(k)}$ time.

2:for $C\in\mathcal{C}$ do Put the tour $C$ into solution with a probability
of $\min\\{\gamma\cdot x_{C},1\\}$.

3:end for

4:For each customer contained in multiple tours, we shortcut it for all but
one tour. $\triangleright$ Some customers may be contained in more than one
tour due to the randomized rounding.

5:Let $\widetilde{V}$ be the customers that are still unsatisfied.

6:Obtain two new complete graphs: $\widetilde{G}=G[\widetilde{V}\cup D]$ and
$\widetilde{H}=G[\widetilde{V}\cup\\{o\\}]$.

7:Call the refined tree-partition algorithm in Algorithm 1.

Denote the set of tours obtained by the randomized LP-rounding method by
$\mathcal{C}_{1}$ and the set of tours obtained by the refined tree-partition
algorithm by $\mathcal{C}_{2}$. Next, we analyze $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$.

######  Lemma 18.

It holds that $\mathbb{E}[w(\mathcal{C}_{1})]\leq\gamma\cdot\mbox{OPT}$.

###### Proof.

Clearly, we have $\sum_{C\in\mathcal{C}}x_{C}\cdot w(C)\leq\mbox{OPT}$ since
the LP is a relaxation of $k$-MCVRP. Each tour $C\in\mathcal{C}$ is chosen
with a probability of at most $\gamma\cdot x_{C}$. So, the chosen tours have
an expected weight of at most $\sum_{C\in\mathcal{C}}\gamma\cdot x_{C}\cdot
w(C)\leq\gamma\cdot\mbox{OPT}$. The shortcutting in Step 4 will not increase
the weight by the triangle inequality. So, we have
$\mathbb{E}[w(\mathcal{C}_{1})]\leq\gamma\cdot\mbox{OPT}$. ∎

######  Lemma 19.

It holds that $\mbox{Pr}[v\in\widetilde{V}]\leq e^{-\gamma}$ for every $v\in
V$.

###### Proof.

Let $\mathcal{C}_{v}$ be all feasible tours that contain $v$. Note that
$\sum_{v\in\mathcal{C}_{v}}x_{C}\geq 1$ by the definition of LP. So, we have
$\mbox{Pr}[v\in\widetilde{V}]=\prod_{C\in\mathcal{C}_{v}}\mbox{Pr}[C~{}\mbox{is}~{}\mbox{not}~{}\mbox{chosen}]\leq\prod_{C\in\mathcal{C}_{v}}(1-\gamma\cdot
x_{C})\leq e^{-\sum_{C\in\mathcal{C}_{v}}\gamma\cdot x_{C}}\leq e^{-\gamma}$.
∎

Consider an optimal solution of $k$-CVRP in graph $H$. It consists of a set of
simple cycles. Note that if we delete the longest edge from each cycle, we can
obtain a spanning tree (by shortcutting if necessary since a customer may
appear in more than one tour for the splittable case). In the following, we
denote this spanning tree by $T^{**}$.

######  Lemma 20.

It holds that $\mathbb{E}[w(\mathcal{C}_{2})]\leq
e^{-\gamma}\cdot\frac{2}{\lfloor k/2\rfloor+1}\Delta+2c(T^{**})$.

###### Proof.

By Theorem 1, we have $w(\mathcal{C}_{2})\leq\frac{2}{\lfloor
k/2\rfloor+1}\widetilde{\Delta}+2c(\widetilde{T^{\prime*}})$, where
$\widetilde{\Delta}=\sum_{v\in\widetilde{V}}d(v)c(o,v)$,
$\widetilde{T^{\prime*}}$ is an optimal spanning tree in graph
$H[\widetilde{V^{\prime}}]$, and $\widetilde{V^{\prime}}=\\{v\mid
v\in\widetilde{V}~{}\mbox{and}~{}d(v)>\lfloor k/2\rfloor\\}$ by Algorithm 1.
By Lemma 19, we have $\mathbb{E}[\widetilde{\Delta}]=\sum_{v\in
V}d(v)c(o,v)\cdot\mbox{Pr}[v\in\widetilde{V}]\leq e^{-\gamma}\cdot\sum_{v\in
V}d(v)c(o,v)=e^{-\gamma}\cdot\Delta$. Next, we consider
$c(\widetilde{T^{\prime*}})$. Note that $T^{**}$ is a spanning tree in $H$
such that it consists of a set of paths that start from $v$. So, we can
shortcut all customers in $V\setminus\widetilde{V^{\prime}}$ to obtain another
spanning tree in graph $H[\widetilde{V^{\prime}}]$. Since
$\widetilde{T^{\prime*}}$ is an optimal spanning tree in
$H[\widetilde{V^{\prime}}]$, we have $c(\widetilde{T^{\prime*}})\leq
c(T^{**})$ by the triangle inequality. ∎

######  Theorem 21.

For unsplittable, splittable, and unit-demand $k$-MCVRP with any constant
$\gamma\geq 0$, the LP-based tree-partition algorithm can use polynomial time
to output a solution with an expected cost of at most
$\gamma\cdot\mbox{OPT}+e^{-\gamma}\cdot\frac{2}{\lfloor
k/2\rfloor+1}\Delta+2c(T^{**})$.

The algorithm can be derandomized efficiently by the method of conditional
expectations [23].

###  7.2 The Analysis

In this subsection, we show that the LP-based tree-partition algorithm
achieves an approximation ratio of $3+\ln 2-\Theta(1/\sqrt{k})$ for all the
three versions of $k$-MCVRP. By Assumption 3, splittable $k$-MCVRP is
equivalent to unit-demand $k$-MCVRP. Moreover, since an optimal solution of
unit-demand $k$-MCVRP is a lower bound of unsplittable $k$-MCVRP, the analyzed
approximation ratio for unit-demand $k$-MCVRP also holds for unsplittable
$k$-MCVRP. Therefore, we only analyze the approximation ratio for unit-demand
$k$-MCVRP in the following.

By Assumption 4, we can also think that the optimal solution of unit-demand
$k$-CVRP in graph $H$ consists of a set of cycles intersecting only at the
depot $o$. Zhao and Xiao [27] proved the following lemma.

######  Lemma 22 ([27]).

Adding $k^{2}n+k-(n\bmod k)$ unit-demand customers on the depot $o$, for unit-
demand $k$-CVRP, there exists an optimal solution consisting of a set of
$(k+1)$-cycles, which intersect only at the depot.

Note that adding one customer on the depot $o$ for $k$-CVRP is equivalent to
adding one customer on any depot in $D$ for $k$-MCVRP. So, we assume w.o.l.g.
that for unit-demand $k$-CVRP there exists an optimal solution consisting of a
set of $k$-cycles, which intersects only at the depot. Recall that $T^{**}$ is
a spanning tree obtained by deleting the longest edge from each cycle in the
optimal solution. Based on this, Zhao and Xiao [27] proved two following lower
bounds.

######  Lemma 23 ([27]).

It holds that
$\Delta\leq\left(\frac{k+2}{2}-\sum_{i=1}^{m^{\prime}}ix_{i}\right)\mbox{OPT}^{\prime}$
and $c(T^{**})\leq\left(1-\frac{1}{2}\max_{1\leq i\leq
m^{\prime}}x_{i}\right)\mbox{OPT}^{\prime}$, where
$m^{\prime}=\lceil\frac{k+1}{2}\rceil$, $x_{i}\geq 0$, and
$\sum_{i=1}^{m^{\prime}}x_{i}=1$.

Note that $x_{i}$ measures some properties of the optimal solution. By Theorem
21 and Lemma 23, for unit-demand $k$-MCVRP, the approximation ratio of the LP-
based tree-partition algorithm can be computed as follows:

$\max_{\begin{subarray}{c}x_{1},x_{2},\dots,x_{m^{\prime}}\geq 0\\\
x_{1}+x_{2}+\dots+x_{m^{\prime}}=1\end{subarray}}\min_{\begin{subarray}{c}\gamma\geq
0\end{subarray}}\left\\{\gamma+e^{-\gamma}\cdot\frac{2}{\lfloor
k/2\rfloor+1}\left(\frac{k+2}{2}-\sum_{i=1}^{m^{\prime}}ix_{i}\right)+2\left(1-\frac{1}{2}\max_{1\leq
i\leq m^{\prime}}x_{i}\right)\right\\}.$

As mentioned, this approximation ratio also holds for splittable and
unsplittable $k$-MCVRP. Computing this approximation ratio is an optimization
problem. We can even use computers to solve it in a brute-and-force way. Next,
we give its precise value (details are put in Appendix C).

######  Theorem 24 (*).

For unsplittable, splittable, and unit-demand $k$-MCVRP, the LP-based tree-
partition algorithm achieves an approximation ratio of $\max\\{g(\lceil
x_{0}\rceil),g(\lfloor x_{0}\rfloor)\\}$, where
$x_{0}\coloneqq\frac{\sqrt{4k+5}-1}{2}$ and $g(x)\coloneqq
3+\ln\left(\frac{k+1-x}{\lfloor k/2\rfloor+1}\right)-\frac{1}{x}$.

Our approximation ratio $3+\ln 2-\Theta(1/\sqrt{k})$ has a good performance
when $k$ is a small constant. By the calculation, the
$(H_{k}-\Theta(\ln^{2}k/k))$-approximation ratio for $k$-set cover in [10] is
better than ours for $k\leq 11$. So, for $k\leq 11$, the current-best ratios
for $k$-MCVRP are $H_{k}-\Theta(\ln^{2}k/k)$ [10].

###  7.3 A Further Improvement for Splittable $k$-MCVRP

Consider that $k$ is a big constant. If $(2/k)\Delta$ is close to
$\mbox{OPT}^{\prime}$, for splittable and unit-demand $k$-MCVRP, the LP-based
tree-partition achieves a $(3+\ln 2)$-approximation ratio. Similarly, we can
find an almost optimal Hamiltonian cycle by Lemma 13, and then the cycle-
partition algorithm achieves a $(3<3+\ln 2)$-approximation ratio. So, we can
obtain a further improvement for splittable and unit-demand $k$-MCVRP by
making a trade-off between them.

######  Theorem 25.

For splittable and unit-demand $k$-MCVRP, there is a polynomial-time $(3+\ln
2-1/9000)$-approximation algorithm.

###### Proof.

If $(1-\varepsilon)\cdot\mbox{OPT}^{\prime}\geq(2/k)\Delta$, we call the LP-
based tree-partition algorithm with $\gamma=\ln 2$. By Theorem 21, it has a
weight of at most $\ln 2\cdot\mbox{OPT}+\frac{1}{\lfloor
k/2\rfloor+1}\Delta+2c(T^{**})\leq\ln
2\cdot\mbox{OPT}+\frac{2}{k}\Delta+2c(T^{**})$. Recall that
$\mbox{OPT}\geq\mbox{OPT}^{\prime}$. By Lemma 23, we have
$c(T^{**})\leq\mbox{OPT}^{\prime}$. Then, it has an approximation ratio of
$\ln 2+1-\varepsilon+2=3+\ln 2-\varepsilon$. Otherwise, we use the Hamiltonian
$C$ in Lemma 13 to call the cycle-partition algorithm. By the proof of Theorem
14, it has an approximation ratio of $3+2f(\varepsilon)$.

So, the combined algorithm has an approximation ratio of
$\min_{\varepsilon}\max\\{3+\ln 2-\varepsilon,3+2f(\varepsilon)\\}$. By the
calculation, the best choice for $\varepsilon$ is $1/9000$. So, the
approximation ratio is $3+\ln 2-1/9000$. ∎

By the calculation, we can see that the result $3+\ln 2-\Theta(1/\sqrt{k})$ in
Theorem 24 is better than $3+\ln 2-1/9000$ for any $k<3\times 10^{8}$. Note
that for unsplittable $k$-MCVRP we cannot obtain further improvements using
the same method. The reason is that even using an optimal Hamiltonian cycle
the LP-based cycle-partition only achieves an approximation ratio of about
$3+\ln 2$ by Theorem 16. So, there is no improvement compared with the LP-
based tree-partition algorithm.

##  8 Conclusion

In this paper, we consider approximation algorithms for $k$-MCVRP. Previously,
only a few results were available in the literature. Based on recent progress
in approximating $k$-CVRP, we design improved approximation algorithms for
$k$-MCVRP. When $k$ is general, we improve the approximation ratio to
$4-1/1500$ for splittable and unit-demand $k$-MCVRP and to $4-1/50000$ for
unsplittable $k$-MCVRP; when $k$ is fixed, we improve the approximation ratio
to $3+\ln 2-\max\\{\Theta(1/\sqrt{k}),1/9000\\}$ for splittable and unit-
demand $k$-MCVRP and to $3+\ln 2-\Theta(1/\sqrt{k})$ for unsplittable
$k$-MCVRP.

We remark that for unsplittable, splittable, and unit-demand $k$-MCVRP with
fixed $3\leq k\leq 11$ the current best approximation ratios are still
$H_{k}-\Theta(\ln^{2}k/k)$ [10]. In the future, one may study how to improve
these results.

A more general problem than $k$-MCVRP is called _Multidepot Capacitated Arc
Routing_ (MCARP), where both vertices and arcs are allowed to require a
demand. For MCARP, current best-known approximation algorithms on general
metric graphs are still based on the cycle-partition algorithm (see [26]).
Some results in this paper could be applied to MCARP to obtain some similar
improvements.

## References

  * [1] Kemal Altinkemer and Bezalel Gavish.  Heuristics for unequal weight delivery problems with a fixed error guarantee.  Operations Research Letters, 6(4):149–158, 1987.
  * [2] Kemal Altinkemer and Bezalel Gavish.  Heuristics for delivery problems with constant error guarantees.  Transportation Science, 24(4):294–297, 1990.
  * [3] Tetsuo Asano, Naoki Katoh, Hisao Tamaki, and Takeshi Tokuyama.  Covering points in the plane by _k_ -tours: Towards a polynomial time approximation scheme for general _k_.  In STOC 1997, pages 275–283. ACM, 1997.
  * [4] Jannis Blauth, Vera Traub, and Jens Vygen.  Improving the approximation ratio for capacitated vehicle routing.  Mathematical Programming, pages 1–47, 2022.
  * [5] Agustín Bompadre, Moshe Dror, and James B. Orlin.  Improved bounds for vehicle routing solutions.  Discrete Optimization, 3(4):299–316, 2006.
  * [6] Nicos Christofides.  Worst-case analysis of a new heuristic for the travelling salesman problem.  Technical report, Carnegie-Mellon University, 1976.
  * [7] Vasek Chvatal.  A greedy heuristic for the set-covering problem.  Mathematics of Operations Research, 4(3):233–235, 1979.
  * [8] Moshe Dror and Pierre Trudeau.  Split delivery routing.  Naval Research Logistics, 37(3):383–402, 1990.
  * [9] Zachary Friggstad, Ramin Mousavi, Mirmahdi Rahgoshay, and Mohammad R. Salavatipour.  Improved approximations for capacitated vehicle routing with unsplittable client demands.  In IPCO 2022, volume 13265 of Lecture Notes in Computer Science, pages 251–261. Springer, 2022.
  * [10] Anupam Gupta, Euiwoong Lee, and Jason Li.  A local search-based approach for set covering.  In SOSA 2023, pages 1–11. SIAM, 2023.
  * [11] Mordecai Haimovich and Alexander H. G. Rinnooy Kan.  Bounds and heuristics for capacitated routing problems.  Mathematics of Operations Research, 10(4):527–542, 1985.
  * [12] Tobias Harks, Felix G. König, and Jannik Matuschke.  Approximation algorithms for capacitated location routing.  Transportation Science, 47(1):3–22, 2013.
  * [13] Refael Hassin and Asaf Levin.  A better-than-greedy approximation algorithm for the minimum set cover problem.  SIAM Journal on Computing, 35(1):189–200, 2005.
  * [14] Felipe Carrasco Heine, Antonia Demleitner, and Jannik Matuschke.  Bifactor approximation for location routing with vehicle and facility capacities.  European Journal of Operational Research, 304(2):429–442, 2023\.
  * [15] Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan.  A (slightly) improved approximation algorithm for metric TSP.  In STOC 2021, pages 32–45. ACM, 2021.
  * [16] Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan.  A deterministic better-than-3/2 approximation algorithm for metric TSP.  In IPCO 2023, volume 13904 of Lecture Notes in Computer Science, pages 261–274. Springer, 2023.
  * [17] Xiaofan Lai, Liang Xu, Zhou Xu, and Yang Du.  An approximation algorithm for k-depot split delivery vehicle routing problem.  INFORMS Journal on Computing, 2023.
  * [18] Chung-Lun Li and David Simchi-Levi.  Worst-case analysis of heuristics for multidepot capacitated vehicle routing problems.  INFORMS Journal on Computing, 2(1):64–73, 1990.
  * [19] Jairo R Montoya-Torres, Julián López Franco, Santiago Nieto Isaza, Heriberto Felizzola Jiménez, and Nilson Herazo-Padilla.  A literature review on the vehicle routing problem with multiple depots.  Computers & Industrial Engineering, 79:115–129, 2015.
  * [20] Sivakumar Rathinam, Raja Sengupta, and Swaroop Darbha.  A resource allocation algorithm for multivehicle systems with nonholonomic constraints.  IEEE Transactions on Automation Science and Engineering, 4(1):98–104, 2007.
  * [21] Anatolii Ivanovich Serdyukov.  Some extremal bypasses in graphs.  Upravlyaemye Sistemy, 17:76–79, 1978.
  * [22] Vera Traub, Jens Vygen, and Rico Zenklusen.  Reducing path TSP to TSP.  SIAM Journal on Computing, 51(3):20–24, 2022.
  * [23] David P Williamson and David B Shmoys.  The design of approximation algorithms.  Cambridge university press, 2011.
  * [24] Zhou Xu and Brian Rodrigues.  A 3/2-approximation algorithm for the multiple tsp with a fixed number of depots.  INFORMS Journal on Computing, 27(4):636–645, 2015.
  * [25] Zhou Xu, Liang Xu, and Brian Rodrigues.  An analysis of the extended christofides heuristic for the k-depot tsp.  Operations Research Letters, 39(3):218–223, 2011.
  * [26] Wei Yu and Yujie Liao.  Approximation and polynomial algorithms for multi-depot capacitated arc routing problems.  In PDCAT 2021, pages 93–100. Springer, 2021.
  * [27] Jingyang Zhao and Mingyu Xiao.  Improved approximation algorithms for capacitated vehicle routing with fixed capacity.  CoRR, abs/2210.16534, 2022.

##  Appendix A The Flaw in the Previous Algorithm

Our refined tree-partition algorithm has the same basic idea as the previous
algorithm [12]. So, in the following, we use the same notations as in
Algorithm 1. To show the flaw in the previous algorithm, we first explain two
main differences between them.

The first difference. Note that the previous algorithm did not make Assumption
2. So, a customer’s demand could be very large. To deal with customers $v\in
V$ with $d(v)\geq k$, the previous algorithm assigns $\lceil d(v)/k\rceil$
trivial tours from $v$ to its nearest depot [12], which is different from Step
1 in our algorithm.

Then, the previous algorithm generates tours based on splitting a constrained
forest $\mathcal{F}$. Similarly, it considers a tree
$\mathcal{T}_{u}\in\mathcal{F}$ rooted at $u$. If $d(T_{u})\leq k$, it also
generates a tour directly by doubling and shortcutting. For $d(T_{u})>k$, it
finds a customer $v\in T_{u}$ such that $d(T_{v})>k$ and
$d(T_{v^{\prime}})\leq k$ for every $v^{\prime}\in Q_{v}$. Then, it greedily
partitions the sub-trees in $\mathcal{T}_{v}$ into $l$ sets
$\mathcal{T}_{1},\dots,\mathcal{T}_{l}$ such that $k/2<d(\mathcal{T}_{i})\leq
k$ for each $i\in\\{2,\dots,l\\}$. It generates a single tour for each
$\mathcal{T}_{i}$ with $i\in\\{2,\dots,l\\}$ as we did in Steps 13-15 (note
that a slight difference is that we have $\lfloor
k/2\rfloor<d(\mathcal{T}_{i})\leq k$ for each $i\in\\{2,\dots,l\\}$, but it is
not the key). Then, we can explain the second difference.

The second difference. The previous algorithm takes care customers in
$\mathcal{T}_{i}$ with $i\in\\{2,\dots,l\\}$ but it ignores customers in
$\mathcal{T}_{1}$. Then, we can show the flaw in the previous algorithm.

The flaw. We may have $d(v)+d(\mathcal{T}_{1})>k$ and $d(\mathcal{T}_{1})\leq
k/2$. Let $T^{\prime}_{u}$ be the remaining tree after updating $T_{u}$ by
removing trees in $\mathcal{T}_{2}\cup\dots\cup\mathcal{T}_{l}$. It is
possible that $d(T^{\prime}_{u})>k$. As a result, the previous algorithm may
find $v$ again since $d(T^{\prime}_{v})=d(v)+d(\mathcal{T}_{1})>k$ and
$d(T_{v^{\prime}})\leq d(\mathcal{T}_{1})\leq k/2<k$ for every $v^{\prime}\in
Q^{\prime}_{v}$. However, after finding $v$ in $T^{\prime}_{u}$, the algorithm
will only get one partition $\mathcal{T}^{\prime}_{1}$ for the sub-trees
$\mathcal{T}^{\prime}_{v}=\mathcal{T}_{1}$, i.e.,
$\mathcal{T}^{\prime}_{1}=\mathcal{T}^{\prime}_{v}=\mathcal{T}_{1}$. Since it
ignores customers in $\mathcal{T}^{\prime}_{1}$, the algorithm will never
terminate.

For example, $T_{u}=uvv^{\prime}$, i.e., $T_{u}$ is a simple path on three
different vertices, where $u$ is the depot and both $v$ and $v^{\prime}$ are
customers. Moreover, we have $k=5$, $d(v)=4$, $d(v^{\prime})=2$, $d(T_{v})=6$,
and $Q_{v}=\\{v^{\prime}\\}$. Since $d(T_{u})=d(v)+d(v^{\prime})=6>k$, the
previous algorithm could find $v$ satisfying the condition: $d(T_{v})>k$ and
$d(T_{v^{\prime}})\leq k$ for every $v^{\prime}\in Q_{v}$, but then it will do
nothing since it only gets one partition.

###  A.1 The Modification

We remark that the previous algorithm can be easily modified to deal with the
flaw while keeping the upper bound in Lemma 10.

Firstly, we consider $d(\mathcal{T}_{1})>k/2$. It can be handled directly like
$\mathcal{T}_{i}$ with $i\in\\{2,\dots,l\\}$ as we did in Steps 9-11. Note
that by the proof of Theorem 11 we can get that this tour has a cost of at
most
$\frac{2}{d(\mathcal{T}_{1})}\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v)+2c(\mathcal{T}^{\prime}_{1})\leq\frac{4}{k}\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v)+2c(\mathcal{T}^{\prime}_{1})$,
which is allowed since the upper bound in Lemma 10 is $(4/k)\Delta+2c(T^{*})$.

Next, we consider $d(\mathcal{T}_{1})\leq k/2$. Note that we cannot do the
same way like $\mathcal{T}_{i}$ with $i\in\\{2,\dots,l\\}$ because the cost of
this tour would be
$\frac{2}{d(\mathcal{T}_{1})}\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v)+2c(\mathcal{T}^{\prime}_{1})>\frac{4}{k}\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v)+2c(\mathcal{T}^{\prime}_{1})$.
To deal with this case, we need to further consider $d(v)$. We may assume that
$d(v)+d(\mathcal{T}_{1})>k$; otherwise, the algorithm will not find $v$ in
$T^{\prime}_{u}$. Let $S$ denote the component obtained by adding $v$ with
edges joining $v$ and each tree in $\mathcal{T}_{1}$, and $e_{S}$ denote the
edge connecting one depot to one vertex in $S$ with minimized weight. We will
assign two tours to satisfy $v$ and all customers in $\mathcal{T}_{1}$.

  * •

For the first one, we directly assign a trivial tour (satisfying $v$) from $v$
to its nearest depot;

  * •

For the second one, we first make two copies of edges in $S$ and two copies of
edge $e_{S}$, and then obtain a tour (satisfying all customers in trees of
$\mathcal{T}_{1}$) by shortcutting.

Since $v$ will be removed after we assign these two tours, after the
modification, the algorithm will terminate. Next, we prove that the cost of
these two tours is at most $\frac{4}{k}\sum_{v^{\prime}\in
S}d(v^{\prime})c(o,v^{\prime})+2c(S)$, which is desired.

######  Lemma 26.

The cost of these two tours is at most $\frac{4}{k}\sum_{v^{\prime}\in
S}d(v^{\prime})c(o,v^{\prime})+2c(S)$.

###### Proof.

Since we have $d(S)=d(v)+d(\mathcal{T}_{1})>k$, it is sufficient to prove that
the cost of these two tours is at most $\frac{4}{d(S)}\sum_{v^{\prime}\in
S}d(v^{\prime})c(o,v^{\prime})+2c(S)$.

Clearly, the first tour has a cost of $2c(o,v)$. By the proof of Theorem 11,
the second tour has a cost of at most $2w(e_{S})+2c(S)$, where
$w(e_{S})=\min_{v^{\prime}\in
S}c(o,v^{\prime})=\min\\{c(o,v),\min_{v^{\prime}\in\mathcal{T}_{i}}c(o,v^{\prime})\\}$.
The total cost of these two tours is at most $2c(o,v)+2w(e_{S})+2c(S)$. Then,
it is sufficient to prove
$2c(o,v)+2w(e_{S})\leq\frac{4}{d(S)}\sum_{v^{\prime}\in
S}d(v^{\prime})c(o,v^{\prime})$. We consider the following two cases.

Case 1:
$c(o,v)\leq\frac{1}{d(\mathcal{T}_{1})}\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v^{\prime})$.
We can get that $d(S)c(o,v)=(d(v)+d(\mathcal{T}_{1}))c(o,v)\leq
d(v)c(o,v)+\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v^{\prime})=\sum_{v^{\prime}\in
S}d(v^{\prime})c(o,v^{\prime})$. So,
$c(o,v)\leq\frac{1}{d(S)}\sum_{v^{\prime}\in S}d(v^{\prime})c(o,v^{\prime})$.
Moreover, since $w(e_{S})=\min_{v^{\prime}\in S}c(o,v^{\prime})$, we have
$w(e_{S})\leq\frac{1}{d(S)}\sum_{v^{\prime}\in
S}d(v^{\prime})c(o,v^{\prime})$. Therefore, we have
$2c(o,v)+2w(e_{S})\leq\frac{4}{d(S)}\sum_{v^{\prime}\in
S}d(v^{\prime})c(o,v^{\prime})$.

Case 2:
$c(o,v)\geq\frac{1}{d(\mathcal{T}_{1})}\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v^{\prime})$.
We have
$w(e_{S})\leq\frac{1}{d(\mathcal{T}_{1})}\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v^{\prime})$
since $w(e_{S})\leq\min_{v^{\prime}\in\mathcal{T}_{i}}c(o,v^{\prime})$. Then,
it is sufficient to prove that
$2c(o,v)+\frac{2}{d(\mathcal{T}_{1})}\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v^{\prime})\leq\frac{4}{d(S)}\sum_{v^{\prime}\in
S}d(v^{\prime})c(o,v^{\prime})$. We can get the following reductions:

$\displaystyle
2c(o,v)+\frac{2}{d(\mathcal{T}_{1})}\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v^{\prime})$
$\displaystyle\leq\frac{4}{d(S)}\sum_{v^{\prime}\in
S}d(v^{\prime})c(o,v^{\prime})$
$\displaystyle\left(c(o,v)+\frac{1}{d(\mathcal{T}_{1})}\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v^{\prime})\right)d(S)$
$\displaystyle\leq 2\sum_{v^{\prime}\in
S}d(v^{\prime})c(o,v^{\prime})\quad(\Longleftrightarrow)$
$\displaystyle\left(c(o,v)+\frac{1}{d(\mathcal{T}_{1})}\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v^{\prime})\right)(d(v)+d(\mathcal{T}_{1}))$
$\displaystyle\leq
2\left(d(v)c(o,v)+\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v^{\prime})\right)\quad(\Longleftrightarrow)$
$\displaystyle\left(\frac{c(o,v)}{\frac{1}{d(\mathcal{T}_{1})}\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v^{\prime})}+1\right)\left(\frac{d(v)}{d(\mathcal{T}_{1})}+1\right)$
$\displaystyle\leq
2\left(\frac{d(v)}{d(\mathcal{T}_{1})}\cdot\frac{c(o,v)}{\frac{1}{d(\mathcal{T}_{1})}\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v^{\prime})}+1\right).$

Recall that $d(v)+d(\mathcal{T}_{1})>k$ and $d(\mathcal{T}_{1})\leq k/2$. So,
we have $d(v)>d(\mathcal{T}_{1})$. Moreover, we have
$\frac{c(o,v)}{\frac{1}{d(\mathcal{T}_{1})}\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v^{\prime})}\geq
1$ since we assume
$c(o,v)\geq\frac{1}{d(\mathcal{T}_{1})}\sum_{v^{\prime}\in\mathcal{T}_{1}}d(v^{\prime})c(o,v^{\prime})$
in Case 2. Then, the above inequality holds since one can verify that
$(x+1)(y+1)\leq 2(xy+1)$ holds for any $x,y\geq 1$. ∎

Although the above modification is simple, the analysis becomes a bit complex.
We remark that another possible modification is to directly assign $\lceil
d(v)/k\rceil$ trivial tours from $v$ to its nearest depot for each $v\in V$
with $d(v)>k/2$ (instead of $d(v)\geq k$ in [12]). Similar to the proof of
Theorem 11, one can prove that the tree-partition algorithm has a cost of at
most $(4/k)\Delta+2c(T^{*})$, as claimed in [12]. By a tighter analysis, one
may slightly improve this bound to $\frac{4}{k+1}\Delta+2c(T^{*})$.

###  A.2 The Limitation of the Previous Algorithm

To handle customers $v\in V$ with $d(v)\geq k$, the previous algorithm assigns
$\lceil d(v)/k\rceil$ trivial tours from $v$ to its nearest depot. If
$d(v)=k+1$, the cost of these two tours for $v$ is $4c(o,v)=\frac{4}{k+1}\cdot
d(v)c(o,v)$. The total cost for these customers could be very close to
$\frac{4}{k+1}\Delta$. According to the ‘cask effect’, it is unlikely to get
an upper bound better than $\frac{4}{k+1}\Delta+2c(T^{*})$.

##  Appendix B The Details of the LP-Based Cycle-Partition Algorithm

In this section, we fix a constant $0<\delta<1$. Consider a customer $v\in V$.
If $d(v)\geq\delta k$, we say it is _big_ ; otherwise, it is _small_. Let
$V_{b}\coloneqq\\{v\mid d(v)\geq\delta k,v\in V\\}$ be the set of big
customers and $V_{s}\coloneqq V\setminus V_{b}$ be the set of small customers.
Moreover, let $\Delta_{b}\coloneqq\sum_{v\in V_{b}}d(v)c(o,v)$ and
$\Delta_{s}\coloneqq\sum_{v\in V_{s}}d(v)c(o,v)$.

As mentioned, the LP-based cycle-partition algorithm mainly contains two
phrases. The first is to obtain a partial solution with a weight of at most
$\ln 2\cdot\mbox{OPT}$ based on randomized LP-rounding for big customers; the
second is to construct tours with an expected weight of
$\frac{1}{1-\delta}(2/k)\Delta+2c(C)$ for customers that are still
unsatisfied, where $C$ is a given Hamiltonian cycle in graph $H$. Note that
the second phrase is based on a variant of the UITP algorithm for unsplittable
$k$-CVRP, proposed in [9].

Consider the first phrase. For unsplittable $k$-MCVRP, each feasible tour
contains at most $1/\delta$ big customers. So, there are at most
$mn^{O(1/\delta)}$ feasible tours containing only big customers. Denote the
set of these tours by $\mathcal{C}$, and define a variable $x_{C}$ for each
$C\in\mathcal{C}$. We have the following LP.

minimize $\displaystyle\sum_{C\in\mathcal{C}}w(C)\cdot x_{C}$ subject to
$\displaystyle\sum_{\begin{subarray}{c}C\in\mathcal{C}:\\\ v\in
C\end{subarray}}x_{C}\geq\ $ $\displaystyle 1,\quad$ $\displaystyle\forall\
v\in V,$ $\displaystyle x_{C}\geq\ $ $\displaystyle 0,\quad$
$\displaystyle\forall\ C\in\mathcal{C}.$

Given an optimal solution of unsplittable $k$-MCVRP, one can shortcut all
small customers to obtain a solution for big customers without increasing the
weight. Since this LP considers all feasible tours on big customers, it
provides a lower bound for unsplittable $k$-MCVRP. We obtain a set of tours
$\mathcal{C}_{1}$ by randomized rounding: for each tour $C\in\mathcal{C}$, we
select it with a probability of $\min\\{\ln 2\cdot x_{C},1\\}$.

Let $\widetilde{V}$ be the left customers that are still unsatisfied.
Friggstad  _et al._ [9] proposed a variant of the UITP algorithm for
unsplittable $k$-CVRP. In the following, we call it the _$\delta$ -UITP_
algorithm. The idea of the $\delta$-UITP algorithm is still to split a
Hamiltonian cycle in graph $H$ into segments in a good way, with each
containing at most $k$ of demand, and for each segment assign two edges
between the depot $o$ and endpoints of the segment. We have the following
lemma.

######  Lemma 27 ([9]).

Given a Hamiltonian cycle $C$ in graph $H$, for unsplittable $k$-CVRP with any
constant $\delta>0$, the $\delta$-UITP algorithm can use polynomial time to
output a solution of cost at most
$\frac{1}{1-\delta}(2/k)\Delta_{s}+\frac{1}{1-\delta}(4/k)\Delta_{b}+c(C)$.

Consider the second phrase. To satisfy customers in $\widetilde{V}$, we first
construct a set of tours $\mathcal{C}_{2}$ for unsplittable $k$-CVRP by
calling the $\delta$-UITP algorithm and then modify tours in $\mathcal{C}_{2}$
into feasible tours $\mathcal{C}^{\prime}_{2}$ for unsplittable $k$-MCVRP.
Note that given a Hamiltonian cycle $C$ in graph $H$ we can obtain a
Hamiltonian cycle $\widetilde{C}$ in $H[\widetilde{V}\cup\\{o\\}]$ by
shortcutting. The modification works as follows. Note that tours of
$\mathcal{C}_{2}$ in graph $H$ correspond to a set of walks in $G$. These
walks may contain a walk $u_{s}v_{i}\dots v_{j}u_{t}$ that starts with and
ends at different depots $u_{s}$ and $u_{t}$ (the middle vertices are all
customers). This is not allowed since in $k$-MCVRP each vehicle must return to
the depot it starts. Let $w(v_{i}\dots v_{j})$ denote the sum of the weights
of edges in $v_{i}\dots v_{j}$. Note that $v_{i}\dots v_{j}$ is a segment
obtained from splitting the Hamiltonian cycle $\widetilde{C}$. We consider two
possible modifications: $u_{s}v_{i}\dots v_{j}u_{s}$ and $u_{t}v_{i}\dots
v_{j}u_{t}$, which corresponds to two feasible tours for $k$-MCVRP. By the
triangle inequality, the better one has a weight of at most
$w(u_{s},v_{i})+2w(v_{i}\dots v_{j})+w(v_{j},u_{t})$. It uses an additional
weight of the segment $v_{i}\dots v_{j}$. So, after the modification for all
these walks, we get a set of feasible tours $\mathcal{C}^{\prime}_{2}$ for
$k$-MCVRP using an additional cost of the Hamiltonian cycle $\widetilde{C}$.

The LP-based cycle-partition algorithm is shown in Algorithm 3.

Algorithm 3 An LP-based cycle-partition algorithm for unsplittable $k$-MCVRP

Input: Two undirected complete graphs: $G=(V\cup D,E)$ and
$H=(V\cup\\{o\\},F)$, a Hamiltonian cycle $C$ in graph $H$, and a constant
$\delta>0$.
Output: A solution for unsplittable $k$-MCVRP.

1:Solve the LP in $mn^{O(1/\delta)}$ time.

2:for $C^{\prime}\in\mathcal{C}$ do Put the tour $C^{\prime}$ into solution
with a probability of $\min\\{\gamma\cdot x_{C^{\prime}},1\\}$.

3:end for

4:For each customer contained in multiple tours, we shortcut it for all but
one tour. $\triangleright$ Some customers may be contained in more than one
tour due to the randomized rounding.

5:Let $\widetilde{V}$ be the customers that are still unsatisfied.

6:Obtain two new complete graphs: $\widetilde{G}=G[\widetilde{V}\cup D]$ and
$\widetilde{H}=G[\widetilde{V}\cup\\{o\\}]$, and a Hamiltonian cycle
$\widetilde{C}$ in $\widetilde{H}$ by shortcutting $C$.

7:Call the $\delta$-UITP algorithm with $\widetilde{C}$ in Lemma 27 to obtain
a set of tours $\mathcal{C}_{2}$ in $H$ for unsplittable $k$-CVRP.

8:Obtain a set of minimal walks $\mathcal{W}$ that starts with and ends at
depots in $\widetilde{G}$ with respect to $\mathcal{C}_{2}$. $\triangleright$
each walk in $\mathcal{W}$ contains only two depots

9:while $W=u_{s}v_{i}\dots v_{j}u_{t}\in\mathcal{W}$ such that $u_{s}$ and
$u_{t}$ are different depots do

10: Modify it into the better from $u_{s}v_{i}\dots v_{j}u_{s}$ and
$u_{t}v_{i}\dots v_{j}u_{t}$.

11:end while

12:Obtain a set of feasible tours $\mathcal{C}^{\prime}_{2}$ in graph $G$ with
respect to $\mathcal{W}$, and put them into solution.

Denote the set of tours obtained by the randomized LP-rounding method by
$\mathcal{C}_{1}$. The total cost of the LP-based cycle-partition algorithm is
$w(\mathcal{C}_{1})+w(\mathcal{C}^{\prime}_{2})$. Next, we analyze
$\mathcal{C}_{1}$ and $\mathcal{C}^{\prime}_{2}$.

######  Lemma 28.

It holds that $\mathbb{E}[w(\mathcal{C}_{1})]\leq\ln 2\cdot\mbox{OPT}$.

###### Proof.

Recall that LP provides a lower bound of unsplittable $k$-MCVRP. Then,
$\sum_{C\in\mathcal{C}}x_{C}\cdot w(C)\leq\mbox{OPT}$. Each tour
$C\in\mathcal{C}$ is chosen with a probability of at most $\ln 2\cdot x_{C}$.
So, the chosen tours have an expected weight of at most
$\sum_{C\in\mathcal{C}}\ln 2\cdot x_{C}\cdot w(C)\leq\ln 2\cdot\mbox{OPT}$.
The shortcutting in Step 4 will not increase the weight by the triangle
inequality. So, we have $\mathbb{E}[w(\mathcal{C}_{1})]\leq\ln
2\cdot\mbox{OPT}$. ∎

######  Lemma 29.

It holds that $\mbox{Pr}[v\in\widetilde{V}\mid v\in V_{s}]=1$ and
$\mbox{Pr}[v\in\widetilde{V}\mid v\in V_{b}]\leq 1/2$.

###### Proof.

Clearly, small customers are still not satisfied since tours in LP are only
for big customers. Hence, $\mbox{Pr}[v\in\widetilde{V}\mid v\in V_{s}]=1$.
Consider a big customer $v\in V_{b}$. Let $\mathcal{C}_{v}$ be the set of
tours in $\mathcal{C}$ that contain $v$. Note that
$\sum_{v\in\mathcal{C}_{v}}x_{C}\geq 1$ by the definition of LP. So, we have
$\mbox{Pr}[v\in\widetilde{V}\mid v\in
V_{b}]=\prod_{C\in\mathcal{C}_{v}}\mbox{Pr}[C~{}\mbox{is}~{}\mbox{not}~{}\mbox{chosen}]\leq\prod_{C\in\mathcal{C}_{v}}(1-\ln
2\cdot x_{C})\leq e^{-\sum_{C\in\mathcal{C}_{v}}\ln 2\cdot x_{C}}\leq e^{-\ln
2}=1/2$. ∎

######  Lemma 30.

It holds that
$\mathbb{E}[w(\mathcal{C}^{\prime}_{2})]\leq\frac{1}{1-\delta}\Delta+2c(C)$.

###### Proof.

Recall that $\widetilde{C}$ is obtained by shortcutting $C$ and tours in
$\mathcal{C}^{\prime}_{2}$ are obtained by modifying tours in
$\mathcal{C}_{2}$ using an additional cost of $c(\widetilde{C})$. We have
$w(\mathcal{C}^{\prime}_{2})\leq c(\mathcal{C}_{2})+c(\widetilde{C})\leq
c(\mathcal{C}_{2})+c(C)$. By Lemmas 27 and 29,
$\mathbb{E}[c(\mathcal{C}_{2})]\leq\frac{1}{1-\delta}(2/k)\sum_{v\in
V_{s}}d(v)c(o,v)\cdot\mbox{Pr}[v\in\widetilde{V}\mid v\in
V_{s}]+\frac{1}{1-\delta}(4/k)\sum_{v\in
V_{b}}d(v)c(o,v)\cdot\mbox{Pr}[v\in\widetilde{V}\mid v\in
V_{b}]+c(C)\leq\frac{1}{1-\delta}(2/k)\Delta_{s}+\frac{1}{1-\delta}(2/k)\Delta_{b}+c(C)$.
Note that $\Delta_{s}+\Delta_{b}=\Delta$. Then, we have
$\mathbb{E}[w(\mathcal{C}^{\prime}_{2})]\leq\frac{1}{1-\delta}(2/k)\Delta+2c(C)$.
∎

We remark that the algorithm can be derandomized efficiently by the method of
conditional expectations [23]. By Lemmas 28 and 30, for unsplittable $k$-MCVRP
with any constant $0<\delta<1$, the LP-based cycle-partition algorithm has an
expected weight of at most $\ln
2\cdot\mbox{OPT}+\frac{1}{1-\delta}(2/k)\Delta+2c(C)$, which implies the
result in Theorem 16.

##  Appendix C Proof of Theorem 24

###### Proof.

We may assume that in the worst case we have $\left(\frac{2}{\lfloor
k/2\rfloor+1}\left(\frac{k+2}{2}-\sum_{i=1}^{m^{\prime}}ix_{i}\right)\right)\geq
1$. Otherwise, it is easy to verify that we can set $\gamma=0$ for the LP-
based tree-partition algorithm to obtain a much better result than that in
Theorem 24. In the following, we set $\gamma=\ln\left(\frac{2}{\lfloor
k/2\rfloor+1}\left(\frac{k+2}{2}-\sum_{i=1}^{m^{\prime}}ix_{i}\right)\right)$.
So, the approximation ratio becomes

$\max_{\begin{subarray}{c}x_{1},x_{2},\dots,x_{m^{\prime}}\geq 0\\\
x_{1}+x_{2}+\dots+x_{m^{\prime}}=1\end{subarray}}\left\\{1+\ln\left(\frac{2}{\lfloor
k/2\rfloor+1}\left(\frac{k+2}{2}-\sum_{i=1}^{m^{\prime}}ix_{i}\right)\right)+2\left(1-\frac{1}{2}\max_{1\leq
i\leq m^{\prime}}x_{i}\right)\right\\}.$

Zhao and Xiao [27] proved that in the worst case we have $x_{1}\geq
x_{2}=\cdots=x_{l}=\frac{1-x_{1}}{l-1}$ and $x_{i}=0$ for each $l<i\leq
m^{\prime}$, where $l=\lceil\frac{1}{x_{1}}\rceil\leq m^{\prime}$. So,
$\max_{1\leq i\leq m^{\prime}}x_{i}=x_{1}$ and
$\sum_{i=1}^{m^{\prime}}ix_{i}=x_{1}+\sum_{i=2}^{l}i\frac{1-x_{1}}{l-1}=\frac{l}{2}(1-x_{1})+1$.
The approximation ratio becomes

$\max_{\begin{subarray}{c}0<x_{1}\leq 1\\\ \lceil 1/x_{1}\rceil\leq
m^{\prime}\end{subarray}}\left\\{3+\ln\left(\frac{k-(1-x_{1})\left\lceil\frac{1}{x_{1}}\right\rceil}{\lfloor
k/2\rfloor+1}\right)-x_{1}\right\\}.$

Let

$f(x)\coloneqq
3+\ln\left(\frac{k-(1-x)\left\lceil\frac{1}{x}\right\rceil}{\lfloor
k/2\rfloor+1}\right)-x,\quad
x\in(0,1],\quad\left\lceil\frac{1}{x}\right\rceil\leq m^{\prime}.$

Assume that $f(x_{0})=\max_{0<x\leq 1}f(x)$, i.e., the approximation ratio.
For $k=3$, it is easy to see that $\max_{0<x\leq 1}f(x)=2.5$. The result in
Theorem 24 holds. So, we may consider $k\geq 4$ in the following.

For any $k\geq 4$, we will first show that $1/x_{0}$ must be an integer. Then,
let

$g(x)\coloneqq 3+\ln\left(\frac{k-(1-\frac{1}{x})x}{\lfloor
k/2\rfloor+1}\right)-\frac{1}{x}=3+\ln\left(\frac{k+1-x}{\lfloor
k/2\rfloor+1}\right)-\frac{1}{x},\quad x\geq 1.$

We can determine $\max_{x\in\mathbb{Z}_{\geq 1}}g(x)$, which is an upper bound
of the approximation ratio $f(x_{0})$. Then, we can get the result in Theorem
24.

######  Claim 31.

$1/x_{0}$ must be an integer.

###### Proof.

Consider $x\in[\frac{1}{u+1},\frac{1}{u})$, where $u\in\mathbb{Z}_{\geq 1}$.
We have $\lceil\frac{1}{x}\rceil=u+1$. We can get

$f^{\prime}(x)=\frac{u+1}{k-(1-x)(u+1)}-1,\quad
x\in\left[\frac{1}{u+1},\frac{1}{u}\right).$

It is easy to see that there are three cases for $f^{\prime}(x)$.

Case 1. $f^{\prime}(x)\geq 0$ for $x\in[\frac{1}{u+1},\frac{1}{u})$: We will
show that $x_{0}\notin[\frac{1}{u+1},\frac{1}{u})$.

In this case, for $x\in[\frac{1}{u+1},\frac{1}{u})$, we have
$f(x)\leq\lim_{x\rightarrow(\frac{1}{u})^{-}}f(x)$. By $f(x)$, it is easy to
see that
$\lim_{x\rightarrow(\frac{1}{u})^{-}}f(x)<\lim_{x\rightarrow(\frac{1}{u})^{+}}f(x)=f(\frac{1}{u})$.
Hence, $x_{0}\notin[\frac{1}{u+1},\frac{1}{u})$.

Case 2. $f^{\prime}(x)\leq 0$ for $x\in[\frac{1}{u+1},\frac{1}{u})$: We will
show that $1/x_{0}$ is an integer if $x_{0}\in[\frac{1}{u+1},\frac{1}{u})$.

In this case, for $x\in[\frac{1}{u+1},\frac{1}{u})$, we have $f(x)\leq
f(\frac{1}{u+1})$. It is easy to see that $1/x_{0}=u+1$ if
$x_{0}\in[\frac{1}{u+1},\frac{1}{u})$.

Case 3. $f^{\prime}(x)\geq 0$ for $x\in[\frac{1}{u+1},x_{u}]$ and
$f^{\prime}(x)\leq 0$ for $[x_{u},\frac{1}{u})$, where
$\frac{1}{u+1}<x_{u}<\frac{1}{u}$: We will show that
$f(x_{u})<f(\frac{1}{u})$, and hence $x_{0}\notin[\frac{1}{u+1},\frac{1}{u})$.

In this case, we have $f^{\prime}(x_{u})=0$. Then, we have
$x_{u}=2-\frac{k}{u+1}$. Note that $\lceil\frac{1}{x}\rceil=u+1\leq
m^{\prime}=\lceil\frac{k+1}{2}\rceil$. Then,
$u\leq\lceil\frac{k+1}{2}\rceil-1\leq\frac{k}{2}$. Moreover, since
$x_{u}\geq\frac{1}{u+1}$, we have

$\frac{k}{2}\geq u\geq\frac{k-1}{2}.$

It is easy to see that $f(x_{u})\leq
f^{\prime}(\frac{1}{u+1})(x_{u}-\frac{1}{u+1})+f(\frac{1}{u+1})\leq
f^{\prime}(\frac{1}{u+1})(\frac{1}{u}-\frac{1}{u+1})+f(\frac{1}{u+1})$ since
$f(x)$ is a concave function for $x\in[\frac{1}{u+1},\frac{1}{u})$. To prove
$f(x_{u})<f(\frac{1}{u})$, it is sufficient to prove

$f^{\prime}(\frac{1}{u+1})\left(\frac{1}{u}-\frac{1}{u+1}\right)+f(\frac{1}{u+1})<f(\frac{1}{u}),\quad\frac{k-1}{2}\leq
u\leq\frac{k}{2}.$

By $f(x)$ and $f^{\prime}(x)$, it is sufficient to prove

$\ln\left(1+\frac{1}{k-u}\right)-\frac{1}{(k-u)u}>0,\quad\frac{k-1}{2}\leq
u\leq\frac{k}{2}.$

Hence, it is sufficient to prove
$\ln(1+\frac{1}{k-u_{0}})-\frac{1}{u_{0}(k-u_{0})}>0$, where
$u_{0}=\frac{k-1}{2}$. Note that $\ln(1+x)>x(1-\frac{x}{2})$ for $0<x<1$.
Since $0<\frac{1}{k-u_{0}}<1$, we have
$\ln(1+\frac{1}{k-u_{0}})>\frac{1}{k-u_{0}}(1-\frac{1}{2(k-u_{0})})$.
Moreover, since $k\geq 4$, we have
$\frac{1}{u_{0}}=\frac{2}{k-1}\leq\frac{2}{3}$ and
$\frac{1}{2(k-u_{0})}=\frac{1}{k+1}\leq\frac{1}{5}$. Hence, we have

$\ln\left(1+\frac{1}{k-u_{0}}\right)>\frac{1}{k-u_{0}}\left(1-\frac{1}{2(k-u_{0})}\right)>\frac{1}{k-u_{0}}\left(\frac{2}{3}+\frac{1}{5}-\frac{1}{2(k-u_{0})}\right)\geq\frac{1}{u_{0}(k-u_{0})}.$

According to the above three cases, we know that the claim holds. ∎

Then, we are ready to calculate $\max_{x\in\mathbb{Z}_{\geq 1}}g(x)$, which is
an upper bound of the approximation ratio by the claim. We have

$g^{\prime}(x)=\frac{-1}{k+1-x}+\frac{1}{x^{2}}.$

When $x=x_{0}\coloneqq\frac{\sqrt{4k+5}-1}{2}$, we can get that
$g^{\prime}(x)=0$. So, $\max_{x\in\mathbb{Z}_{\geq 1}}g(x)=\max\\{g(\lceil
x_{0}\rceil),g(\lfloor x_{0}\rfloor)\\}$.

Note that we can determine the value $\gamma$ as follows: if
$\max_{x\in\mathbb{Z}_{\geq 1}}g(x)=g(\lceil x_{0}\rceil)$, let
$x^{*}\coloneqq\frac{1}{\lceil x_{0}\rceil}$; otherwise, let
$x^{*}\coloneqq\frac{1}{\lfloor x_{0}\rfloor}$. $x^{*}$ is the value of
$x_{1}$ in the worst case. Then, we get
$\gamma=\ln\left(\frac{k+1-\frac{1}{x^{*}}}{\lfloor k/2\rfloor+1}\right)$. ∎

##  Appendix D The Function

The function $f:\mathbb{R}_{>0}\rightarrow\mathbb{R}_{>0}$, given in [4],
satisfies that

$f(\varepsilon)=\min_{\begin{subarray}{c}0<\theta\leq 1-\tau\\\
0<\tau,\rho\leq
1/6\end{subarray}}\left\\{\frac{1+\zeta}{\theta}+\frac{1-\tau-\theta}{\theta\cdot(1-\tau)}+\frac{3\varepsilon}{1-\theta}+\frac{3\rho}{(1-\rho)\cdot(1-\tau)}\right\\}-1,$

where $\theta$ is let to be $1-\tau$ in [4] and

$\zeta=\frac{3\rho+\tau-4\tau\cdot\rho}{1-\rho}+\frac{\varepsilon}{\tau\cdot\rho}\cdot\left(1-\tau\cdot\rho-\frac{3\rho+\tau-4\tau\cdot\rho}{1-\rho}\right).$