# A Tight $(1.5+\epsilon)$-Approximation for
Unsplittable Capacitated Vehicle Routing on Trees

Claire Mathieu111CNRS, Paris, France, e-mail<EMAIL_ADDRESS>Hang
Zhou222Ecole Polytechnique, Institut Polytechnique de Paris, France, e-mail:
<EMAIL_ADDRESS>
###### Abstract

In the unsplittable capacitated vehicle routing problem (UCVRP) on trees, we
are given a rooted tree with edge weights and a subset of vertices of the tree
called terminals. Each terminal is associated with a positive demand between 0
and 1. The goal is to find a minimum length collection of tours starting and
ending at the root of the tree such that the demand of each terminal is
covered by a single tour (i.e., the demand cannot be split), and the total
demand of the terminals in each tour does not exceed the capacity of 1.

For the special case when all terminals have equal demands, a long line of
research culminated in a quasi-polynomial time approximation scheme
[Jayaprakash and Salavatipour, SODA 2022] and a polynomial time approximation
scheme [Mathieu and Zhou, ICALP 2022].

In this work, we study the general case when the terminals have arbitrary
demands. Our main contribution is a polynomial time
$(1.5+\epsilon)$-approximation algorithm for the UCVRP on trees. This is the
first improvement upon the 2-approximation algorithm more than 30 years ago
[Labbé, Laporte, and Mercure, Operations Research, 1991]. Our approximation
ratio is essentially best possible, since it is NP-hard to approximate the
UCVRP on trees to better than a 1.5 factor.

##  1 Introduction

In the _unsplittable capacitated vehicle routing problem (UCVRP)_ on _trees_ ,
we are given a rooted tree with edge weights and a subset of vertices of the
tree called _terminals_. Each terminal is associated with a positive _demand_
between 0 and 1. The root of the tree is called the _depot_. The goal is to
find a minimum length collection of tours starting and ending at the depot
such that the demand of each terminal is covered by a _single_ tour (i.e., the
demand cannot be split), and the total demand of the terminals in each tour
does not exceed the _capacity_ of 1.

The UCVRP on trees has been well studied in the special setting when all
terminals have _equal_ demands:333Up to scaling, the equal demand setting is
equivalent to the _unit demand_ version of the capacitated vehicle routing
problem in which each terminal has unit demand, and the capacity of each tour
is a positive integer $k$. Hamaguchi and Katoh [HK98] gave a polynomial time
1.5-approximation; the approximation ratio was improved to $1.35078$ by Asano,
Katoh, and Kawashima [AKK01] and was further reduced to $4/3$ by Becker
[Bec18]; Becker and Paul [BP19] gave a bicriteria polynomial time
approximation scheme; and very recently, Jayaprakash and Salavatipour [JS22]
gave a quasi-polynomial time approximation scheme, based on which Mathieu and
Zhou [MZ22] designed a polynomial time approximation scheme.

In this work, we study the UCVRP on trees in the general setting when the
terminals have _arbitrary_ demands. Our main contribution is a polynomial time
$(1.5+\epsilon)$-approximation algorithm (Theorem 1). This is the first
improvement upon the 2-approximation algorithm of Labbé, Laporte, and Mercure
[LLM91] more than 30 years ago. Our approximation ratio is essentially best
possible, since it is NP-hard to approximate the UCVRP on trees to better than
a 1.5 factor [GW81].

######  Theorem 1.

For any $\epsilon>0$, there is a polynomial time
$(1.5+\epsilon)$-approximation algorithm for the unsplittable capacitated
vehicle routing problem on trees.

The UCVRP on trees generalizes the UCVRP on _paths_. The latter problem has
been studied extensively due to its applications in scheduling, see Section
1.1. Previously, the best approximation ratio for the UCVRP on paths was 1.6
due to Wu and Lu [WL20]. As an immediate corollary of Theorem 1, we obtain a
polynomial time $(1.5+\epsilon)$-approximation algorithm for the UCVRP on
paths. This ratio is essentially best possible, since it is NP-hard to
approximate the UCVRP on paths to better than a 1.5 factor (Section A.1).

###  1.1 Related Work

##### UCVRP on paths.

The UCVRP on paths is equivalent to the scheduling problem of minimizing the
makespan on a single batch processing machine with non-identical job sizes
[Uzs94]. Many heuristics have been proposed and evaluated empirically, e.g.,
[Uzs94, DDF02, MDC04, DMS06, KKJ06, PKK10, CDH11, AS15, Mut20].

The UCVRP on paths has also been studied in special cases. For example, in the
special case when the optimal value is at least $\Omega(1/\epsilon^{6})$ times
the maximum distance between any terminal and the depot, asymptotic polynomial
time approximation schemes are known [DMM10, Rot12, CGHI13].444The UCVRP on
paths is called the _train delivery problem_ in [DMM10, Rot12, CGHI13]. In
contrast, the algorithm in Theorem 1 applies to any path instance (and more
generally any tree instance).

##### UCVRP on general metrics.

The first constant-factor approximation algorithm for the UCVRP on general
metrics is due to Altinkemer and Gavish [AG87]. The approximation ratio was
only recently improved in work by Blauth, Traub, and Vygen [BTV21], and then
further by Friggstad, Mousavi, Rahgoshay, and Salavatipour [FMRS22], so that
the best-to-date approximation ratio stands at roughly $3.194$ [FMRS22].

##  2 Overview of Techniques

At a high level, our approach is to modify the problem and add enough
structural constraints so that the structured problem contains a
$(1.5+O(\epsilon))$-approximate solution and can be solved in polynomial time
by dynamic programming.

###  2.1 Preprocessing

We start by some preprocessing as in [MZ22]. We assume without loss of
generality that every vertex in the tree has two children, and the terminals
are the leaf vertices of the tree [MZ22]. Furthermore, we assume that the tree
has bounded distances (Section 3.1). Next, we decompose the tree into
_components_ (Fig. 1 and Section 3.2).

Figure 1: Decomposition of the tree into _components_. Figure extracted from
[MZ22]. Each brown triangle represents a _component_. Each component has a
_root_ vertex and at most one _exit_ vertex.

(a) Decomposition of a component into _blocks_. The orange nodes represent the
_big_ terminals in the component. The black nodes represent the _root_ and the
_exit_ vertices of the component (defined in Lemma 6). The gray nodes are the
branching vertices in the subtree spanning the orange and the black nodes.
Splitting the component at the orange, the black, and the gray nodes results
in a set of _blocks_ , represented by green triangles. Each block has a _root_
vertex and at most one _exit_ vertex. See Section 4.1.

(b) Decomposition of a block into _clusters_. The green triangle represents a
block. Each blue triangle represents a _cluster_. Each cluster has a _root_
vertex and at most one _exit_ vertex. A cluster is _passing_ if it has an exit
vertex, and is _ending_ otherwise. Each passing cluster has a _spine_
(dashed). See Section 4.2.

(c) Decomposition of a passing cluster into _cells_. The blue triangle
represents a passing cluster. Removing the thick edges from the cluster
results in a set of at most $1/\epsilon$ _cells_. Each red triangle represents
a cell. Each of those cells has a _root_ vertex, an _exit_ vertex, and a
_spine_ (dashed). See Section 4.3.

Figure 2: Three-level decomposition of a component.

###  2.2 Solutions Within Each Component

A significant difficulty is to compute solutions within each component. It
would be natural to attempt to extend the approach in the setting when all
terminals have equal demands [MZ22]. In that setting, the _demands of the
subtours_ 555The _demand of a subtour_ is the total demand of the terminals
visited by that subtour. in each component are among a polynomial number of
values; since the component is visited by a constant number of tours in a
near-optimal solution, that solution inside the component can be computed
exactly in polynomial time using a simple dynamic program. However, when the
terminals have arbitrary demands, the demands of the subtours in each
component might be among an exponential number of values.666For example,
consider a component that is a star graph with $\Theta(n)$ leaves, where the
$i^{\rm th}$ leaf has demand $1/2^{i}$. Indeed, unless $P=NP$, we cannot
compute in polynomial time a better-than-$1.5$ approximate solution inside a
component, since that problem generalizes the bin packing problem (Section
A.2).

To compute in polynomial time good approximate solutions within each
component, at a high level, we simplify the solution structure in each
component, so that the demands of the subtours in that component are among a
_constant_ $O_{\epsilon}(1)$ number of values, while increasing the cost of
the solution by at most a multiplicative factor $1.5+O(\epsilon)$.

Where does the $1.5$ factor come from? Intuitively, our construction creates
an additional subtour to cover a selected subset of terminals, charging each
edge on that subtour to _two_ existing subtours using that edge, thus adding a
$0.5$ factor to the cost.

In the rest of this section, we explain our approach in more details.

####  2.2.1 Multi-Level Decomposition (Section 4)

First, we distinguish _big_ and _small_ terminals depending on their demands.
The number of big terminals in a component is $O_{\epsilon}(1)$. Next, we
partition the small terminals of a component into $O_{\epsilon}(1)$ parts
using a _multi-level decomposition_ as follows. In the first level, a
component is decomposed into $O_{\epsilon}(1)$ _blocks_ so that all terminals
strictly inside a block are small; see Figs. 2(a) and 4.1. In the second
level, each block is decomposed into $O_{\epsilon}(1)$ _clusters_ so that the
overall demand of each cluster is roughly an $\epsilon$ fraction of the demand
of a component; see Figs. 2(b) and 4.2. Intuitively, the clusters are such
that, _if_ we assign the small terminals of each cluster to a single subtour,
the subtour capacities would be violated only slightly. We define the _spine_
of a cluster to be the path traversing that cluster. In the third level, each
cluster is decomposed into $O_{\epsilon}(1)$ _cells_ so that the spine of each
cell is roughly an $\epsilon$ fraction of the spine of a cluster; see Figs.
2(c) and 4.3.

Figure 3: Relation of the multiple levels in the decomposition.

####  2.2.2 Simplifying the Local Solution (Section 5)

The main technical contribution in this paper is the Local Theorem (Theorem
12), which simplifies a local solution inside a component so that, _in each
cell, a single subtour visits all small terminals_ , while increasing the cost
of the local solution by at most a multiplicative factor $1.5+O(\epsilon)$.
The Local Theorem builds upon techniques from [MZ22] together with substantial
new ideas.

A first attempt is to combine all subtours of a cluster into a single subtour.
However, there are two obstacles. First, the resulting subtours in the
component are no longer connected; reconnecting those subtours would require
including the spines of the clusters, which would be too expensive. Secondly,
the resulting subtours in the component may exceed their capacities, so an
extra cost is needed to reduce the demands of those subtours; in the equal
demand setting [MZ22], that extra cost is at most an $\epsilon$ fraction of
the solution cost, but this is no longer the case in the arbitrary demand
setting.

We overcome those obstacles thanks to the decomposition of a cluster into
_cells_. In the analysis, we introduce the technical concept of _threshold
cells_ (Fig. 4(a)), and we ensure that each cluster contains _at most one_
threshold cell. A crucial step is to _include the spine subtour of the
threshold cell_ into the solution (Fig. 4(b)). This enables us to reassign all
small terminals of each cell to a single subtour, without losing connectivity,
while only slightly violating the subtour capacities.

To reduce the demand of each subtour exceeding capacity, we select some cells
from that subtour, and we remove all pieces in that subtour belonging to those
cells. We show that each removed piece is connected to the root through at
least _two_ subtours in the solution (Lemma 18, see Fig. 5). That property is
a main technical novelty in this paper. It enables us to reconnect all removed
pieces with an extra cost of at most _half_ of the solution cost (Lemma 19),
hence an approximation ratio of $1.5+O(\epsilon)$.

###  2.3 Postprocessing

As in [MZ22], we modify the tree so that it has only $O_{\epsilon}(1)$ levels
of components; see Section 6. Consider a near-optimal solution in the
resulting tree (Theorem 24). After applying the Local Theorem (Theorem 12) to
simplify the local solutions in all components, we obtain a global solution
(Theorem 27); see Section 7. We observe that the possible subtour demands in
that global solution are within a polynomial number of values (29).
Furthermore, we leverage the _adaptive rounding_ technique due to Jayaprakash
and Salavatipour [JS22] and we show that, in each subtree, the subtour demands
are among a constant $O_{\epsilon}(1)$ number of values (Theorem 31); see
Section 8.

Finally, we design a polynomial time dynamic program to compute the best
solution that satisfies the structural constraints established previously. The
computed solution is a $(1.5+O(\epsilon))$-approximation. See Section 9.

######  Remark 2.

For more general metrics, such as graphs of bounded treewidth and the
Euclidean space, it is challenging to simplify the solution structure due to
the lack of the _unique_ spine in a subproblem. It is an open question to
design optimal approximation algorithms in those metrics.

##  3 Preliminaries

Let $T$ be a rooted tree $(V,E)$ with edge weights $w(u,v)\geq 0$ for all
$(u,v)\in E$. Let $n$ denote the number of vertices in $V$. The _cost_ of a
tour (resp. a subtour) $t$, denoted by $\mathrm{cost}(t)$, is the overall
weight of the edges on $t$. For a set $S$ of tours (resp. subtours), the
_cost_ of $S$, denoted by $\mathrm{cost}(S)$, is $\sum_{t\in
S}\mathrm{cost}(t)$.

######  Definition 3 (UCVRP on trees).

An instance of the _unsplittable capacitated vehicle routing problem (UCVRP)_
on _trees_ consists of

  * •

an edge weighted _tree_ $T=(V,E)$ with _root_ $r\in V$ representing the
_depot_ ,

  * •

a set $V^{\prime}\subseteq V$ of _terminals_ ,

  * •

for each terminal $v\in V^{\prime}$, a _demand_ of $v$, denoted by
$\mathrm{demand}(v)$, which belongs to $(0,1]$.

A feasible solution is _a set of tours_ such that

  * •

each tour starts and ends at $r$,

  * •

the demand of each terminal is covered by a _single_ tour,

  * •

the total demand of the terminals covered by each tour does not exceed the
_capacity_ of 1.

The goal is to find a feasible solution of minimum cost.

For any two vertices $u,v\in V$, let $\mathrm{dist}(u,v)$ denote the distance
between $u$ and $v$ in the tree $T$.

We say that a tour (resp. a subtour) _visits_ a terminal if it covers the
demand of that terminal. For technical reasons, we allow _dummy_ terminals of
appropriate demands to be included artificially. The _demand_ of a tour (resp.
a subtour) $t$, denoted by $\mathrm{demand}(t)$, is defined to be the total
demand of all terminals (including dummy terminals) visited by $t$.

###  3.1 Reduction to Bounded Distance Instances

######  Definition 4 (Definition 3 in [MZ22]).

Let $D_{\min}$ (resp. $D_{\max}$) denote the minimum (resp. maximum) distance
between the depot and any terminal in the tree $T$. We say that $T$ has
_bounded distances_ if $D_{\max}<(1/\epsilon)^{(1/\epsilon)-1}\cdot D_{\min}.$

The next theorem (Theorem 5) enables us to assume without loss of generality
that the tree $T$ has bounded distances.

######  Theorem 5 (Theorem 5 in [MZ22]).

For any $\rho\geq 1$, if there is a polynomial time $\rho$-approximation
algorithm for the UCVRP on trees with _bounded distances_ , then there is a
polynomial time $(1+5\epsilon)\rho$-approximation algorithm for the UCVRP on
trees with _general distances_.

###  3.2 Decomposition Into Components (Fig. 1)

We decompose the tree $T$ into components as in [MZ22].

######  Lemma 6 (Lemma 9 in [MZ22]).

Let $\Gamma=12/\epsilon$. There is a polynomial time algorithm to compute a
partition of the edges of the tree $T$ into a set $\mathcal{C}$ of
_components_ , such that all of the following properties are satisfied:

  1. 1.

Every component $c\in\mathcal{C}$ is a connected subgraph of $T$; the _root_
vertex of the component $c$, denoted by $r_{c}$, is the vertex in $c$ that is
closest to the depot.

  2. 2.

A component $c$ shares vertices with other components at vertex $r_{c}$ and
possibly at one other vertex, called the _exit_ vertex of the component $c$
and denoted by $e_{c}$. We say that $c$ is an _internal_ component if $c$ has
an exit vertex, and is a _leaf_ component otherwise.

  3. 3.

The total demand of the terminals in each component $c\in\mathcal{C}$ is at
most $2\Gamma$.

  4. 4.

The number of components in $\mathcal{C}$ is at most
$\max\\{1,3\cdot\mathrm{demand}(T)/\Gamma\\}$, where $\mathrm{demand}(T)$
denotes the total demand of the terminals in the tree $T$.

######  Definition 7 ([MZ22]).

Let $c\in\mathcal{C}$ be any component. A _subtour in component $c$_ is a path
$t$ that starts and ends at the root $r_{c}$ of component $c$, and such that
every vertex on $t$ is in component $c$. We say that $t$ is a _passing
subtour_ if $c$ has an exit vertex and that vertex belongs to $t$, and is an
_ending subtour_ otherwise.

##  4 Multi-Level Decomposition in a Component

Let $c\in\mathcal{C}$ be any component. We distinguish _big_ and _small_
terminals in $c$ depending on their demands.

######  Definition 8 (big and small terminals).

Let $\alpha=\epsilon^{(1/\epsilon)+1}$. Let
$\Gamma^{\prime}=\epsilon\cdot\alpha/\Gamma$, where $\Gamma$ is defined in
Lemma 6. We say that a terminal $v$ is _big_ if
$\mathrm{demand}(v)>\Gamma^{\prime}$ and _small_ otherwise.

We partition the _small_ terminals in $c$ using a _multi-level decomposition_
: first, the component $c$ is decomposed into _blocks_ (Section 4.1); next,
each block is decomposed into _clusters_ (Section 4.2); and finally, each
cluster is decomposed into _cells_ (Section 4.3).

We introduce some common notations for blocks, clusters, and cells. Each block
(resp. cluster or cell) has a _root_ vertex and at most one _exit_ vertex. We
say that a terminal $v$ is _strictly_ inside a block (resp. cluster or cell)
if $v$ belongs to the block (resp. cluster or cell) and, in addition, $v$ is
different from the root vertex and the exit vertex of the block (resp. cluster
or cell). Note that any terminal strictly inside a block (resp. cluster or
cell) is small. The _demand_ of a block (resp. cluster or cell) is defined as
the total demand of all terminals _strictly_ inside that block (resp. cluster
or cell). We say that a block (resp. cluster or cell) is _passing_ if it has
an exit vertex and is _ending_ otherwise. The _spine_ of a passing block
(resp. passing cluster or passing cell) is the path between the root vertex
and the exit vertex of that block (resp. cluster or cell).

###  4.1 Decomposition of a Component Into Blocks (Fig. 2(a))

Let $c$ be any component. Let $U\subseteq V$ denote the set of vertices
consisting of the big terminals in $c$, the _root_ vertex of $c$, and possibly
the _exit_ vertex of $c$ if $c$ is an _internal_ component (see Lemma 6 for
definitions). Let $T_{U}$ denote the subtree of $c$ spanning the vertices in
$U$. We say that a vertex in $T_{U}$ is a _key_ vertex if either it belongs to
$U$ or it has two children in $T_{U}$. We define a _block_ to be a maximally
connected subgraph of component $c$ in which any key vertex has degree 1; in
other words, blocks are obtained by splitting the component at the key
vertices. The blocks form a partition of the edges of component $c$.

###  4.2 Decomposition of a Block Into Clusters (Fig. 2(b))

As an adaptation from Lemma 6, we decompose a block into clusters in Lemma 9.

######  Lemma 9.

Let $b$ be any block. There is a polynomial time algorithm to compute a
partition of the edges of the block $b$ into a set of _clusters_ , such that
all of the following properties are satisfied:

  1. 1.

Every cluster $x$ is a connected subgraph of $b$; the _root_ vertex of the
cluster $x$, denoted by $r_{x}$, is the vertex in $x$ that is closest to the
depot.

  2. 2.

A cluster $x$ shares vertices with other clusters at vertex $r_{x}$ and
possibly at one other vertex, called the _exit_ vertex of the cluster $x$ and
denoted by $e_{x}$. If block $b$ has an exit vertex $e_{b}$, then there is a
cluster $x$ in $b$ such that $e_{x}=e_{b}$.

  3. 3.

The demand of each cluster in $b$ is at most $2\Gamma^{\prime}$.

  4. 4.

The number of clusters in $b$ is at most
$3\cdot(\mathrm{demand}(b)/\Gamma^{\prime}+1)$.

The proof of Lemma 9 is in Appendix B.

###  4.3 Decomposition of a Cluster Into Cells (Fig. 2(c))

Let $x$ be any cluster. If $x$ is an ending cluster, then the decomposition of
$x$ consists of a single _cell_ , which is the entire cluster $x$. If $x$ is a
passing cluster, then we decompose $x$ into _cells_ as follows. Let $\ell$
denote the cost of the spine of cluster $x$. When $\ell=0$, the decomposition
of $x$ consists of a single _cell_ , which is the entire cluster $x$. Next, we
assume that $\ell>0$. For each integer $i\in[1,(1/\epsilon)-1]$, there exists
a unique edge $(u,v)$ on the spine of cluster $x$ satisfying
$\min(\mathrm{dist}(r_{x},u),\mathrm{dist}(r_{x},v))\leq
i\cdot\epsilon\cdot\ell<\max(\mathrm{dist}(r_{x},u),\mathrm{dist}(r_{x},v))$;
let $e_{i}$ denote that edge. Removing the edges
$e_{1},e_{2},\dots,e_{(1/\epsilon)-1}$ from cluster $x$ results in at most
$1/\epsilon$ connected subgraphs; each subgraph is called a _cell_. Observe
that those cells form a partition of the vertices of cluster $x$.

From the construction, the (unique) cell inside an ending cluster is an ending
cell, and the cells inside a passing cluster are passing cells. The cost of
the spine of any passing cell in a passing cluster is at most an $\epsilon$
fraction of the cost of the spine of that cluster.

######  Fact 10.

In any component $c$, the number of cells and the number of big terminals are
both $O_{\epsilon}(1)$.

###### Proof.

By Lemma 6, the total demand of the terminals in component $c$ is at most
$2\Gamma$. Since the demand of a big terminal is at least $\Gamma^{\prime}$,
there are at most $2\Gamma/\Gamma^{\prime}=O_{\epsilon}(1)$ big terminals in
$c$.

From the construction in Section 4.1, the set $U$ consists of at most
$2+2\Gamma/\Gamma^{\prime}$ vertices. Since each vertex in $c$ has at most two
children, the number of blocks in $c$ is at most $2|U|\leq
4+4\Gamma/\Gamma^{\prime}$. From the construction in Section 4.2, each block
$b$ is partitioned into at most $3\cdot(\mathrm{demand}(b)/\Gamma^{\prime}+1)$
clusters, where $\mathrm{demand}(b)$ is at most the total demand of the
terminals in component $c$, which is at most $2\Gamma$. From the construction
in Section 4.3, each cluster is partitioned into at most $1/\epsilon$ cells.
So the number of cells in $c$ is at most
$\left(4+4\Gamma/\Gamma^{\prime}\right)\cdot(3\cdot(2\Gamma/\Gamma^{\prime}+1))\cdot(1/\epsilon)=O_{\epsilon}(1).$
∎

######  Definition 11 (Adaptation from Definition 7).

A _subtour in a cluster (resp. cell)_ is a path $t$ that starts and ends at
the root of that cluster (resp. cell), and such that every vertex on $t$ is in
that cluster (resp. cell). We say that $t$ is a _passing subtour_ if that
cluster (resp. cell) has an exit vertex and that vertex belongs to $t$, and is
an _ending subtour_ otherwise. The _spine subtour_ in a passing cluster (resp.
passing cell) consists of the spine of that cluster (resp. cell) in both
directions.

##  5 Simplifying the Local Solution

In this section, we prove the Local Theorem (Theorem 12).

######  Theorem 12 (Local Theorem).

Let $c$ be any component. Let $S_{c}$ denote a set of at most
$(2\Gamma/\alpha)+1$ subtours in component $c$ visiting all terminals in $c$.
Then there exists a set $S^{*}_{c}$ of subtours in component $c$ visiting all
terminals in $c$, such that all of the following properties hold:

  1. 1.

For each cell in $c$, a single subtour in $S^{*}_{c}$ visits all small
terminals in that cell;

  2. 2.

$S^{*}_{c}$ contains one particular subtour $\bar{t}$ of demand at most 1, and
the subtours in $S^{*}_{c}\setminus\\{\bar{t}\\}$ are in one-to-one
correspondence with the subtours in $S_{c}$, such that for every subtour $t$
in $S_{c}$ and its corresponding subtour $t^{*}$ in
$S^{*}_{c}\setminus\\{\bar{t}\\}$, the demand of $t^{*}$ is at most the demand
of $t$, and in addition, if $t$ is a passing subtour in $c$, then $t^{*}$ is
also a passing subtour in $c$;

  3. 3.

The cost of $S^{*}_{c}$ is at most $1.5+2\epsilon$ times the cost of $S_{c}$.

###  5.1 Construction of $S^{*}_{c}$

The construction of $S^{*}_{c}$ starts from $S_{c}$ and proceeds in 5 steps.
Step 2 uses a new concept of _threshold cells_ and is the main novelty in the
construction. Step 1 and Step 3 are based on the following lemma due to Becker
and Paul [BP19].

######  Lemma 13 (Assignment Lemma, Lemma 1 in [BP19]).

Let $G=(V[G],E[G])$ be an edge-weighted bipartite graph with vertex set
$V[G]=A\uplus B$ and edge set $E[G]\subseteq A\times B$, such that each edge
$(a,b)\in E[G]$ has a weight $w(a,b)\geq 0$. For each vertex $b\in B$, let
$N(b)$ denote the set of vertices $a\in A$ such that $(a,b)\in E[G]$. We
assume that $N(b)\neq\emptyset$ and the weight $w(b)$ of the vertex $b$
satisfies $0\leq w(b)\leq\sum_{a\in N(b)}w(a,b)$. Then there exists a function
$f:B\to A$ such that each vertex $b\in B$ is assigned to a vertex $a\in N(b)$
and, for each vertex $a\in A$, we have

$\sum_{b\in B\mid f(b)=a}w(b)-\sum_{b\in B\mid(a,b)\in
E[G]}w(a,b)\leq\max_{b\in B}\big{\\{}w(b)\big{\\}}.$

##### Step 1: Combining ending subtours within each cluster.

Let $A_{0}$ denote $S_{c}$. We define a weighted bipartite graph $G$ in which
the vertices in one part represent the subtours in $A_{0}$ and the vertices in
the other part represent the clusters in $c$.777With a slight abuse, we
identify a vertex in $G$ with either a subtour in $A_{0}$ or a cluster in $c$.
There is an edge in $G$ between a subtour $a\in A_{0}$ and a cluster $x$ in
$c$ if and only if $a$ contains an ending subtour $t$ in $x$; the weight of
the edge is defined to be $\mathrm{demand}(t)$. For each cluster $x$ in $c$,
we define the weight of $x$ in $G$ to be the sum of the weights of its
incident edges in $G$. We apply the Assignment Lemma (Lemma 13) to the graph
$G$ (deprived of the vertices of degree 0) and obtain a function $f$ that maps
each cluster $x$ in $c$ to some subtour $a\in A_{0}$ such that $(a,x)$ is an
edge in $G$.

We construct a set of subtours $A_{1}$ as follows: for every cluster $x$ in
$c$ and for every subtour $a\in A_{0}$ containing an ending subtour $t$ in
$x$, the subtour $t$ is removed from $a$ and added to the subtour $f(x)$.
Observe that each resulting subtour in $A_{1}$ is connected. From the
construction, _for each cluster $x$, at most one subtour in $A_{1}$ has an
ending subtour in $x$_. In particular, for any _ending cell_ , which is
equivalent to an ending cluster, a single subtour in $A_{1}$ visits all small
terminals in that cell.

##### Step 2: Extending ending subtours within threshold cells.

Let $x$ be any passing cluster in $c$ such that there is a subtour in $A_{1}$
containing an ending subtour in $x$. From Step 1 of the construction, such a
subtour in $A_{1}$ is unique; let $t_{e}$ denote the corresponding ending
subtour in $x$. Define the _threshold cell_ of cluster $x$ to be the deepest
cell in $x$ containing vertices of $t_{e}$. See Fig. 4(a). We add to $t_{e}$
the part of the _spine subtour in the threshold cell of $x$_ that does not
belong to $t_{e}$, resulting in a subtour $\tilde{t}_{e}$; see Fig. 4(b).

Let $A_{2}$ denote the resulting set of subtours in $c$ after the extension
within all threshold cells. From the construction, _for each passing cell $s$,
all subtours in $s$ that are contained in $A_{2}$ are passing subtours in
$s$._

(a) Subtour before extension.

(b) Subtour after extension.

Figure 4: The threshold cell and the extension of an ending subtour. The
outermost triangle in blue represents a cluster $x$. In Fig. 4(a), the black
segments represent the ending subtour $t_{e}$ in $x$. The _threshold cell_ of
cluster $x$ is the _deepest_ cell visited by $t_{e}$ and is represented by the
yellow triangle. In Fig. 4(b), subtour $t_{e}$ is extended within the
threshold cell: the green segment represents the part of the _spine subtour of
the threshold cell_ that is added to $t_{e}$, resulting in a subtour
$\tilde{t}_{e}$.

##### Step 3: Combining passing subtours within each passing cell.

We define a weighted bipartite graph $G^{\prime}$ in which the vertices in one
part represent the subtours in $A_{2}$ and the vertices in the other part
represent the passing cells in $c$.888With a slight abuse, we identify a
vertex in $G^{\prime}$ with either a subtour in $A_{2}$ or a passing cell in
$c$. There is an edge in $G^{\prime}$ between a subtour $a\in A_{2}$ and a
passing cell $s$ in $c$ if and only if $a$ contains a non-spine passing
subtour $t$ in $s$; the weight of the edge is defined to be the total demand
of the small terminals on $t$. For each passing cell $s$ in $c$, we define the
weight of $s$ in $G^{\prime}$ to be the sum of the weights of its incident
edges in $G^{\prime}$. We apply the Assignment Lemma (Lemma 13) to the graph
$G^{\prime}$ (deprived of the vertices of degree 0) and obtain a function
$f^{\prime}$ that maps each passing cell $s$ in $c$ to some subtour $a\in
A_{2}$ such that $(a,s)$ is an edge in $G^{\prime}$.

We construct a set of subtours $A_{3}$ as follows: for every passing cell $s$
in $c$ and for every subtour $a\in A_{2}$ containing a non-spine passing
subtour $t$ in $s$, the subtour $t$ is removed from $a$ except for the spine
subtour of $s$; the removed part is added to the subtour $f^{\prime}(s)$.
Observe that each resulting subtour in $A_{3}$ is connected. From the
construction, _for each passing cell $s$, a single subtour in $A_{3}$ visits
all small terminals in $s$_.

##### Step 4: Correcting subtour capacities.

For each subtour $t_{3}$ in $A_{3}$, let $t_{0}$ denote the corresponding
subtour in $A_{0}$. As soon as the demand of $t_{3}$ is greater than the
demand of $t_{0}$, we repeatedly modify $t_{3}$ as follows: find a terminal
$v$ that is _visited by $t_{3}$ but not visited by $t_{0}$_; let $s$ denote
the cell containing $v$ and let $t_{s}$ denote the subtour of $t_{3}$ in cell
$s$; if $s$ is an ending cell, then remove $t_{s}$ from $t_{3}$; and if $s$ is
a passing cell, then remove $t_{s}$ from $t_{3}$ except for the spine subtour
of $s$.

Let $A_{4}$ denote the resulting set of modified subtours. Observe that each
subtour in $A_{4}$ is connected. From the construction, _the demand of each
subtour in $A_{4}$ is at most the demand of the corresponding subtour in
$A_{0}$._ Note that the big terminals in each subtour in $A_{4}$ are the same
as the big terminals in the corresponding subtour in $A_{0}$.999Any big
terminal cannot be removed, since it is the exit vertex of some cell, thus
belongs to the spine of that cell.

Let $\mathcal{R}$ denote the set of the removed pieces. We claim that the
total demand of the pieces in $\mathcal{R}$ is at most 1 (Lemma 20).

##### Step 5: Creating an additional subtour.

We connect all pieces in $\mathcal{R}$ by a single subtour in component $c$;
let $\bar{t}$ be that subtour.

Finally, let $S^{*}_{c}$ denote $A_{4}\cup\\{\bar{t}\,\\}$.

###  5.2 Analysis on the Cost of $S^{*}_{c}$

From the construction of $S_{c}^{*}$, we observe that the cost of $S_{c}^{*}$
equals the cost of $S_{c}$ plus the extra costs in Step 2 and in Step 5 of the
construction, denoted by $W_{2}$ and $W_{5}$, respectively.

To analyze the extra costs, first, in a preliminary lemma (Lemma 14), we bound
the overall cost of the spines of the threshold cells. Lemma 14 will be used
to analyze both $W_{2}$ (Corollary 15) and $W_{5}$ (Lemma 19).

######  Lemma 14.

The overall cost of the spines of all threshold cells in the component $c$ is
at most $(\epsilon/2)\cdot\mathrm{cost}(S_{c})$.

###### Proof.

Consider any threshold cell $s$. Let $x$ be the passing cluster that contains
$s$. As observed in Section 4.3, the cost of the spine of cell $s$ is at most
an $\epsilon$ fraction of the cost of the spine of the cluster $x$. Since $x$
is a passing cluster, at least one subtour in $S_{c}$ contains a passing
subtour in $x$; let $t_{x}$ denote that passing subtour in $x$. Observe that
$t_{x}$ contains each edge of the spine of cluster $x$ in both directions
(Definition 11), so the cost of the spine of $x$ is at most
$\mathrm{cost}(t_{x})/2$. Thus the cost of the spine of $s$ is at most
$(\epsilon/2)\cdot\mathrm{cost}(t_{x})$. We _charge_ the cost of the spine of
$s$ to $t_{x}$.

From the construction, each cluster contains at most one threshold cell. Thus
the costs of the spines of all threshold cells are charged to disjoint parts
of $S_{c}$. The claim follows. ∎

Observe that the extra cost in Step 2 of the construction is at most the
overall cost of the spine subtours in all threshold cells in the component
$c$, which equals twice the overall cost of the spines of those cells by
Definition 11.

######  Corollary 15.

The extra cost $W_{2}$ in Step 2 of the construction is at most
$\epsilon\cdot\mathrm{cost}(S_{c})$.

Next, we bound the extra cost in Step 5 of the construction.

######  Fact 16.

Let $t$ denote any subtour in $S_{c}$. Let $x$ denote any cluster in $c$. Let
$r_{c}$ and $r_{x}$ denote the root vertices of component $c$ and of cluster
$x$, respectively; let $e_{x}$ denote the exit vertex of cluster $x$. If the
$r_{c}$-to-$r_{x}$ path (resp. the $r_{c}$-to-$e_{x}$ path) belongs to $t$,
then that path belongs to the corresponding subtour of $t$ throughout the
construction in Section 5.1.

######  Definition 17 (nice edges).

We say that an edge $e$ in component $c$ is _nice_ if $e$ belongs to _at least
two_ subtours in $A_{2}$.

The next Lemma is the main novelty in the analysis.

######  Lemma 18.

Any piece in $\mathcal{R}$ is connected to the root $r_{c}$ of component $c$
through nice edges in $c$.

###### Proof.

Consider any piece $q\in\mathcal{R}$. Let $s$ be the cell containing $q$. Let
$x$ be the cluster containing $q$. See Fig. 5. Let $r_{s}$ and $r_{x}$ denote
the root vertices of cell $s$ and of cluster $x$, respectively. Observe that
the terminals in $x$ are visited by at least two subtours in $S_{c}$. This is
because, if all terminals in cluster $x$ are visited by a single subtour in
$S_{c}$, then those terminals belong to the corresponding subtour throughout
the construction, thus none of those terminals belongs to a piece in
$\mathcal{R}$, contradiction. Thus the $r_{c}$-to-$r_{x}$ path belongs to at
least two subtours in $S_{c}$. By 16, the $r_{c}$-to-$r_{x}$ path belongs to
at least two subtours in $A_{2}$, thus every edge on the $r_{c}$-to-$r_{x}$
path is nice. It suffices to show the following Claim:

_Piece $q$ is connected to vertex $r_{x}$ through nice edges in $c$. (*)_

There are two cases:

_Case 1: $x$ is an ending cluster._ See Fig. 5(a). From the decomposition in
Section 4.3, $s$ is an ending cell and $s$ equals $x$. Piece $q$ is an ending
subtour in $x$ and in particular contains $r_{x}$. Claim (*) follows
trivially.

_Case 2: $x$ is a passing cluster._ Let $e_{s}$ and $e_{x}$ denote the exit
vertices of cell $s$ and of cluster $x$, respectively. Observe that at least
one subtour in $S_{c}$ contains a passing subtour in $x$. There are two
subcases.

_Subcase 2(i): At least two subtours in $S_{c}$ contain passing subtours in
$x$._ See Fig. 5(b). Then the $r_{c}$-to-$e_{x}$ path belongs to at least two
subtours in $S_{c}$. By 16, the $r_{c}$-to-$e_{x}$ path belongs to at least
two subtours in $A_{2}$, thus each edge on the spine of $x$ is nice. Since
piece $q$ contains a vertex on the spine of $x$, Claim (*) follows.

_Subcase 2(ii): Exactly one subtour in $S_{c}$ contains a passing subtour in
$x$._ See Figs. 5(c) and 5(d). Let $t_{p}$ denote that passing subtour in $x$.
As observed previously, at least two subtours in $S_{c}$ visit terminals in
$x$, so there must be at least one subtour in $S_{c}$ that contains an ending
subtour in $x$. Let $t_{e}^{1},\dots,t_{e}^{m}$ (for some $m\geq 1$) denote
the ending subtours in $x$ contained in the subtours in $S_{c}$. In Step 1 of
the construction, the $m$ ending subtours are combined into a single ending
subtour, denoted by $t_{e}$ (recall that the threshold cell of $x$ is defined
with respect to $t_{e}$); and in Step 2 of the construction, subtour $t_{e}$
is extended to a subtour $\tilde{t}_{e}$ (Fig. 4). Note that the passing
subtour $t_{p}$ remains unchanged in Steps 1 and 2 of the construction. We
observe that cell $s$ is either above or equal to the threshold cell of $x$.
This is because, if cell $s$ is below the threshold cell of $x$, then all
terminals in $s$ are visited by a single subtour in $S_{c}$, i.e., the subtour
$t_{p}$, so those terminals belong to the corresponding subtour of $t_{p}$
throughout the construction, thus none of those terminals belongs to a piece
in $\mathcal{R}$, contradiction. Hence the following two subsubcases.

_Subsubcase 2(ii)( $\alpha$): $s$ is above the threshold cell of $x$_, see
Fig. 5(c). Each edge on the $r_{x}$-to-$e_{s}$ path belongs to both subtours
$t_{p}$ and $t_{e}$, hence is nice. Since $q$ contains some vertex on the
spine of $s$, Claim (*) follows.

_Subsubcase 2(ii)( $\beta$): $s$ equals the threshold cell of $x$_, see Fig.
5(d). Observe that each edge on the $r_{x}$-to-$e_{s}$ path belongs to
$\tilde{t}_{e}$ due to the extension of the ending subtour $t_{e}$ within the
threshold cell (Step 2 of the construction). Thus each edge on the
$r_{x}$-to-$e_{s}$ path belongs to both subtours $t_{p}$ and $\tilde{t}_{e}$,
hence is nice. Since $q$ contains some vertex on the spine of $s$, Claim (*)
follows. ∎

(a) Case 1.

(b) Subcase 2(i).

(c) Subsubcase 2(ii)($\alpha$).

(d) Subsubcase 2(ii)($\beta$)

Figure 5: Illustrations for the different cases in the proof of Lemma 18. A
removed piece $q\in\mathcal{R}$ is in brown. The cell $s$ containing that
piece is represented by the triangle in red; the cluster $x$ containing that
piece is represented by the outermost triangle in blue. The black node $r_{c}$
is the root of component $c$. In Fig. 5(a), $x$ is an ending cluster. In Fig.
5(b), $x$ is a passing cluster, and the solution $S_{c}$ contains two passing
subtours in $x$. In Figs. 5(c) and 5(d), $x$ is a passing cluster, and the
solution $S_{c}$ contains a unique passing subtour in $x$; the yellow triangle
represents the threshold cell of $x$. In the case when $q$ belongs to the
threshold cell (Fig. 5(d)), $q$ is connected to $r_{c}$ through at least two
subtours, thanks to the extension of the ending subtour within the threshold
cell.

######  Lemma 19.

The extra cost $W_{5}$ in Step 5 of the construction is at most
$(0.5+\epsilon)\cdot\mathrm{cost}(S_{c})$.

###### Proof.

First, we argue that the extra cost $W_{5}$ in Step 5 of the construction is
at most twice the overall cost of the nice edges in $c$. Let $H$ be the multi-
subgraph in $c$ that consists of the pieces in $\mathcal{R}$ and two copies of
each nice edge in $c$ (one copy for each direction). Since any piece in
$\mathcal{R}$ is connected to the root $r_{c}$ of component $c$ through nice
edges (Lemma 18), $H$ induces a connected subtour in $c$.

Second, we bound the overall cost of the nice edges in $c$. From the
construction, any nice edge $e$ in $c$ is of at least one of the two classes:

  1. 1.

edge $e$ belongs to at least two subtours in $S_{c}$;

  2. 2.

edge $e$ belongs to the spine of a threshold cell in component $c$.

Each nice edge $e$ of the first class has at least 4 copies in $S_{c}$, since
each subtour to which $e$ belongs contains 2 copies of $e$ (one for each
direction). Thus the overall cost of the nice edges of the first class is at
most $0.25\cdot\mathrm{cost}(S_{c})$. By Lemma 14, the overall cost of the
nice edges of the second class is at most
$(\epsilon/2)\cdot\mathrm{cost}(S_{c})$. Hence the overall cost of the nice
edges of both classes is at most $(0.25+\epsilon/2)\cdot\mathrm{cost}(S_{c})$.

Since the extra cost $W_{5}$ is at most twice the overall cost of the nice
edges in $c$, we have $W_{5}\leq(0.5+\epsilon)\cdot\mathrm{cost}(S_{c})$. ∎

From Corollaries 15 and 19, we conclude that

$\mathrm{cost}(S_{c}^{*})=\mathrm{cost}(S_{c})+W_{2}+W_{5}\leq(1.5+2\epsilon)\cdot\mathrm{cost}(S_{c}).$

Hence the third property of the claim in the Local Theorem (Theorem 12).

###  5.3 Feasibility

From the construction, $S_{c}^{*}$ is a set of subtours in $c$ visiting all
terminals in $c$. The first property of the claim in the Local Theorem
(Theorem 12) follows from the construction. The second property of the claim
follows from the construction, 16, and the following Lemma 20.

######  Lemma 20.

The total demand of the pieces in $\mathcal{R}$ is at most 1.

###### Proof.

Observe that the pieces in $\mathcal{R}$ are removed from subtours in $A_{3}$.
Let $t_{3}$ denote any subtour in $A_{3}$. Let $t_{0}$, $t_{1}$, $t_{2}$, and
$t_{4}$ denote the corresponding subtours of $t_{3}$ in $A_{0}$, $A_{1}$,
$A_{2}$, and $A_{4}$, respectively. Let $\Delta$ denote the overall demand of
the pieces that are removed from $t_{3}$ in Step 4 of the construction.
Observe that $\Delta=\mathrm{demand}(t_{3})-\mathrm{demand}(t_{4})$. To bound
$\Delta$, first, by Step 1 of the construction and the Assignment Lemma (Lemma
13), $\mathrm{demand}(t_{1})-\mathrm{demand}(t_{0})$ is at most the maximum
demand of a cluster, which is at most $2\Gamma^{\prime}$ by the definition of
clusters (Section 4.2). By Step 2 of the construction,
$\mathrm{demand}(t_{2})=\mathrm{demand}(t_{1})$. By Step 3 of the construction
and the Assignment Lemma (Lemma 13),
$\mathrm{demand}(t_{3})-\mathrm{demand}(t_{2})$ is at most the maximum demand
of a cell, which is at most $2\Gamma^{\prime}$ by the definition of cells
(Section 4.3). By Step 4 of the construction,
$\mathrm{demand}(t_{0})-\mathrm{demand}(t_{4})$ is at most the maximum demand
of a cell, which is at most $2\Gamma^{\prime}$. Combining, we have
$\Delta=\mathrm{demand}(t_{3})-\mathrm{demand}(t_{4})\leq 6\Gamma^{\prime}$.

The number of subtours in $A_{3}$ equals the number of subtours in $S_{c}$,
which is at most $(2\Gamma/\alpha)+1$ by assumption. Thus total demand of the
pieces in $\mathcal{R}$ is at most
$6\Gamma^{\prime}\cdot((2\Gamma/\alpha)+1)<13\epsilon<1$, assuming
$\epsilon<1/13$. ∎

This completes the proof of the Local Theorem (Theorem 12).

##  6 Height Reduction

In this section, we transform the tree $T$ into a tree $\hat{T}$ so that
$\hat{T}$ has $O_{\epsilon}(1)$ levels of components.

All results in this section are already given in [MZ22] for the equal demand
setting. The arguments for the arbitrary demand setting are identical, except
for the proof of Theorem 24, which is a minor adaptation of the proof in
[MZ22], see Remark 25.

######  Lemma 21 (Lemma 21 in [MZ22]).

Let $\tilde{D}=\alpha\cdot\epsilon\cdot D_{\min}$, where $\alpha$ is defined
in Definition 8 and $D_{\min}$ is defined in Definition 4. Let
$H_{\epsilon}=(1/\epsilon)^{(2/\epsilon)+1}$. For each $i\in[1,H_{\epsilon}]$,
let $\mathcal{C}_{i}\subseteq\mathcal{C}$ denote the set of components
$c\in\mathcal{C}$ such that
$\mathrm{dist}(r,r_{c})\in\left[(i-1)\cdot\tilde{D},i\cdot\tilde{D}\right)$.
Then any component $c\in\mathcal{C}$ belongs to a set $\mathcal{C}_{i}$ for
some $i\in[1,H_{\epsilon}]$.

######  Definition 22 (Definition 22 in [MZ22]).

We say that a set of components $\tilde{\mathcal{C}}\subseteq\mathcal{C}_{i}$
is _maximally connected_ if the components in $\tilde{\mathcal{C}}$ are
connected to each other and $\tilde{\mathcal{C}}$ is maximal within
$\mathcal{C}_{i}$. For a maximally connected set of components
$\tilde{\mathcal{C}}\subseteq\mathcal{C}_{i}$, we define the _critical vertex_
of $\tilde{\mathcal{C}}$ to be the root vertex of the component
$c\in\tilde{\mathcal{C}}$ that is closest to the depot.

Algorithm 1 Construction of the tree $\hat{T}$ ([MZ22]).

1:for each $i\in[1,H_{\epsilon}]$ do

2: for each maximally connected set of components
$\tilde{\mathcal{C}}\subseteq\mathcal{C}_{i}$ do

3: $z\leftarrow$ critical vertex of $\tilde{\mathcal{C}}$

4: for each component $c\in\tilde{\mathcal{C}}$ do

5: $\delta\leftarrow r_{c}$-to-$z$ distance in $T$

6:  _Split_ the tree $T$ at the root vertex $r_{c}$ of the component $c$

7: Add an edge between the root of the component $c$ and $z$ with weight
$\delta$

8:$\hat{T}\leftarrow$the resulting tree

######  Fact 23 (Fact 6 in [MZ22]).

Algorithm 1 constructs in polynomial time a tree $\hat{T}$ such that:

  * •

The components in $\hat{T}$ are the same as those in the tree $T$;

  * •

Any solution to the UCVRP on the tree $\hat{T}$ can be transformed in
polynomial time into a solution to the UCVRP on the tree $T$ without
increasing the cost.

######  Theorem 24 (Adaptation of Theorem 23 in [MZ22]).

Consider the UCVRP on the tree $\hat{T}$. There exist dummy terminals of
appropriate demands and a solution $\mathrm{OPT}_{2}$ visiting all of the real
and the dummy terminals, such that all of the following properties hold:

  1. 1.

For each component $c$, there are at most $(2\Gamma/\alpha)+1$ tours visiting
terminals in $c$;

  2. 2.

For each component $c$ and each tour $t$ visiting terminals in $c$, the total
demand of the terminals in $c$ visited by $t$ is at least $\alpha$;

  3. 3.

The cost of $\mathrm{OPT}_{2}$ is at most $1+3\epsilon$ times the optimal cost
for the UCVRP on the tree $T$.

######  Remark 25.

In the proof of Theorem 24, everything in [MZ22] carries over to the arbitrary
demand setting, except that the _Iterated Tour Partitioning (ITP)_ algorithm,
which is used to reduce the demand of the tours exceeding capacity, is adapted
as follows. Let $t_{\mathrm{TSP}}$ be a traveling salesman tour visiting a
selected subset of terminals (Section 3.1 in [MZ22]). We partition
$t_{\mathrm{TSP}}$ into segments, such that all segments, except possibly the
last segment, have demands between $1-\alpha$ and $1$, instead of being
exactly $1$. This is achievable since every terminal on $t_{\mathrm{TSP}}$ has
demand at most $\alpha$. The analysis is identical to [MZ22] except for a
suitable adaptation of the analysis of the ITP algorithm.

##  7 Combining Local Solutions

######  Definition 26.

For any component $c\in\mathcal{C}$, let $\mathcal{Q}_{c}$ denote the
partition of the terminals of component $c$, such that each part of the
partition consists of either all small terminals in a cell in $c$, or a single
big terminal in $c$. We define the set

$Y_{c}=\\{\alpha\\}\cup\Big{(}\big{\\{}\mathrm{demand}\big{(}\tilde{\mathcal{Q}}_{c}\big{)}:\tilde{\mathcal{Q}}_{c}\subseteq\mathcal{Q}_{c}\big{\\}}\cap(\alpha,1]\Big{)}.$

######  Theorem 27.

Consider the UCVRP on the tree $\hat{T}$. There exist dummy terminals of
appropriate demands and a solution $S^{*}$ visiting all of the real and the
dummy terminals, such that all of the following properties hold:

  1. 1.

For each cell, a single tour visits all small terminals in that cell;

  2. 2.

For each component $c$ and each tour $t$ visiting terminals in $c$, the total
demand of the terminals in $c$ visited by $t$ belongs to $Y_{c}$;

  3. 3.

The cost of $S^{*}$ is at most $1.5+7\epsilon$ times the optimal cost for the
UCVRP on the tree $T$.

###### Proof.

Let $S$ denote the solution to the UCVRP on the tree $\hat{T}$ that is
identical to $\mathrm{OPT}_{2}$ defined in Theorem 24, except for ignoring
dummy terminals in $\mathrm{OPT}_{2}$. To construct $S^{*}$, we modify the
solution $S$ component by component as follows. Consider any component $c$.
Let $S_{c}$ denote the set of subtours in $c$ obtained by restricting the
tours of $S$ visiting terminals in $c$. By Theorem 24,
$|S_{c}|\leq(2\Gamma/\alpha)+1$. We apply the Local Theorem (Theorem 12) on
$S_{c}$ to obtain a set $S_{c}^{*}$ of subtours in $c$, such that $S_{c}^{*}$
contains one particular subtour $\bar{t}$ of demand at most 1, and the
subtours in $S_{c}^{*}\setminus\\{\bar{t}\\}$ are in one-to-one correspondence
with the subtours in $S_{c}$. For the subtour $\bar{t}$, we create a new tour
from the depot by adding the $r$-to-$r_{c}$ connection in both directions.
Next, consider any subtour $t^{(1)}$ in $S_{c}$; let $t^{(2)}$ be the
corresponding subtour in $S_{c}^{*}$. We replace $t^{(1)}$ in the solution $S$
by a subtour $t$ defined as follows: $t$ is identical to $t^{(2)}$, except
that if $t^{(2)}$ visits terminals in $c$ and the demand of $t^{(2)}$ is less
than $\alpha$, then we add to $t$ a _dummy_ terminal at $r_{c}$ of demand
$\alpha-\mathrm{demand}(t^{(2)})$.

Let $S^{*}$ denote the resulting solution.

By the second property of the Local Theorem (Theorem 12), in any component
$c$, if a subtour in $S_{c}$ is a passing subtour, then the corresponding
subtour in $S_{c}^{*}$ is a passing subtour, thus each tour in $S^{*}$ is a
connected tour starting and ending at the depot. Again by the Local Theorem,
in any component $c$, the subtours in $S_{c}^{*}$ together visit all terminals
in $c$, thus the tours in $S^{*}$ together visit all of the real and the dummy
terminals in $\hat{T}$.

To see that the tours in $S^{*}$ are within the capacity, first, by the second
property of the Local Theorem (Theorem 12), any additional tour created from a
subtour $\hat{t}$ in some set $S_{c}^{*}$ is within the capacity. Next,
consider any tour $a$ among the remaining tours in $S^{*}$. Consider any
component $c$ that contains terminals visited by $a$; let $t$ be the subtour
in $c$ from tour $a$. Let $t^{(0)}$, $t^{(1)}$, and $t^{(2)}$ denote the
corresponding subtours of $t$ in $\mathrm{OPT}_{2}$, $S_{c}$, and $S_{c}^{*}$,
respectively. By Theorem 24, $\mathrm{demand}(t^{(0)})\geq\alpha$. By
definition of $S$, $\mathrm{demand}(t^{(1)})\leq\mathrm{demand}(t^{(0)})$. Now
we use the second property of the Local Theorem (Theorem 12), which ensures
that $\mathrm{demand}(t^{(2)})\leq\mathrm{demand}(t^{(1)})$. Thus
$\mathrm{demand}(t)=\max\\{\mathrm{demand}(t^{(2)}),\alpha\\}\leq\mathrm{demand}(t^{(0)})$.
Let $a^{(0)}$ denote the tour in $\mathrm{OPT}_{2}$ corresponding to $a$. Then
$\mathrm{demand}(a)\leq\mathrm{demand}(a_{0})$. Since $\mathrm{OPT}_{2}$ is a
solution to the UCVRP (Theorem 24), the total demand of (the real and the
dummy) terminals in $a^{(0)}$ is at most 1. Thus tour $a$ is within the
capacity.

The first property of the claim follows from the first property of the Local
Theorem (Theorem 12). The second property of the claim follows from the first
property of the claim and the construction of $S^{*}$. It remains to analyze
the cost of $S^{*}$.

From the construction of $S^{*}$, we have

$\mathrm{cost}(S^{*})=\sum_{c}\mathrm{cost}(S^{*}_{c})+\sum_{c}2\cdot\mathrm{dist}(r,r_{c}),$
(1)

where we use the fact that, for each component $c$, the distance in the tree
$\hat{T}$ between the depot $r$ and the root $r_{c}$ of component $c$ equals
that distance in the tree $T$. By Lemma 17 in [MZ22],

$\sum_{c}\mathrm{dist}(r,r_{c})\leq\frac{\epsilon}{8}\cdot\mathrm{opt}.$ (2)

By the third property of the Local Theorem (Theorem 12), we have

$\sum_{c}\mathrm{cost}(S^{*}_{c})\leq\sum_{c}(1.5+2\epsilon)\cdot\mathrm{cost}(S_{c})=(1.5+2\epsilon)\cdot\mathrm{cost}(S).$
(3)

By the definition of $S$ and Theorem 24, we have

$\mathrm{cost}(S)=\mathrm{cost}(\mathrm{OPT}_{2})\leq(1+3\epsilon)\cdot\mathrm{opt},$
(4)

where $\mathrm{opt}$ denotes the optimal cost for the UCVRP on the tree $T$.

The last property of the claim follows from Eqs. 1, 3, 4 and 2. ∎

##  8 Structure Theorem

######  Definition 28.

Let $Y\subseteq[\alpha,1]$ denote the set of values $y\in[\alpha,1]$ such that
$y$ equals the sum of the elements in a multi-subset of $\bigcup_{c}Y_{c}$.

######  Fact 29.

$\\{\mathcal{Q}_{c}\\}_{c}$, $\\{Y_{c}\\}_{c}$, and $Y$ satisfy the following
properties:

  1. 1.

For any component $c$, the set $\mathcal{Q}_{c}$ consists of $O_{\epsilon}(1)$
parts and the set $Y_{c}$ consists of $O_{\epsilon}(1)$ values;

  2. 2.

For any component $c$, we have $Y_{c}\subseteq Y$;

  3. 3.

For any values $y\in Y$ and $y^{\prime}\in Y$ such that $y+y^{\prime}\leq 1$,
we have $y+y^{\prime}\in Y$;

  4. 4.

The set $Y$ consists of $n^{O_{\epsilon}(1)}$ values.

###### Proof.

The first property of the claim follows from 10. The second and the third
properties of the claim follow from Definition 28. For any component $c$, each
value in $Y_{c}$ is at least $\alpha$, so each value $y\in Y$ is the sum of at
most $1/\alpha$ values in $\bigcup_{c}Y_{c}$. Since the number of components
in the tree $\hat{T}$ is at most $n$, the fourth property of the claim
follows. ∎

######  Definition 30 (subtours at a vertex).

For any vertex $v\in V$, we say that a path is _a subtour at $v$_ if that path
starts and ends at $v$ and only visits vertices in the subtree of $\hat{T}$
rooted at $v$.

We build on Theorem 27 to obtain the following Structure Theorem.

######  Theorem 31 (Structure Theorem).

Let $\beta=\frac{1}{4}\cdot\epsilon^{(4/\epsilon)+1}$. Consider the UCVRP on
the tree $\hat{T}$. There exist dummy terminals of appropriate demands and a
solution $\hat{S}$ visiting all of the real and the dummy terminals, such that
all of the following properties hold:

  1. 1.

For each cell, a single tour visits all small terminals in that cell;

  2. 2.

For each component $c$ and each tour $t$ visiting terminals in $c$, the total
demand of the terminals in $c$ visited by $t$ belongs to $Y_{c}$;

  3. 3.

For the root of each component and for each critical vertex (Definition 22),
the demand of each subtour at that vertex belongs to $Y$;

  4. 4.

For each critical vertex, there exist $\frac{1}{\beta}$ values in $Y$ such
that demand of each subtour at a child of that vertex is among those values;

  5. 5.

The cost of $\hat{S}$ is at most $1.5+8\epsilon$ times the optimal cost for
the UCVRP on the tree $T$.

In the rest of the section, we prove the Structure Theorem (Theorem 31).

###  8.1 Construction of $\hat{S}$

We construct the solution $\hat{S}$ by modifying the solution $S^{*}$ defined
in Theorem 27. The construction is an adaptation of Section 5.1 in [MZ22].

######  Definition 32.

Let $I\subseteq V$ denote the set of vertices $v\in V$ such that $v$ is either
the root of a component or a critical vertex.

We consider the vertices in $I$ in the bottom up order.

Let $v$ be any vertex in $I$. Let $S^{*}(v)$ denote the set of subtours at $v$
in $S^{*}$. We construct a set $A(v)$ of subtours at $v$ satisfying the
following invariants:

  * •

the subtours in $A(v)$ have a one-to-one correspondence with the subtours in
$S^{*}(v)$; and

  * •

for each subtour in $A(v)$, its demand belongs to $Y$ and is at most the
demand of the corresponding subtour in $S^{*}(v)$.

The construction of $A(v)$ is according to one of the following three cases on
$v$.

##### Case 1: $v$ is the root vertex $r_{c}$ of a leaf component $c$ in
$\hat{T}$.

Let $A(v)=S^{*}(v)$. For each subtour in $A(v)$, its demand belongs to $Y_{c}$
by Theorem 27, thus belongs to $Y$ by 29.

##### Case 2: $v$ is the root vertex $r_{c}$ of an internal component $c$ in
$\hat{T}$.

For each subtour $a\in S^{*}(v)$, if $a$ contains a subtour at the exit vertex
$e_{c}$ of component $c$, letting $t$ denote this subtour and $t^{\prime}$
denote the subtour in $A(e_{c})$ corresponding to $t$, we replace the subtour
$t$ in $a$ by the subtour $t^{\prime}$. Let $a^{\prime}$ denote the resulting
subtour. By induction, the demand of $t^{\prime}$ is at most that of $t$, thus
the demand of $a^{\prime}$ is at most the demand of $a$. Again by induction,
the demand of $t^{\prime}$ belongs to $Y$. Using the same argument as before,
the demand of the subtour in $c$ that is contained in $a$ belongs to $Y$.
Since the set $Y$ is closed under addition (29), the demand of $a^{\prime}$ is
in $Y$.

Let $A(v)$ be the resulting set of subtours at $v$.

##### Case 3: $v$ is a critical vertex in $\hat{T}$.

Let $r_{1},\dots,r_{m}$ be the children of $v$ in $\hat{T}$. For each subtour
$a\in S^{*}(v)$ and for each $i\in[1,m]$, if $a$ contains a subtour at
$r_{i}$, letting $t$ denote this subtour and $t^{\prime}$ denote the subtour
in $A(r_{i})$ corresponding to $t$, we replace $t$ in $a$ by $t^{\prime}$. Let
$A_{1}(v)$ denote the resulting set of subtours at $v$.

Let $W_{v}$ denote the set of the subtours at the children of $v$ in
$A_{1}(v)$, i.e., $W_{v}=A(r_{1})\cup\dots\cup A(r_{m})$. By induction, the
demand of each subtour in $W_{v}$ belongs to $Y$. If
$|W_{v}|\leq\frac{1}{\beta}$, let $A(v)=A_{1}(v)$.

Next, consider the non-trivial case when $|W_{v}|>\frac{1}{\beta}$. We sort
the subtours in $W_{v}$ in non-decreasing order of their demands, and
partition these subtours into $\frac{1}{\beta}$ groups of equal
cardinality.101010We add empty subtours to the first groups if needed in order
to achieve equal cardinality among all groups. We _round_ the demands of the
subtours in each group to the maximum demand in that group. For each
$i\in[1,m]$ and each subtour at $r_{i}$, the demand of that subtour is
increased to the rounded value by adding a _dummy_ terminal of appropriate
demand at vertex $r_{i}$. We rearrange the subtours in $W_{v}$ as follows.

  * •

Each subtour $t\in W_{v}$ in the last group is discarded, i.e., detached from
the subtour in $A_{1}(v)$ to which it belongs.

  * •

Each subtour $t\in W_{v}$ in other groups is associated in a one-to-one manner
to a subtour $t^{\prime}\in W_{v}$ in the next group. Letting $a$ (resp.
$a^{\prime}$) denote the subtour in $A_{1}(v)$ to which $t$ (resp.
$t^{\prime}$) belongs, we detach $t$ from $a$ and reattach $t$ to
$a^{\prime}$.

Let $A(v)$ be the set of the resulting subtours at $v$ after the rearrangement
for all $t\in W_{v}$. From the construction, the demand of each subtour in
$A(v)$ is at most the demand of the corresponding subtour in $S^{*}(v)$. Since
the demand of each subtour in $A(v)$ is the sum of values in $Y$ and the set
$Y$ is closed under addition (Property 3 of 29), the demand of that subtour
belongs to $Y$.

To construct a solution $\hat{S}$ visiting all terminals, it remains to cover
those subtours that are discarded in the construction. For each discarded
subtour $t$, we complete $t$ into a separate tour by adding the connection to
the depot in both directions. Observe that the demand of $t$ belongs to $Y$.
Let $B$ denote the set of those newly created tours.

Let $\hat{S}=A(r)\cup B$, where $r$ denotes the root of the tree $\hat{T}$.

###  8.2 Analysis of $\hat{S}$

It is easy to see that $\hat{S}$ is a feasible solution to the UCVRP, i.e.,
each tour in $\hat{S}$ starts and ends at the depot and has total demand at
most 1, and each terminal is covered by some tour in $\hat{S}$. The solution
$\hat{S}$ satisfies the first four properties of the claim. Following the
analysis in Section 5.2 in [MZ22], we obtain that
$\mathrm{cost}(\hat{S})\leq\frac{2}{2-\epsilon}\cdot\mathrm{cost}(S^{*})$,
where we use the bounded distance property of $T$ and the properties of
$\hat{T}$. Combined with the bound on $\mathrm{cost}(S^{*})$ in Theorem 27,
the last property of the claim follows.

This completes the proof of the Structure Theorem (Theorem 31).

##  9 Dynamic Program

In this section, we prove Theorem 33.

######  Theorem 33.

There is a polynomial time dynamic program that computes a solution for the
UCVRP on the tree $\hat{T}$ with cost at most $1.5+8\epsilon$ times the
optimal cost on the tree $T$.

Theorem 1 follows immediately from 23 and Theorem 33.

To design the dynamic program in Theorem 33, we compute the best solution on
the tree $\hat{T}$ that satisfies the properties in the Structure Theorem
(Theorem 31). The algorithm consists of two phases: the first phase computes
local solutions inside components (Section 9.1) and the second phase computes
solutions in subtrees in the bottom up order (Section 9.2). Properties 1 and 2
of the Structure Theorem are used in Section 9.1; Properties 3 and 4 of the
Structure Theorem are used in Section 9.2. The analysis on the cost of the
output solution is given in Section 9.3.

###  9.1 Computing Solutions Inside Components

######  Definition 34.

A _local configuration_ $(c,A)$ is defined by a component $c$ and a list $A$
consisting of $\ell(A)$ pairs
$(y_{1},b_{1}),(y_{2},b_{2}),\dots,(y_{\ell(A)},b_{\ell(A)})$ such that

  * •

$\ell(A)\leq|\mathcal{Q}_{c}|=O_{\epsilon}(1)$;

  * •

for each $i\in[1,\ell(A)]$, $y_{i}\in Y_{c}$ and $b_{i}\in\\{\text{passing,
ending}\\}$.

The _value_ of the local configuration $(c,A)$, denoted by $f(c,A)$, is the
minimum cost of a collection of $\ell(A)$ subtours $t_{1},\dots,t_{\ell(A)}$
in $c$ such that:

  * •

$t_{1},\dots,t_{\ell(A)}$ together cover all terminals in $c$;

  * •

For each $i\in[1,\ell(A)]$, the demand of $t_{i}$ is at most $y_{i}$ and the
type of $t_{i}$ is $b_{i}$;111111When the demand of $t_{i}$ is strictly less
than $y_{i}$, a _dummy_ terminal will be added to $t_{i}$ so that the total
demand of the real and the dummy terminals on $t_{i}$ equals $y_{i}$.

  * •

For each cell in $c$, some $t_{i}$ visits all small terminals in that cell.

When the local configuration $(c,A)$ corresponds to the solution $\hat{S}$
defined in the Structure Theorem (Theorem 31), that solution satisfies the
above constraints using the first two properties in that Theorem. Thus the
value of that local configuration is at most the cost of $\hat{S}$ in $c$.

The computation for the value of a local configuration is done by exhaistive
search and detailed in Algorithm 2.

Algorithm 2 Computation for local configurations inside a component $c$

1:for each list
$A=\left((y_{1},b_{1}),(y_{2},b_{2}),\dots,(y_{\ell(A)},b_{\ell(A)})\right)$
do

2: $f(c,A)\leftarrow\infty$

3: for each partition of $\mathcal{Q}_{c}$ into $\ell$ parts
$\mathcal{Q}_{c}^{(1)},\dots,\mathcal{Q}_{c}^{(\ell)}$ s.t. $\forall i$,
$\mathrm{demand}(\mathcal{Q}_{c}^{(i)})\leq y_{i}$ do

4: for each $i\in[1,\ell]$ do

5: $U\leftarrow\\{$terminals in $\mathcal{Q}_{c}^{(i)}\\}$

6: if $b_{i}$=passing then $U\leftarrow U\cup\\{\text{the exit vertex of
}c\\}$

7: $t_{i}\leftarrow$ the subtour in $c$ spanning $U$
$f(c,A)\leftarrow\min(f(c,A),\sum_{i}\mathrm{cost}(t_{i}))$

8:return $f(c,\cdot)$

##### Running time.

Since $|\mathcal{Q}_{c}|=O_{\epsilon}(1)$ (29), the number of partitions of
$\mathcal{Q}_{c}$ is $O_{\epsilon}(1)$, and for each partition, the subtour
costs can be computed in polynomial time, hence polynomial time to compute the
value of a local configuration. Observe that the number of local
configurations in $c$ is $O_{\epsilon}(1)$. Thus the overall running time to
compute the values of all local configurations in $c$ is polynomial.

###  9.2 Computing Solutions in Subtrees

The algorithm to compute solutions in a subtree is identical to the dynamic
program in Section 6.2 in [MZ22] in the equal demand setting, except for a
suitable adaptation of the values of the subtour demands. In the arbitrary
demand setting, the subtour demands are values in the set $Y$ by Property 3 in
the Structure Theorem (Theorem 31). Since the set $Y$ is closed under addition
(29), the dynamic program in [MZ22] carries over to the arbitrary demand
setting (this is the place where we use Property 4 in the Structure Theorem).
Since $Y$ consists of a polynomial number of values (29), the polynomial
running time of the algorithm in [MZ22] carries over to the arbitrary demand
setting.

For completeness, the algorithm and the running time analysis are given in
Appendix C.

###  9.3 Cost Analysis

The cost of the output solution is at most the cost of the solution $\hat{S}$
in the Structure Theorem (Theorem 31), which is at most $1.5+8\epsilon$ times
the optimal cost for the UCVRP on the tree $T$.

This completes the proof of Theorem 33.

##  Appendix A Hardness on the Approximation

###  A.1 UCVRP on Paths

We reduce the bin packing problem to the UCVRP on paths. Consider a bin
packing instance with $n$ items of sizes $a_{1},\dots,a_{n}$, where
$0<a_{i}\leq 1$ for each $i\in[1,n]$. We construct an instance of the UCVRP on
paths as follows. The path consists of $n+1$ vertices $r,v_{1},\dots,v_{n}$,
such that $r$ is the depot and $v_{1},\dots,v_{n}$ are the terminals. The
weight of the edge $rv_{1}$ equals 1; the weight of the edge $v_{i}v_{i+1}$
equals 0 for each $i\in[1,n-1]$. The demand of $v_{i}$ equals $a_{i}$ for each
$i\in[1,n]$. Observe that a solution to this instance of the UCVRP is
equivalent to a solution to the bin packing instance. Since it is NP-hard to
approximate the bin packing problem to better than a 1.5 factor [WS11], it is
NP-hard to approximate the UCVRP on paths to better than a 1.5 factor.

###  A.2 UCVRP Inside a Component

We reduce the bin packing problem to the UCVRP inside a component. Consider a
bin packing instance with $n$ items of sizes $a_{1},\dots,a_{n}$, where
$0<a_{i}\leq 1$ for each $i\in[1,n]$. We construct a component in the UCVRP as
follows. The component consists of $n+2$ vertices $r,v_{0},v_{1},\dots,v_{n}$
which form a star at $v_{0}$, such that $r$ is the depot and
$v_{1},\dots,v_{n}$ are the terminals. The weight of the edge $rv_{0}$ equals
1; the weight of the remaining edges $v_{0}v_{i}$ equals 0 for all
$i\in[1,n]$. The demand of $v_{i}$ equals $a_{i}$ for each $i\in[1,n]$.
Observe that a solution to this instance of the UCVRP is equivalent to a
solution to the bin packing instance. Since it is NP-hard to approximate the
bin packing problem to better than a 1.5 factor [WS11], it is NP-hard to
approximate the UCVRP in a component to better than a 1.5 factor.

##  Appendix B Proof of Lemma 9

The proof of Lemma 9 is a minor adaptation from the proof of Lemma 6 in
[MZ22].

For any subgraph $H$ of $b$, the _demand_ of $H$, denoted by
$\mathrm{demand}(H)$, is defined as the total demand of all terminals in $H$
that are _strictly_ inside $b$.

First, we construct _leaf clusters_ as follows. For any vertex $v\in b$ such
that the subtree of $b$ rooted at $v$ has demand at least $\Gamma^{\prime}$
and each of the subtrees rooted at the children of $v$ has demand strictly
less than $\Gamma^{\prime}$, we create a leaf cluster that equals the subtree
of $b$ rooted at $v$. If the block $b$ has an exit vertex $e_{b}$, we need to
ensure that $e_{b}$ is the exit vertex of some cluster. To that end, we
distinguish two cases: if $e_{b}$ belongs to some existing leaf cluster, then
we set $e_{b}$ to be the exit vertex of that cluster; otherwise, we create a
(trivial) leaf cluster consisting of the singleton $\\{e_{b}\\}$ and set
$e_{b}$ to be the root vertex and the exit vertex of that cluster. See
Algorithm 3 for a formal description of the construction of leaf clusters.
Observe that the leaf clusters are disjoint subtrees of $b$.

######  Definition 35 (key vertices).

The _backbone_ of $b$ is the subgraph of $b$ spanning the root of $b$ and the
roots of the leaf clusters. We say that a vertex $v\in b$ is a _key vertex_ if
it belongs to one of the three cases: (1) $v$ is the root of the block $b$;
(2) $v$ is the root of a leaf cluster; (3) $v$ has two children in the
backbone.

We say that two key vertices $v_{1}$ and $v_{2}$ are _consecutive_ if the
$v_{1}$-to-$v_{2}$ path in the tree does not contain any other key vertex. For
each pair of consecutive key vertices $(v_{1},v_{2})$, we consider the
subgraph _between_ $v_{1}$ and $v_{2}$, and decompose that subgraph into
_internal clusters_ , each of demand at most $2\Gamma$, such that all of these
cluster are _big_ (i.e., of demand at least $\Gamma$) except possibly for the
upmost cluster. See Algorithm 4 for the detailed construction of internal
clusters.

Algorithm 3 Construction of leaf clusters in block $b$.

1:for each vertex $v\in b$ do

2: $T(v)\leftarrow$ subtree of $b$ rooted at $v$

3:for each non-leaf vertex $v\in b$ do

4: Let $v_{1}$ and $v_{2}$ denote the two children of $v$ in $b$

5: if $\mathrm{demand}(T(v))\geq\Gamma^{\prime}$ and
$\mathrm{demand}(T(v_{1}))<\Gamma^{\prime}$ and
$\mathrm{demand}(T(v_{2}))<\Gamma^{\prime}$ then

6: Create a leaf cluster that equals $T(v)$ and has root vertex $v$

7:if $b$ has an exit vertex $e_{b}$ then

8: if $e_{b}$ belongs to some existing leaf cluster $x$ then

9: $e_{x}\leftarrow e_{b}$

10: else

11: Create a leaf cluster $x^{*}$ that equals a singleton $\\{e_{b}\\}$

12: $e_{x^{*}}\leftarrow e_{b}$

13: $r_{x^{*}}\leftarrow e_{b}$

Algorithm 4 Construction of internal clusters in block $b$.

1:for each pair of _consecutive_ key vertices $v_{1},v_{2}$ such that $v_{1}$
is an ancester of $v_{2}$ do

2: $v_{1}^{\prime}\leftarrow$ child of $v_{1}$ on the $v_{1}$-to-$v_{2}$ path

3: for each vertex $v$ on the $v_{1}^{\prime}$-to-$v_{2}$ path do
$H(v)\leftarrow T(v)\setminus T(v_{2})$

4: $x\leftarrow v_{2}$

5: while $H(v_{1}^{\prime})$ has demand at least $\Gamma^{\prime}$ do

6: $v\leftarrow$ the deepest vertex on the $v_{1}^{\prime}$-to-$x$ path such
that $H(v)$ has demand at least $\Gamma^{\prime}$

7: Create an internal cluster that equals $H(v)$ with root vertex $v$ and exit
vertex $x$

8: $x\leftarrow v$

9: for each vertex $v^{\prime}$ on the $v_{1}^{\prime}$-to-$x$ path do
$H(v^{\prime})\leftarrow T(v^{\prime})\setminus T(x)$

10: Create an internal cluster that equals $\\{(v_{1},v_{1}^{\prime})\\}\cup
H(v_{1})$ with root vertex $v_{1}$ and exit vertex $x$

The first three properties in the claim follow from the construction. It
remains to show the last property in the claim. The following lemma is crucial
in the analysis.

######  Lemma 36.

We say that a cluster in $b$ is _good_ if it is a leaf cluster or a big
cluster, and is _bad_ otherwise. There is a map from all clusters in $b$ to
good clusters in $b$ such that each good cluster in $b$ has at most three pre-
images.

###### Proof.

First, we define a map $\phi_{\rm good}$ that maps each good cluster to
itself. Next, we consider the bad clusters. Observe that the root vertex
$r_{x}$ of any bad cluster $x$ is a key vertex. We say that a bad cluster $x$
is a _left bad_ cluster (resp.  _right bad_ cluster) if $x$ contains the left
child (resp. right child) of $r_{x}$. We define a map $\phi_{\rm left}$ from
left bad clusters to leaf clusters, such that the image of a left bad cluster
is the leaf cluster that is _rightmost_ among its descendants. We show that
$\phi_{\rm left}$ is injective. Let $c_{1}$ and $c_{2}$ be any left bad
clusters. Observe that $r_{c_{1}}$ and $r_{c_{2}}$ are distinct key vertices.
If $r_{c_{1}}$ is ancestor of $r_{c_{2}}$ (the case when $r_{c_{2}}$ is
ancestor of $r_{c_{1}}$ is similar), then $\phi_{\rm left}(c_{2})$ is in the
left subtree of $r_{c_{2}}$ whereas $\phi_{\rm left}(c_{1})$ is outside the
left subtree of $r_{c_{2}}$, so $\phi_{\rm left}(c_{1})\neq\phi_{\rm
left}(c_{2})$. In the remaining case, the subtrees rooted at $r_{c_{1}}$ and
at $r_{c_{2}}$ are disjoint, so $\phi_{\rm left}(c_{1})\neq\phi_{\rm
left}(c_{2})$. Thus $\phi_{\rm left}$ is injective. Note that every leaf
cluster is good, so $\phi_{\rm left}$ is an injective map from left bad
clusters to good clusters. Similarly, we obtain an injective map $\phi_{\rm
right}$ from right bad clusters to good clusters. The claim follows by
combining the three injective maps $\phi_{\rm good}$, $\phi_{\rm left}$, and
$\phi_{\rm right}$. ∎

Observe that all good clusters are big except possibly one cluster, i.e., the
cluster $x^{*}$ containing the exit vertex $e_{b}$ of the block. Thus the
number of good clusters is at most $\mathrm{demand}(b)/\Gamma^{\prime}+1$. By
Lemma 36, the number of clusters in $b$ is at most three times the number of
good clusters in $b$, hence the last property of the claim. This completes the
proof of Lemma 9.

##  Appendix C Computing Solutions in Subtrees

This section is a slight adaptation from [MZ22]. Everything is identical to
[MZ22] except that we use the properties on the set $Y$ for the subtour
demands (29).

######  Definition 37.

A _subtree configuration_ $(v,A)$ is defined by a vertex $v$ and a list $A$
consisting of $\ell(A)$ pairs $(\tilde{y}_{1},n_{1})$,
$(\tilde{y}_{2},n_{2}),\ldots,(\tilde{y}_{\ell},n_{\ell(A)})$ such that

  * •

$v$ belongs to the set $I$ (Definition 32);

  * •

$\ell(A)=O_{\epsilon}(1)$; in particular, when $v$ is a critical vertex,
$\ell(A)\leq\left(\frac{1}{\beta}\right)^{\frac{1}{\alpha}}$;

  * •

for each $i\in[1,\ell(A)]$, $\tilde{y}_{i}$ belongs to the set $Y$ (Definition
28) and $n_{i}$ is an integer in $[0,n]$.

The _value_ of the subtree configuration $(v,A)$, denoted by $g(v,A)$, is the
minimum cost of a collection of $\ell(A)$ subtours in the subtree of $\hat{T}$
rooted at $v$, each subtour starting and ending at $v$, that together visit
all of the real terminals of the subtree rooted at $v$, such that, for each
$i\in[1,\ell(A)]$, there are $n_{i}$ subtours each with total demand of the
real and the dummy terminals that equals $\tilde{y}_{i}$.

When $v$ is the root $r$, any subtree configuration $(r,A)$ corresponds to a
solution to the UCVRP on the tree $\hat{T}$. The output of the algorithm is
the minimum value of $g(r,A)$ among all lists $A$.

To compute the values of subtree configurations, we consider the vertices
$v\in I$ in the bottom up order. For each vertex $v\in I$ that is the root of
a component, we compute the values $g(v,\cdot)$ using Algorithm 5 in Section
C.1; and for each vertex $v\in I$ that is a critical vertex, we compute the
values $g(v,\cdot)$ using Algorithm 6 in Section C.2. See Fig. 6.

Figure 6: At each vertex of the tree, the dynamic program memorizes the
demands of the subtours in the subtree and their total cost. Here is an
example of the flow of execution in the dynamic program. First, independent
computation in each component (Algorithm 2). Next, computation in the subtrees
rooted at vertices $v_{4}$ and $v_{5}$ (Algorithm 6). Then computation in the
subtrees rooted at vertices $v_{2}$ and $v_{3}$ (Algorithm 5). Finally,
computation in the subtree rooted at vertex $v_{1}$ (Algorithm 6). The output
is the best solution in the subtree rooted at $v_{1}$.

###  C.1 Subtree Configurations at the Root of a Component

In this subsection, we compute the values of the subtree configurations at the
root $r_{c}$ of a component $c$.

From Section 5, we have already computed the values of the local
configurations in the component $c$. If $c$ is a leaf component, the local
configurations in $c$ induce the subtree configurations at $r_{c}$, where
$\tilde{y}_{i}$ is the demand of the $i$-th subtour in the local configuration
and $n_{i}=1$ for each $i$. In the following, we consider the case when $c$ is
an internal component. From Definition 22, we observe that the exit vertex
$e_{c}$ of the component $c$ is a critical vertex. Thus the values of subtree
configurations at $e_{c}$ have already been computed using Algorithm 6 in
Section C.2 according to the bottom up order of the computation. To compute
the value of a subtree configuration at $r_{c}$, we combine a subtree
configuration at $e_{c}$ and a local configuration in $c$, in the following
way.

Consider a subtree configuration $(e_{c},A_{e})$ and a local configuration
$(c,A_{c})$, where

$A_{e}=((\tilde{y}_{1},n_{1}),(\tilde{y}_{2},n_{2}),\ldots,(\tilde{y}_{\ell_{e}},n_{\ell_{e}})),$
$A_{c}=((y_{1},b_{1}),(y_{2},b_{2}),\dots,(y_{\ell_{c}},b_{\ell_{c}})).$

To each $i\in[1,\ell_{c}]$ such that $b_{i}$ is “passing”, we associate
$y_{i}$ with $\tilde{y}_{j}$ for some $j\in[1,\ell_{e}]$ with the constraints
that $y_{i}+\tilde{y}_{j}\leq 1$ and for each $j\in[1,\ell_{e}]$ at most
$n_{j}$ elements are associated to $\tilde{y}_{j}$ (because in the subtree
rooted at $e_{c}$ we only have $n_{j}$ subtours of demand $\tilde{y}_{j}$ at
our disposal). Observe that, for each association $(y_{i},\tilde{y}_{j})$, we
have $y_{i}\in Y_{c}\subseteq Y$ (29), $\tilde{y}_{j}\in Y$, and
$y_{i}+\tilde{y}_{j}\leq 1$. Thus $y_{i}+\tilde{y}_{j}\in Y$ by 29.
Consequently, we obtain the list $A$ of a subtree configuration $(r_{c},A)$ as
follows:

  * •

For each association $(y_{i},\tilde{y}_{j})$, we put in $A$ the pair
$(y_{i}+\tilde{y}_{j},1)$.

  * •

For each pair $(\tilde{y}_{j},n_{j})\in A_{e}$, we put in $A$ the pair
$(\tilde{y}_{j},n_{j}-(\text{number of $y_{i}$'s associated to
$\tilde{y}_{j}$}))$.

  * •

For each pair $(y_{i},``\text{ending}")\in A_{c}$, we put in $A$ the pair
$(y_{i},1)$.

From the construction, $\ell(A)\leq\ell(A_{e})+\ell(A_{c})$. Since $e_{c}$ is
a critical vertex,
$\ell(A_{e})\leq\left(\frac{1}{\beta}\right)^{\frac{1}{\alpha}}$ by Definition
37. From Definition 34, $\ell(A_{c})=O_{\epsilon}(1)$. Thus
$\ell(A)\leq\left(\frac{1}{\beta}\right)^{\frac{1}{\alpha}}+O_{\epsilon}(1)=O_{\epsilon}(1)$.

Next, we compute the cost of the combination of the subtree configuration
$(e_{c},A_{e})$ and the local configuration $(c,A_{c})$; let $x$ denote this
cost. For any subtour $t$ at $e_{c}$ that is not associated to any non-spine
passing subtour in the component $c$, we pay an extra cost to include the
spine subtour of the component $c$, which is combined with the subtour $t$.
The number of times that we include the spine subtour of $c$ is the number of
subtours at $e_{c}$ minus the number of passing subtours in $A_{c}$, which is
$\sum_{j\leq\ell_{e}}n_{j}-\sum_{i\leq\ell_{c}}\mathbbm{1}\left[b_{i}\text{ is
``passing''}\right]$. Thus we have

$x=f(c,A_{c})+g(e_{c},A_{e})+\mathrm{cost}(\mathrm{spine}_{c})\cdot\left(\bigg{(}\sum_{j\leq\ell_{e}}n_{j}\bigg{)}-\bigg{(}\sum_{i\leq\ell_{c}}\mathbbm{1}\left[b_{i}\text{
is ``passing''}\right]\bigg{)}\right).$ (5)

The algorithm is described in Algorithm 5.

Algorithm 5 Computation for subtree configurations at the root of a component
$c$.

1:for each list $A$ do

2: $g(r_{c},A)=+\infty$.

3:for each subtree configuration $(e_{c},A_{e})$ and each local configuration
$(c,A_{c})$ do

4: for each way to combine $(e_{c},A_{e})$ and $(c,A_{c})$ do

5: $A\leftarrow$ the resulting list

6: $x\leftarrow$ the cost computed in Equation (5)

7: $g(r_{c},A)\leftarrow\min(g(r_{c},A),x)$.

8:return $g(r_{c},\cdot)$

##### Running time

Since $|Y|=n^{O_{\epsilon}(1)}$ (29), the number of subtree configurations
$(e_{c},A_{e})$ and the number of local configurations $(c,A_{c})$ are both
$n^{O_{\epsilon}(1)}$. For fixed $(e_{c},A_{e})$ and $(c,A_{c})$, the number
of ways to combine them is $O_{\epsilon}(1)$. Thus the running time of
Algorithm 5 is $n^{O_{\epsilon}(1)}$.

###  C.2 Subtree Configurations at a Critical Vertex

In this subsection, we compute the values of the subtree configurations at a
critical vertex. Let $z$ denote any critical vertex.

Consider the solution $\hat{S}$ in the Structure Theorem (Theorem 31). By
Property 4 in the Structure Theorem, there exists a set $X\subseteq Y$ of
$\frac{1}{\beta}$ values such that the demand of each subtour at a child of
$z$ is among the values in $X$. Since $Y\subseteq[\alpha,1]$, we have
$X\subseteq[\alpha,1]$. Thus the demand of a subtour at $z$ is the sum of at
most $\frac{1}{\alpha}$ values in $X$. Therefore, the number of distinct
demands of the subtours at $z$ is at most
$(\frac{1}{\beta})^{\frac{1}{\alpha}}=O_{\epsilon}(1)$. In addition, those
demands belong to $Y$, since each demand is the sum of a multiset of values in
$X$ and using 29.

To compute a solution satisfying Property 4 in the Structure Theorem, we
enumerate all sets $X\subseteq Y$ of $\frac{1}{\beta}$ values, compute a
solution with respect to each set $X$, and return the best solution found.
Unless explicitly mentioned, we assume in the following that the set $X$ is
fixed.

######  Definition 38 (sum list).

A _sum list_ $A$ consists of $\ell(A)$ pairs $(y_{1},n_{1})$, $(y_{2},n_{2})$,
…, $(y_{\ell(A)},n_{\ell(A)})$ such that

  1. 1.

$\ell(A)\leq(\frac{1}{\beta})^{\frac{1}{\alpha}}$;

  2. 2.

For each $i\in[1,\ell(A)]$, $y_{i}\in Y$ is the sum of a multiset of values in
$X$ and $n_{i}$ is an integers in $[0,n]$.

From the Structure Theorem, we only need to consider subtree configurations
$(z,A)$ such that the list $A$ is a sum list.

Let $r_{1},r_{2},\ldots,r_{m}$ be the children of $z$. For each $i\in[1,m]$,
let

$A_{i}=((y_{1}^{(i)},n_{1}^{(i)}),(y_{2}^{(i)},n_{2}^{(i)}),\ldots,(y_{\ell_{i}}^{(i)},n_{\ell_{i}}^{(i)}))$

denote the list in a subtree configuration $(r_{i},A_{i})$. We _round_ the
list $A_{i}$ to a list

$\overline{A_{i}}=((\overline{y_{1}^{(i)}},n_{1}^{(i)}),\overline{(y_{2}^{(i)}},n_{2}^{(i)}),\ldots,(\overline{y_{\ell_{i}}^{(i)}},n_{\ell_{i}}^{(i)})),$

where $\overline{x}$ denotes the smallest value in $X$ that is greater than or
equal to $x$, for any value $x$. The rounding is represented by adding a dummy
terminal of demand $\overline{x}-x$ at vertex $r_{i}$ to each subtour of
initial demand $x$.

Let $\mathcal{S}\subseteq Y$ denote a multiset such that for each $i\in[1,m]$
and for each $j\in[1,\ell_{i}]$, the multiset $\mathcal{S}$ contains
$n_{j}^{(i)}$ copies of $\overline{y_{j}^{(i)}}$.

######  Definition 39 (compatibility).

A multiset $\mathcal{S}\subseteq Y$ and a sum list

$A=((y_{1},n_{1}),(y_{2},n_{2}),\ldots,(y_{\ell(A)},n_{\ell(A)}))$

are _compatible_ if there is a partition of $\mathcal{S}$ into
$\sum_{i=1}^{\ell(A)}n_{i}$ parts and a correspondence between the parts of
the partition and the values $y_{i}$’s, such that for each $y_{i}$, there are
$n_{i}$ associated parts, and for each of those parts, the elements in that
part sum up to $y_{i}$.

For a sum list
$A=((y_{1},n_{1}),(y_{2},n_{2}),\ldots,(y_{\ell(A)},n_{\ell(A)}))$, the value
$g(z,A)$ of the subtree configuration $(z,A)$ equals the minimum, over all
sets $X$ and all subtree configurations $\\{(r_{i},A_{i})\\}_{1\leq i\leq m}$
such that $\mathcal{S}$ and $A$ are compatible, of

$\sum_{i=1}^{m}g(r_{i},A_{i})+2\cdot n(A_{i})\cdot w(r_{i},z),$ (6)

where $n(A_{i})$ denotes $\sum_{j=1}^{\ell_{i}}n_{j}^{(i)}$. We note that
$n_{1}y_{1}+n_{2}y_{2}+\cdots+n_{\ell(A)}y_{\ell(A)}$ is equal to the total
demand of the (real and dummy) terminals in the subtree rooted at $z$.

Algorithm 6 Computation for subtree configurations at a critical vertex $z$.

1:for each list $A$ do

2: $g(z,A)\leftarrow+\infty$

3:for each set $X\subseteq Y$ of $\frac{1}{\beta}$ values do

4: for each $i\in[0,m]$ and each list $A$ do

5: $\mathrm{DP}_{i}(A)\leftarrow+\infty$

6: $\mathrm{DP}_{0}(\emptyset)\leftarrow 0$

7: for each $i\in[1,m]$ do

8: for each subtree configuration $(r_{i},A_{i})$ do

9: $\overline{A_{i}}\leftarrow round(A_{i})$

10: for each sum list $A_{\leq i-1}$ do

11: for each way to combine $A_{\leq i-1}$ and $\overline{A_{i}}$ do

12: $A_{\leq i}\leftarrow$ the resulting sum list

13: $x\leftarrow\mathrm{DP}_{i-1}(A_{\leq i-1})+g(r_{i},A_{i})+2\cdot
n(A_{i})\cdot w(r_{i},z)$

14: $\mathrm{DP}_{i}(A_{\leq i})\leftarrow\min(\mathrm{DP}_{i}(A_{\leq i}),x)$

15: for each list $A$ do

16: $g(z,A)\leftarrow\min(g(z,A),\mathrm{DP}_{m}(A))$

17:return $g(z,\cdot)$

Fix any set $X\subseteq Y$ of $\frac{1}{\beta}$ values. We show how to compute
the minimum cost of Eq. 6 over all subtree configurations
$\\{(r_{i},A_{i})\\}_{1\leq i\leq m}$ such that $\mathcal{S}$ and $A$ are
compatible. For each $i\in[1,m]$ and for each subtree configuration
$(r_{i},A_{i})$, the value $g(r_{i},A_{i})$ has already been computed using
Algorithm 5 in Section C.1, according to the bottom up order of the
computation. We use a dynamic program that scans $r_{1},\dots,r_{m}$ one by
one: those are all siblings, so here the reasoning is not bottom-up but left-
right. Fix any $i\in[1,m]$. Let $\mathcal{S}_{i}\subseteq Y$ denote a multiset
such that for each $i^{\prime}\in[1,i]$ and for each
$j\in[1,\ell_{i^{\prime}}]$, the multiset $\mathcal{S}_{i}$ contains
$n_{j}^{(i^{\prime})}$ copies of $\overline{y_{j}^{(i^{\prime})}}$. We define
a dynamic program table $\mathrm{DP}_{i}$. The value $\mathrm{DP}_{i}(A_{\leq
i})$ at a sum list $A_{\leq i}$ equals the minimum, over all subtree
configurations $\\{(r_{i^{\prime}},A_{i^{\prime}})\\}_{1\leq i^{\prime}\leq
i}$ such that $\mathcal{S}_{i}$ and $A_{\leq i}$ are compatible, of

$\sum_{i^{\prime}=1}^{i}g(r_{i^{\prime}},A_{i^{\prime}})+2\cdot
n(A_{i^{\prime}})\cdot w(r_{i^{\prime}},z).$

When $i=m$, the values $\mathrm{DP}_{m}(\cdot)$ are those that we are looking
for. It suffices to fill in the tables
$\mathrm{DP}_{1},\dots,\mathrm{DP}_{m}$.

To compute the value $\mathrm{DP}_{i}$ at a sum list $A_{\leq i}$, we use the
value $\mathrm{DP}_{i-1}$ at a sum list $A_{\leq i-1}$ and the value
$g(r_{i},A_{i})$ of a subtree configuration $(r_{i},A_{i})$. Let $A_{\leq
i-1}=((\hat{y}_{1},\hat{n}_{1}),(\hat{y}_{2},\hat{n}_{2}),\ldots,(\hat{y}_{\ell},\hat{n}_{\ell}))$.
We combine $A_{\leq i-1}$ and $\overline{A_{i}}$ as follows. For each
$p\in[1,\ell]$ and each $j\in[1,\ell_{i}]$ such that
$\hat{y}_{p}+\overline{y_{j}^{(i)}}\leq 1$, we observe that
$\hat{y}_{p}+\overline{y_{j}^{(i)}}$ is the sum of a multiset of values in
$X$, thus belongs to $Y$ by 29. We create $n_{p,j}$ copies of the association
of $(\hat{y}_{p},\overline{y_{j}^{(i)}})$, where $n_{p,j}\in[0,n]$ is an
integer variable that we enumerate in the algorithm. We require that for each
$p\in[1,\ell]$, $\sum_{j=1}^{\ell_{i}}n_{p,j}\leq\hat{n}_{p}$; and for each
$j\in[1,\ell_{i}]$, $\sum_{p=1}^{\ell}n_{p,j}\leq n_{j}^{(i)}$. The resulting
sum list $A_{\leq i}$ is obtained as follows.

  * •

For each association $(\hat{y}_{p},\overline{y_{j}^{(i)}})$, we put in
$A_{\leq i}$ the pair $(\hat{y}_{p}+\overline{y_{j}^{(i)}},n_{p,j})$.

  * •

For each pair $(\hat{y}_{p},\hat{n}_{p})\in A_{\leq i-1}$, we put in $A_{\leq
i}$ the pair $(\hat{y}_{p},\hat{n}_{p}-\sum_{j=1}^{\ell_{i}}n_{p,j})$.

  * •

For each pair $(\overline{y_{j}^{(i)}},n_{j}^{(i)})\in\overline{A_{i}}$, we
put in $A_{\leq i}$ the pair
$(\overline{y_{j}^{(i)}},n_{j}^{(i)}-\sum_{p=1}^{\ell}n_{p,j})$.

The algorithm is described in Algorithm 6.

##### Running time

Since $|Y|=n^{O_{\epsilon}(1)}$, the numbers of subtree configurations and of
sum lists are $n^{O_{\epsilon}(1)}$. Observe that the number of ways to
combine them and the number of sets $X$ are $n^{O_{\epsilon}(1)}$. Thus the
overall running time of Algorithm 6 is $n^{O_{\epsilon}(1)}$.

## References

  * [AG87] Kemal Altinkemer and Bezalel Gavish.  Heuristics for unequal weight delivery problems with a fixed error guarantee.  Operations Research Letters, 6(4):149–158, 1987.
  * [AKK01] Tetsuo Asano, Naoki Katoh, and Kazuhiro Kawashima.  A new approximation algorithm for the capacitated vehicle routing problem on a tree.  Journal of Combinatorial Optimization, 5(2):213–231, 2001.
  * [AS15] Muhammad Al-Salamah.  Constrained binary artificial bee colony to minimize the makespan for single machine batch processing with non-identical job sizes.  Applied Soft Computing, 29:379–385, 2015.
  * [Bec18] Amariah Becker.  A tight 4/3 approximation for capacitated vehicle routing in trees.  In International Conference on Approximation Algorithms for Combinatorial Optimization Problems, volume 116, pages 3:1–3:15, 2018.
  * [BP19] Amariah Becker and Alice Paul.  A framework for vehicle routing approximation schemes in trees.  In Workshop on Algorithms and Data Structures, pages 112–125. Springer, 2019.
  * [BTV21] Jannis Blauth, Vera Traub, and Jens Vygen.  Improving the approximation ratio for capacitated vehicle routing.  In International Conference on Integer Programming and Combinatorial Optimization, pages 1–14. Springer, 2021.
  * [CDH11] Huaping Chen, Bing Du, and George Q. Huang.  Scheduling a batch processing machine with non-identical job sizes: a clustering perspective.  International Journal of Production Research, 49(19):5755–5778, 2011.
  * [CGHI13] Jing Chen, He Guo, Xin Han, and Kazuo Iwama.  The train delivery problem revisited.  In International Symposium on Algorithms and Computation, pages 601–611. Springer, 2013.
  * [DDF02] Lionel Dupont and Clarisse Dhaenens-Flipo.  Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure.  Computers & Operations Research, 29(7):807–819, 2002.
  * [DMM10] Aparna Das, Claire Mathieu, and Shay Mozes.  The train delivery problem-vehicle routing meets bin packing.  In International Workshop on Approximation and Online Algorithms, pages 94–105. Springer, 2010.
  * [DMS06] Purushothaman Damodaran, Praveen Kumar Manjeshwar, and Krishnaswami Srihari.  Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms.  International Journal of Production Economics, 103(2):882–891, 2006\.
  * [FMRS22] Zachary Friggstad, Ramin Mousavi, Mirmahdi Rahgoshay, and Mohammad R. Salavatipour.  Improved approximations for capacitated vehicle routing with unsplittable client demands.  In International Conference on Integer Programming and Combinatorial Optimization, pages 251–261. Springer, 2022.
  * [GW81] Bruce L. Golden and Richard T. Wong.  Capacitated arc routing problems.  Networks, 11(3):305–315, 1981.
  * [HK98] Shin-ya Hamaguchi and Naoki Katoh.  A capacitated vehicle routing problem on a tree.  In International Symposium on Algorithms and Computation, pages 399–407. Springer, 1998.
  * [JS22] Aditya Jayaprakash and Mohammad R. Salavatipour.  Approximation schemes for capacitated vehicle routing on graphs of bounded treewidth, bounded doubling, or highway dimension.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 877–893. SIAM, 2022.
  * [KKJ06] Ali Husseinzadeh Kashan, Behrooz Karimi, and Fariborz Jolai.  Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes.  International Journal of Production Research, 44(12):2337–2360, 2006.
  * [LLM91] Martine Labbé, Gilbert Laporte, and Hélene Mercure.  Capacitated vehicle routing on trees.  Operations Research, 39(4):616–622, 1991.
  * [MDC04] Sharif Melouk, Purushothaman Damodaran, and Ping-Yu Chang.  Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing.  International Journal of Production Economics, 87(2):141–147, 2004\.
  * [Mut20] İbrahim Muter.  Exact algorithms to minimize makespan on single and parallel batch processing machines.  European Journal of Operational Research, 285(2):470–483, 2020\.
  * [MZ22] Claire Mathieu and Hang Zhou.  A PTAS for capacitated vehicle routing on trees.  In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), page 95:1–95:20, 2022.
  * [PKK10] N. Rafiee Parsa, Behrooz Karimi, and Ali Husseinzadeh Kashan.  A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes.  Computers & Operations Research, 37(10):1720–1730, 2010.
  * [Rot12] Thomas Rothvoß.  The entropy rounding method in approximation algorithms.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 356–372. SIAM, 2012.
  * [Uzs94] Reha Uzsoy.  Scheduling a single batch processing machine with non-identical job sizes.  The International Journal of Production Research, 32(7):1615–1635, 1994.
  * [WL20] Yuanxiao Wu and Xiwen Lu.  Capacitated vehicle routing problem on line with unsplittable demands.  Journal of Combinatorial Optimization, pages 1–11, 2020.
  * [WS11] David P. Williamson and David B. Shmoys.  The Design of Approximation Algorithms.  Cambridge University Press, 2011.