$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}{3+\frac{2}{\lfloor
k/2\rfloor}}-1\geq\frac{k^{2}-3k-2}{3k+1}.\quad(\mbox{by}~{}\lfloor
k/2\rfloor\geq(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})(\frac{1}{u}-\frac{1}{u+1})+f(\frac{1}{u+1})<f(\frac{1}{u}),\quad\frac{k^{2}-3k-2}{3k+1}\leq
u\leq\frac{k}{2}.$

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

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

Hence, it is sufficient to prove that
$\ln(1+\frac{1}{k-u_{0}})-\frac{1}{u_{0}(k-u_{0})}>0$, where
$u_{0}=\frac{k^{2}-3k-2}{3k+1}$. 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 7$, we have
$\frac{1}{u_{0}}=\frac{3k+1}{k^{2}-3k-2}\leq\frac{11}{13}$ and
$\frac{1}{2(k-u_{0})}=\frac{3k+1}{4(k+1)^{2}}\leq\frac{11}{128}$. 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{11}{13}+\frac{11}{128}-\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. We will consider two cases of $k$.

Case 1. $k$ is odd: We have

$g(x)=\frac{5}{2}+\ln
2+\ln\frac{k+1-x}{k+1}-\frac{k-1+6x}{2(k+1)x}\quad\mbox{and}\quad
g^{\prime}(x)=\frac{-1}{k+1-x}+\frac{k-1}{2(k+1)x^{2}}.$

When $x=l_{o}=\frac{\sqrt{(k-1)^{2}+8(k-1)(k+1)^{2}}-(k-1)}{4(k+1)}$, we can
get that $g^{\prime}(x)=0$. Hence, it is easy to see that
$\max_{x\in\mathbb{Z}_{\geq 1}}g(x)=\max\\{g(\lceil l_{o}\rceil),g(\lfloor
l_{o}\rfloor)\\}=\max\\{\rho_{o}(\lceil l_{o}\rceil),\rho_{o}(\lfloor
l_{o}\rfloor)\\}$.

Case 2. $k$ is even: We have

$g(x)=\frac{5}{2}+\ln
2+\ln\frac{k+1-x}{k+2}-\frac{k+6x}{2(k+2)x}\quad\mbox{and}\quad
g^{\prime}(x)=\frac{-1}{k+1-x}+\frac{k}{2(k+2)x^{2}}.$

When $x=l_{e}=\frac{\sqrt{k^{2}+8k(k+1)(k+2)}-k}{4(k+2)}$, we can get that
$g^{\prime}(x)=0$. Hence, it is easy to see that $\max_{x\in\mathbb{Z}_{\geq
1}}g(x)=\max\\{g(\lceil l_{e}\rceil),g(\lfloor
l_{e}\rfloor)\\}=\max\\{\rho_{e}(\lceil l_{e}\rceil),\rho_{e}(\lfloor
l_{e}\rfloor)\\}$. ∎

It is worth noting that for $k\geq 7$ we have $x_{1}=x_{2}=\cdots=x_{l}=1/l$
in the worst case. For $k<7$, e.g., $k=6$, we may have
$1>x_{1}>x_{2}=\cdots=x_{l}$ in the worst case. Theorem 51 only considers
$k\geq 7$ for the sake of analysis. In fact, for $k<7$, the ratio is the same
as in Theorem 50.

##  13 A Further Improvement for Unsplittable 5-CVRP

In this section, we further improve the approximation ratio from
$5/3+\ln(5/3)<2.178$ to $2.157$ for unsplittable 5-CVRP. Different from our
algorithms for unsplittable 3-CVRP and 4-CVRP, we will use LP-UITP for
unsplittable 5-CVRP. This is the reason why we do not put our algorithms for
unsplittable 3-CVRP, 4-CVRP and 5-CVRP together.

For unsplittable 5-CVRP, we will consider two algorithms and we make a trade-
off between them. In the first algorithm, we first construct a mod-5-cycle
packing and then generate a feasible solution based on it. The second
algorithm is to call the refined LP-UITP algorithm on the Hamiltonian cycle
$H_{CS}$.

We assume that the demand of each customer is 1, 2, 3 or 4. Our first
algorithm will first compute a cycle packing $\mathcal{C}_{\bmod 5}$, where
“$\bmod~{}5$” means the total demand of customers in each cycle in the packing
is divisible by 5. We will simply call this cycle packing a mod-$5$-cycle
packing. It is computed in the following way: we consider the instance as a
unit-demand instance $G^{\prime}$ by taking each customer $v_{i}$ as $d_{i}$
customers with the unit-demand as the same place. Then, we call the
polynomial-time algorithm in Lemma 28 to generate a mod-$k$-tree packing
$\mathcal{T}_{\bmod 5}$ in $G^{\prime}[V^{\prime}]$ such that
$w(\mathcal{T}_{\bmod 5})\leq w(\mathcal{C}^{*}_{\bmod 5})$. By doubling the
mod-$k$-tree packing $\mathcal{T}_{\bmod 5}$ and then shortcutting, we can get
a mod-5-cycle packing $\mathcal{C}^{\prime}_{\bmod 5}$ in $G[V^{\prime}]$ such
that $w(\mathcal{C}^{\prime}_{\bmod 5})\leq 2w(\mathcal{C}^{*}_{\bmod 5})$.
Note that $\mathcal{C}^{\prime}_{\bmod 5}$ may not be a mod-5-cycle packing
for the original graph $G[V]$. By shortcutting in $\mathcal{C}^{\prime}_{\bmod
5}$, we can get a cycle packing $\mathcal{C}_{\bmod 5}$ on $V$. Moreover, the
total demand of all customers in each cycle in $\mathcal{C}_{\bmod 5}$ is
divisible by 5. We will use this mod-$5$-cycle packing $\mathcal{C}_{\bmod 5}$
for unsplittable 5-CVRP. We have that $w(\mathcal{C}_{\bmod 5})\leq
2w(\mathcal{C}_{5}^{*})$ and it holds that $\left|C\right|\bmod
5=\sum_{v_{j}\in C}d_{j}\bmod 5=0$ for each $C\in\mathcal{C}_{\bmod 5}$. The
next steps of our algorithm are based on the packing $\mathcal{C}_{\bmod 5}$.
For different types of cycles in $\mathcal{C}_{\bmod 5}$, we have different
operations. Consider a cycle $C$ in $\mathcal{C}_{\bmod 5}$. Let $x$ be the
sum of the demands of all 1-demand, 2-demand and 3-demand customers in $C$. We
classify the cycles in $\mathcal{C}_{\bmod 5}$ into several types
$\mathcal{C}_{<i>}$ according to the value of $x$. We will use $V_{i}$ to
denote the set of customers contained in a cycle in $\mathcal{C}_{<i>}$ and
let $\Delta_{i}=\sum_{v_{j}\in V_{i}}d_{j}w(v_{0},v_{j})$.

Type 0: Cycles with $x=0$, the set of which is denoted by $\mathcal{C}_{<0>}$.
For each cycle $C$ in $\mathcal{C}_{<0>}$, there is no 1-demand or 2-demand
customer and we assign a trivial tour for each 3-demand or 4-demand customer
in $C$. The weight of trivial tours is at most
$\frac{2}{3}\Delta_{0}\leq\frac{2}{3}\Delta_{0}+\frac{2}{3}w(\mathcal{C}_{<0>})$.

Type 1: Cycles with $x\geq 6$, the set of which is denoted by
$\mathcal{C}_{<1>}$. For each cycle $C$ in $\mathcal{C}_{<1>}$, we assign a
trivial tour for each 3-demand or 4-demand customer in $C$ and obtain a small
cycle $C^{\prime}$ from $C$ by shortcutting all 3-demand and 4-demand
customers. The set of cycles $C^{\prime}$ is denoted by
$\mathcal{C}^{\prime}_{<1>}$. Then we apply the EX-UITP algorithm on
$\mathcal{C}^{\prime}_{<1>}$.

We analyze the weight of the tours assigned in this step. Let $V^{\prime}_{1}$
be the set of 1-demand and 2-demand customers in $V_{1}$ and
$V^{\prime\prime}_{1}=V_{1}\setminus V_{1}^{\prime}$ be the set of 3-demand
and 4-demand customers in $V_{1}$. Let $\Delta^{\prime}_{1}=\sum_{v_{j}\in
V^{\prime}_{1}}d_{j}w(v_{0},v_{j})$ and
$\Delta^{\prime\prime}_{1}=\sum_{v_{j}\in
V^{\prime\prime}_{1}}d_{j}w(v_{0},v_{j})$. Note that for each cycle
$C^{\prime}$ in $\mathcal{C}^{\prime}_{<1>}$ we have $|C^{\prime}|=x\geq 6$.
For the tours generated by the EX-UITP algorithm on
$\mathcal{C}^{\prime}_{<1>}$, by Lemma 42, the total weight is at most
$\frac{2}{3}\Delta^{\prime}_{1}+\frac{2}{3}w(\mathcal{C}^{\prime}_{<1>})\leq\frac{2}{3}\Delta^{\prime}_{1}+\frac{2}{3}w(\mathcal{C}_{<1>})$
by the triangle inequality. For trivial tours visiting a 3-demand or 4-demand
customer, the total weight is at most $\frac{2}{3}\Delta^{\prime\prime}_{1}$.
In total, the weight is at most
$\frac{2}{3}\Delta^{\prime}_{1}+\frac{2}{3}\Delta^{\prime\prime}_{1}+\frac{2}{3}w(\mathcal{C}_{<1>})=\frac{2}{3}\Delta_{1}+\frac{2}{3}w(\mathcal{C}_{<1>})$.

We still have several cases, where $x$ is a small constant.

Type 2: Cycles with $x=1$, the set of which is denoted by $\mathcal{C}_{<2>}$.
Each cycle $C\in\mathcal{C}_{<2>}$ contains exactly one 1-demand customer $u$
and at least one 3-demand (or 4-demand) customer $u^{\prime}$ since the total
demand in the cycle is divisible by 5. We assign a tour $T$ visiting two
customers $u$ and $u^{\prime}$ only and a trivial tour for each other 3-demand
or 4-demand customer in $C$ except $u^{\prime}$. We can obtain a small cycle
$C^{\prime}$ from $C$ by shortcutting the 3-demand and 4-demand customers
except $u^{\prime}$. Let $V^{\prime}_{2}$ be the set of customers contained in
$T$ and let $\Delta^{\prime}_{2}=\sum_{v_{j}\in
V^{\prime}_{2}}d_{j}w(v_{0},v_{j})$. Note that
$4\leq|C^{\prime}|=d_{u}+d_{u^{\prime}}\leq 5$. By Lemma 43, we can assign the
tour $T$ with a weight of at most
$\frac{2}{|C^{\prime}|}\Delta^{\prime}_{2}+(1-\frac{1}{|C^{\prime}|})w(C^{\prime})\leq\frac{1}{2}\Delta^{\prime}_{2}+\frac{3}{4}w(C^{\prime})\leq\frac{2}{3}\Delta^{\prime}_{2}+\frac{2}{3}w(C^{\prime})\leq\frac{2}{3}\Delta^{\prime}_{2}+\frac{2}{3}w(C)$
by the triangle inequality. Let $V^{\prime\prime}_{2}=C\setminus
V^{\prime}_{2}$ and $\Delta^{\prime\prime}_{2}=\sum_{v_{j}\in
V^{\prime\prime}_{2}}d_{j}w(v_{0},v_{j})$. For trivial tours visiting the
other 3-demand and 4-demand customers in $V^{\prime\prime}_{2}$, the total
weight is at most $\frac{2}{3}\Delta^{\prime\prime}_{2}$. Thus, by summing all
cycles in $\mathcal{C}_{<2>}$, the weight of tours in this step is at most
$\frac{2}{3}\Delta_{2}+\frac{2}{3}w(\mathcal{C}_{<2>})$.

Type 3: Cycles with $x=2$, the set of which is denoted by $\mathcal{C}_{<3>}$.
Each cycle $C\in\mathcal{C}_{<3>}$ contains exactly two 1-demand customers
$u_{1}$ and $u_{2}$ or exactly one 2-demand customer $u$ and at least one
3-demand (or 4-demand) customer $u^{\prime}$ since the total demand in the
cycle is divisible by 5.

If the demand of $u^{\prime}$ is 3, we assign a single tour $T$ visiting
$\\{u_{1},u_{2},u^{\prime}\\}$ (or $\\{u,u^{\prime}\\}$) and a trivial tour
for each other 3-demand or 4-demand customer in $C$ except $u^{\prime}$. We
can obtain a small cycle $C^{\prime}$ from $C$ by shortcutting the 3-demand
and 4-demand customers except $u^{\prime}$. Let $V^{\prime}_{3}$ be the set of
customers contained in $T$ and let $\Delta^{\prime}_{3}=\sum_{v_{j}\in
V^{\prime}_{3}}d_{j}w(v_{0},v_{j})$. Note that $|C^{\prime}|=5$. By Lemma 43,
we can assign the tour $T$ with a weight of at most
$\frac{2}{5}\Delta^{\prime}_{3}+\frac{3}{5}w(C^{\prime})\leq\frac{2}{3}\Delta^{\prime}_{3}+\frac{2}{3}w(C^{\prime})\leq\frac{2}{3}\Delta^{\prime}_{2}+\frac{2}{3}w(C)$
by the triangle inequality. Let $V^{\prime\prime}_{3}=C\setminus
V^{\prime}_{3}$ and $\Delta^{\prime\prime}_{3}=\sum_{v_{j}\in
V^{\prime\prime}_{3}}d_{j}w(v_{0},v_{j})$. For trivial tours visiting the
other 3-demand and 4-demand customers in $V^{\prime\prime}_{3}$, the total
weight is at most $\frac{2}{3}\Delta^{\prime\prime}_{3}$. Thus, by summing all
cycles in $\mathcal{C}_{<3>}$, the weight of tours in this step is at most
$\frac{2}{3}\Delta_{3}+\frac{2}{3}w(\mathcal{C}_{<3>})$.

If the demand of $u^{\prime}$ is 4, we assign two tours $T_{1}$ and $T_{2}$
with the capacity $2$ and $4$ visiting $\\{u_{1},u_{2},u^{\prime}\\}$ (or
$\\{u,u^{\prime}\\}$) and a trivial tour for each other 3-demand or 4-demand
customer in $C$ except $u^{\prime}$. We can obtain a small cycle $C^{\prime}$
from $C$ by shortcutting the 3-demand and 4-demand customers except
$u^{\prime}$. Define $V^{\prime}_{3}$, $\Delta^{\prime}_{3}$,
$V^{\prime\prime}_{3}$ and $\Delta^{\prime\prime}_{3}$ in the similar way as
above. Note that $|C^{\prime}|=6$. By considering all cases, we can easily get
that we can assign the tours $T_{1}$ and $T_{2}$ with a weight of at most
$\frac{2}{3}\Delta^{\prime}_{3}+\frac{2}{3}w(C^{\prime})\leq\frac{2}{3}\Delta^{\prime}_{3}+\frac{2}{3}w(C)$
by the triangle inequality. For trivial tours visiting the other 3-demand and
4-demand customers in $V^{\prime\prime}_{3}$, the total weight is at most
$\frac{2}{3}\Delta^{\prime\prime}_{3}$. Thus, by summing all cycles in
$\mathcal{C}_{<3>}$, the weight of tours in this step is at most
$\frac{2}{3}\Delta_{3}+\frac{2}{3}w(\mathcal{C}_{<3>})$.

Type 4: Cycles with $3\leq x\leq 5$, the set of which is denoted by
$\mathcal{C}_{<4>}$. For each cycle $C\in\mathcal{C}_{<4>}$, we assign a
trivial tour for each 3-demand or 4-demand customer in $C$ and obtain a small
cycle $C^{\prime}$ from $C$ by shortcutting all 3-demand and 4-demand
customers. Then we assign the last tour $T$ according to $C^{\prime}$. Let
$V^{\prime}_{4}$ be the set of customers contained in $T$ and let
$\Delta^{\prime}_{4}=\sum_{v_{j}\in V^{\prime}_{4}}d_{j}w(v_{0},v_{j})$. By
Lemma 43, we can assign the tour $T$ with a weight of at most
$\frac{2}{x}\Delta^{\prime}_{4}+(1-\frac{1}{x})w(C^{\prime})\leq\frac{2}{3}\Delta^{\prime}_{4}+\frac{2}{3}w(C^{\prime})\leq\frac{2}{3}\Delta^{\prime}_{2}+\frac{2}{3}w(C)$
by the triangle inequality. Let $V^{\prime\prime}_{4}=C\setminus
V^{\prime}_{4}$ and $\Delta^{\prime\prime}_{4}=\sum_{v_{j}\in
V^{\prime\prime}_{4}}d_{j}w(v_{0},v_{j})$. For trivial tours visiting the
3-demand and 4-demand customers in $V^{\prime\prime}_{4}$, the total weight is
at most $\frac{2}{3}\Delta^{\prime\prime}_{4}$. Thus, the weight of tours in
this step is at most $\frac{2}{3}\Delta_{4}+\frac{2}{3}w(\mathcal{C}_{<4>})$.

Recall that $w(\mathcal{C}_{\bmod 5})\leq 2w(\mathcal{C}^{*}_{\bmod 5})$.

######  Lemma 52.

Given the mod-$5$-cycle packing $\mathcal{C}_{\bmod 5}$, for unsplittable
5-CVRP, there is a polynomial-time algorithm to generate an itinerary $I$ such
that $w(I)\leq\frac{2}{3}\Delta+\frac{2}{3}w(\mathcal{C}_{\bmod
5})\leq\frac{2}{3}\Delta+\frac{4}{3}w(\mathcal{C}^{*}_{\bmod 5})$.

######  Lemma 53.

For unsplittable 5-CVRP, there is a $2.157$-approximation algorithm.

###### Proof.

There are two algorithms.

Using the mod-$5$-cycle packing algorithm, by Lemma 52, we can generate an
itinerary $I_{1}$ with

$w(I_{1})\leq\frac{2}{3}\Delta+\frac{4}{3}w(\mathcal{C}_{\bmod 5}^{*}).$

By Lemmas 13 and 17, we have

$\frac{2}{3}\Delta+\frac{4}{3}w(\mathcal{C}_{\bmod
5}^{*})\leq\frac{2}{3}\left(\chi+\frac{3}{2}\right)w(I^{*})+\frac{4}{3}(2-2\chi)w(I^{*})=\frac{11-6\chi}{3}w(I^{*}).$

Using the LP-UITP algorithm and the Hamiltonian cycle $H_{CS}$ on
$V\cup\\{v_{0}\\}$, we can generate an itinerary $I_{2}$ such that

$w(I_{2})\leq\min_{\gamma\geq 0}\left\\{\gamma\cdot
w(I^{*})+e^{-\gamma}\cdot\frac{2}{3}\Delta+\frac{2}{3}w(H_{CS})\right\\}.$

We will set $\gamma=\frac{2}{3}\chi+1$. Since
$\Delta\leq(\chi+\frac{3}{2})w(I^{*})$ by Lemma 13, we have that

$\gamma\cdot w(I^{*})+e^{-\gamma}\cdot\frac{2}{3}\Delta\leq\gamma\cdot
w(I^{*})+e^{-\gamma}\cdot\frac{2}{3}\left(\chi+\frac{3}{2}\right)w(I^{*})=\left(1+\ln\frac{3+2\chi}{3}\right)w(I^{*}).$

Recall that $w(H_{CS})\leq\frac{3-\chi}{2}$ by Lemma 16. Therefore, we have
that

$\displaystyle\gamma\cdot
w(I^{*})+e^{-\gamma}\cdot\frac{2}{3}\Delta+\frac{2}{3}w(H_{CS})\leq\left(\frac{6-\chi}{3}+\ln\frac{3+2\chi}{3}\right)w(I^{*}).$

We will select the better one between these two itineraries. The final ratio
is

$\max_{\begin{subarray}{c}0\leq\chi\leq
1\end{subarray}}\min\left\\{\frac{11-6\chi}{3},\
\frac{6-\chi}{3}+\ln\frac{3+2\chi}{3}\right\\}=\frac{11-6x_{0}}{3}<2.157,$

where $\chi=x_{0}>0.755$ in the worst case, the unique root of the equitation
$\frac{5}{3}(x-1)+\ln\frac{3+2x}{3}=0$. ∎

##  14 Concluding Remarks

In this paper, we consider $k$-CVRP in general metrics and improve the
approximation ratio for $k$ being sufficient large, say $k\leq 1.7\times
10^{7}$. Most of our algorithms are modified from known algorithms or just
classic algorithms. They are simple and easy to implement. Our modified
algorithms, such as EX-ITP, may also have potentials to be applied in fast
experimental and heuristic algorithms. Although our algorithms are simple, the
analysis is technically involved. We need to carefully analyze the structure
of the solutions and most of our analysis is based on pure combinatorial
analysis. We believe that analyzing better theoretical bounds for simple and
classic algorithms is an interesting and important task in algorithms.

## References

  * [1] Anna Adamaszek, Artur Czumaj, and Andrzej Lingas.  Ptas for k-tour cover problem on the plane for moderately large values of k.  Int. J. Found. Comput. Sci., 21(6):893–904, 2010.
  * [2] Kemal Altinkemer and Bezalel Gavish.  Heuristics for unequal weight delivery problems with a fixed error guarantee.  Operations Research Letters, 6(4):149–158, 1987.
  * [3] Kemal Altinkemer and Bezalel Gavish.  Heuristics for delivery problems with constant error guarantees.  Transportation Science, 24(4):294–297, 1990.
  * [4] Shoshana Anily and Julien Bramel.  Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries.  Naval Research Logistics (NRL), 46(6):654–670, 1999.
  * [5] Tetsuo Asano, Naoki Katoh, and Kazuhiro Kawashima.  A new approximation algorithm for the capacitated vehicle routing problem on a tree.  J. Comb. Optim., 5(2):213–231, 2001.
  * [6] Tetsuo Asano, Naoki Katoh, Hisao Tamaki, and Takeshi Tokuyama.  Covering points in the plane by k-tours: a polynomial approximation scheme for fixed k.  IBM Tokyo Research Laboratory Research Report RT0162, 1996.
  * [7] 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.
  * [8] Cristina Bazgan, Refael Hassin, and Jérôme Monnot.  Approximation algorithms for some vehicle routing problems.  Discret. Appl. Math., 146(1):27–42, 2005.
  * [9] Amariah Becker.  A tight 4/3 approximation for capacitated vehicle routing in trees.  In APPROX/RANDOM 2018, volume 116 of LIPIcs, pages 3:1–3:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [10] Amariah Becker, Philip N. Klein, and David Saulpic.  A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs.  In ESA 2017, volume 87 of LIPIcs, pages 12:1–12:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [11] Amariah Becker, Philip N. Klein, and David Saulpic.  Polynomial-time approximation schemes for k-center, k-median, and capacitated vehicle routing in bounded highway dimension.  In ESA 2018, volume 112 of LIPIcs, pages 8:1–8:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [12] Amariah Becker, Philip N. Klein, and Aaron Schild.  A PTAS for bounded-capacity vehicle routing in planar graphs.  In WADS 2019, volume 11646 of Lecture Notes in Computer Science, pages 99–111. Springer, 2019.
  * [13] Amariah Becker and Alice Paul.  A framework for vehicle routing approximation schemes in trees.  In WADS 2019, volume 11646 of Lecture Notes in Computer Science, pages 112–125. Springer, 2019.
  * [14] Walter J Bell, Louis M Dalberto, Marshall L Fisher, Arnold J Greenfield, Ramchandran Jaikumar, Pradeep Kedia, Robert G Mack, and Paul J Prutzman.  Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer.  Interfaces, 13(6):4–23, 1983.
  * [15] Jannis Blauth, Vera Traub, and Jens Vygen.  Improving the approximation ratio for capacitated vehicle routing.  Mathematical Programming, pages 1–47, 2022.
  * [16] Agustín Bompadre, Moshe Dror, and James B. Orlin.  Improved bounds for vehicle routing solutions.  Discret. Optim., 3(4):299–316, 2006.
  * [17] Nicos Christofides.  Worst-case analysis of a new heuristic for the travelling salesman problem.  Technical report, Carnegie-Mellon University, 1976.
  * [18] Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, and Hung Le.  On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs.  In FOCS 2020, pages 589–600. IEEE, 2020.
  * [19] George B Dantzig and John H Ramser.  The truck dispatching problem.  Management science, 6(1):80–91, 1959.
  * [20] Aparna Das and Claire Mathieu.  A quasipolynomial time approximation scheme for euclidean capacitated vehicle routing.  Algorithmica, 73(1):115–142, 2015.
  * [21] Moshe Dror and Pierre Trudeau.  Split delivery routing.  Naval Research Logistics (NRL), 37(3):383–402, 1990.
  * [22] Szymon Dudycz, Jan Marcinkowski, Katarzyna E. Paluch, and Bartosz Rybicki.  A 4/5 - approximation algorithm for the maximum traveling salesman problem.  In IPCO 2017, volume 10328, pages 173–185. Springer, 2017.
  * [23] Marc Dufay, Claire Mathieu, and Hang Zhou.  An approximation algorithm for distance-constrained vehicle routing on trees.  CoRR, abs/2210.03811, 2022.
  * [24] Arnold Filtser and Hung Le.  Low treewidth embeddings of planar and minor-free metrics.  CoRR, abs/2203.15627, 2022.
  * [25] 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.
  * [26] Harold Neil Gabow.  Implementation of algorithms for maximum matching on nonbipartite graphs.  PhD thesis, Stanford University, 1974.
  * [27] Michel X. Goemans and David P. Williamson.  A general approximation technique for constrained forest problems.  SIAM J. Comput., 24(2):296–317, 1995.
  * [28] Bruce L. Golden and Richard T. Wong.  Capacitated arc routing problems.  Networks, 11(3):305–315, 1981.
  * [29] Fabrizio Grandoni, Claire Mathieu, and Hang Zhou.  Unsplittable euclidean capacitated vehicle routing: A (2+$\varepsilon$)-approximation algorithm.  CoRR, abs/2209.05520, 2022.
  * [30] Mordecai Haimovich and Alexander H. G. Rinnooy Kan.  Bounds and heuristics for capacitated routing problems.  Math. Oper. Res., 10(4):527–542, 1985.
  * [31] Shin-ya Hamaguchi and Naoki Katoh.  A capacitated vehicle routing problem on a tree.  In ISAAC 1998, pages 397–406. Springer, 1998.
  * [32] David Hartvigsen.  Extensions of matching theory.  PhD thesis, Carnegie-Mellon University, 1984.
  * [33] Refael Hassin and Shlomi Rubinstein.  Better approximations for max TSP.  Inf. Process. Lett., 75(4):181–186, 2000.
  * [34] Aditya Jayaprakash and Mohammad R. Salavatipour.  Approximation schemes for capacitated vehicle routing on graphs of bounded treewidth, bounded doubling, or highway dimension.  In SODA 2022, pages 877–893. SIAM, 2022.
  * [35] 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.
  * [36] Michael Yu. Khachay and Roman Dubinin.  PTAS for the euclidean capacitated vehicle routing problem in $\mathbb{R}^{d}$.  In DOOR 2016, volume 9869 of Lecture Notes in Computer Science, pages 193–205. Springer, 2016.
  * [37] David G. Kirkpatrick and Pavol Hell.  On the completeness of a generalized matching problem.  In STOC 1978, pages 240–245. ACM, 1978.
  * [38] Martine Labbé, Gilbert Laporte, and Hélène Mercure.  Capacitated vehicle routing on trees.  Oper. Res., 39(4):616–622, 1991.
  * [39] Eugene Lawler.  Combinatorial Optimization: Networks and Matroids.  Holt, Rinehart and Winston, 1976.
  * [40] Chung-Lun Li and David Simchi-Levi.  Worst-case analysis of heuristics for multidepot capacitated vehicle routing problems.  INFORMS J. Comput., 2(1):64–73, 1990.
  * [41] Claire Mathieu and Hang Zhou.  Probabilistic analysis of euclidean capacitated vehicle routing.  In ISAAC 2021, volume 212 of LIPIcs, pages 43:1–43:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [42] Claire Mathieu and Hang Zhou.  A PTAS for capacitated vehicle routing on trees.  In ICALP 2022, volume 229 of LIPIcs, pages 95:1–95:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [43] Claire Mathieu and Hang Zhou.  A tight $\left(\frac{3}{2}+\varepsilon\right)$-approximation for unsplittable capacitated vehicle routing on trees.  CoRR, abs/2202.05691, 2022.
  * [44] Tobias Mömke and Hang Zhou.  Capacitated vehicle routing in graphic metrics.  CoRR, abs/2210.09806, 2022.
  * [45] Robert Clay Prim.  Shortest connection networks and some generalizations.  The Bell System Technical Journal, 36(6):1389–1401, 1957.
  * [46] Anatolii Ivanovich Serdyukov.  Some extremal bypasses in graphs.  Upravlyaemye Sistemy, 17:76–79, 1978.
  * [47] Paolo Toth and Daniele Vigo.  Vehicle routing: problems, methods, and applications.  SIAM, 2014.
  * [48] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian.  New benchmark instances for the capacitated vehicle routing problem.  European Journal of Operational Research, 257(3):845–858, 2017\.

##  Appendix A The Approximation Ratio of Bompadre _et al._ ’s Algorithm

######  Lemma 54 (Bompadre _et al._ [16], Section 3.2.3).

For splittable and unit-demand $k$-CVRP with $k\geq 3$, given an
$\alpha$-approximation algorithm for metric TSP with $\alpha\geq 1$, there is
an approximation algorithm with a ratio of
$1-\frac{\beta}{\beta+1}+(1-\frac{1}{k})\alpha=\alpha+1-\alpha/k-\Omega(1/k^{3})$,
where $\beta$ is the positive root of the following quadratic equation

$0=(2k^{2}-2k)\beta^{2}+\left(2-\alpha+\frac{\alpha}{k}-\frac{2}{k+1}+2k^{2}-2k\right)\beta+\left(1-\alpha+\frac{\alpha}{k}-\frac{2}{k+1}\right).$

##  Appendix B Calculating the Ratio for Splittable Case

In this section, we will prove the approximation ratio of splittable and unit-
demand $k$-CVRP in [15] is at least $5/2-1.005/3000-1.5/k$.

###  B.1 The Main Idea of the Algorithm

The idea in [15] is to distinguish two kinds of instances.

Fixing a constant $\varepsilon>0$, there are two kinds of instances.

  * •

If $(1-\varepsilon)w(I^{*})\geq(2/k)\Delta$, the instance is _simple_.

  * •

Otherwise, the instance is _difficult_.

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

For hard instances, 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 $H$ on $V\cup\\{v_{0}\\}$ such that
$w(H)\leq(1+f(\varepsilon))w(I^{*})$.

Note that the function $f$ can be seen in Appendix D. The above lemma shows
that we can find a good Hamiltonian cycle in the difficult instances if
$\varepsilon$ is small. Hence, using the AG-ITP algorithm, there will always
be an improvement by making a trade-off between the two kinds of instances.

Given a Hamiltonian cycle $H$ on $V\cup\\{v_{0}\\}$, the weight of the AG-ITP
algorithm in [3] for splittable and unit-demand $k$-CVRP is at most

$(2/k)\Delta+(1-1/k)w(H)\leq(2/k)\Delta+w(H).$

###  B.2 A Simple Analysis

In this subsection, we use the weaker result $(2/k)\Delta+w(H)$ of the AG-ITP
algorithm. We will show the ratio in [15] is at least $5/2-1.005/3000$.

Case 1. For easy instances, by the definition, we have
$(1-\varepsilon)w(I^{*})\geq(2/k)\Delta$. Using an $\alpha$-approximate
Hamiltonian cycle on $V\cup\\{v_{0}\\}$, by Lemma 12, we can get that

$(2/k)\Delta+\alpha w(H^{*})\leq(1-\varepsilon)w(I^{*})+\alpha
w(I^{*})=(\alpha+1-\varepsilon)w(I^{*}).$

Case 2. For hard instances, we have $w(I^{*})\geq(2/k)\Delta$ by Lemma 13.
Using the Hamiltonian cycle $H$ on $V\cup\\{v_{0}\\}$ in Lemma 55, we can get
that

$(2/k)\Delta+w(H)\leq
w(I^{*})+(1+f(\varepsilon))w(I^{*})=(2+f(\varepsilon))w(I^{*}).$

Therefore, the approximation ratio of splittable and unit-demand $k$-CVRP is

$\min_{\varepsilon>0}\max\\{\alpha+1-\varepsilon,\
2+f(\varepsilon)\\}=\alpha+1-\varepsilon^{*},$

where $\varepsilon^{*}$ is the maximum value satisfying
$f(\varepsilon)+\varepsilon\leq\alpha-1$. When $\alpha=3/2$, we have

$1.005/3000-6\times 10^{-9}<\varepsilon^{*}<1.005/3000-5\times 10^{-9}.$

Therefore, the ratio is at least $5/2-1.005/3000$ and it holds
$\varepsilon^{*}<1.005/3000$.

###  B.3 A Tighter Analysis

In the previous subsection, we know the ratio is at least $5/2-1.005/3000$.
Since we consider $k=O(1)$, using the stronger result
$(2/k)\Delta+(1-1/k)w(H)$ of the AG-ITP algorithm, the ratio may be better
under a tighter analysis. However, we will show the improvement is at most
$1.5/k$, i.e., the ratio is at least $5/2-1.005/3000-1.5/k$.

Case 1. For easy instances, by the definition, we have
$(1-\varepsilon)w(I^{*})\geq(2/k)\Delta$. Using an $\alpha$-approximate
Hamiltonian cycle on $V\cup\\{v_{0}\\}$, by Lemma 12, we can get that

$(2/k)\Delta+(1-1/k)\alpha w(H^{*})\leq(1-\varepsilon)w(I^{*})+(1-1/k)\alpha
w(I^{*})=(\alpha+1-\varepsilon-\alpha/k)w(I^{*}).$

Case 2. For hard instances, we have $w(I^{*})\geq(2/k)\Delta$ by Lemma 13.
Using the Hamiltonian cycle $H$ on $V\cup\\{v_{0}\\}$ in Lemma 55, we can get
that

$(2/k)\Delta+(1-1/k)w(H)\leq
w(I^{*})+(1-1/k)(1+f(\varepsilon))w(I^{*})=(1+(1-1/k)(1+f(\varepsilon))w(I^{*}).$

Therefore, the approximation ratio of splittable and unit-demand $k$-CVRP is

$\min_{\varepsilon>0}\max\\{\alpha+1-\varepsilon-\alpha/k,\
1+(1-1/k)(1+f(\varepsilon))\\}=\alpha+1-\varepsilon^{**}-\alpha/k,$

where $\varepsilon^{**}$ is the maximum value satisfying
$(1-1/k)f(\varepsilon)+\varepsilon\leq(1-1/k)(\alpha-1)$.

Recall that $\varepsilon^{*}$ is the maximum value satisfying
$f(\varepsilon)+\varepsilon\leq\alpha-1$. Hence, we have
$f(\varepsilon^{*})+\varepsilon^{*}=\alpha-1$. Therefore, we can get
$(1-1/k)f(\varepsilon^{*})+\varepsilon^{*}=(1-1/k)(\alpha-1-\varepsilon^{*})+\varepsilon^{*}>(1-1/k)(\alpha-1)$.
So, when $\alpha=3/2$, we have $\varepsilon^{**}<\varepsilon^{*}<1.005/3000$.
The ratio satisfies that

$\alpha+1-\varepsilon^{**}-\alpha/k>\alpha+1-\varepsilon^{*}-\alpha/k>5/2-1.005/3000-1.5/k.$

Therefore, a tighter analysis shows that the ratio in [15] is at least
$5/2-1.005/3000-1.5/k$. To show our result $5/2-\Theta(\sqrt{1/k})$ is better
for any $k\leq 1.7\times 10^{7}$, it is sufficient to show that it is better
than $5/2-1.005/3000-1.5/k$ for any $k\leq 1.7\times 10^{7}$.

##  Appendix C Calculating the Ratio for Unsplittable Case

In this section, we will prove the approximation ratio of unsplittable
$k$-CVRP in [25] is at least $5/2+\ln 2+\ln(1-1.005/3000)-3/k$.

Note that the constant part $\ln(1-1.005/3000)$ is obtained by using the
method in [15]. Hence, the idea of analysis is similar. Fixing a constant
$\varepsilon>0$, there are two kinds of instances.

  * •

If $(1-\varepsilon)w(I^{*})\geq(2/k)\Delta$, the instance is _simple_.

  * •

Otherwise, the instance is _difficult_.

Given a Hamiltonian cycle on $V\cup\\{v_{0}\\}$, the weight of the AG-UITP
algorithm in [2] for unsplittable $k$-CVRP with even $k\geq 3$ is at most

$(4/k)\Delta+(1-2/k)w(H)\leq(4/k)\Delta+w(H).$

###  C.1 A Simple Analysis

In this subsection, we use the weaker result $(4/k)\Delta+w(H)$ of the AG-UITP
algorithm. Then, the LP-based algorithm in [25] has weight of at most

$\min_{\gamma\geq 0}\\{\gamma\cdot
w(I^{*})+e^{-\gamma}\cdot(4/k)\Delta+w(H)\\}.$

We will show the ratio is at least $5/2+\ln 2+\ln(1-1.005/3000)$.

Case 1. For easy instances, by the definition, we have
$(1-\varepsilon)w(I^{*})\geq(2/k)\Delta$. Using an $\alpha$-approximate
Hamiltonian cycle on $V\cup\\{v_{0}\\}$, by Lemma 12, we can get that

$\gamma\cdot w(I^{*})+e^{-\gamma}\cdot(4/k)\Delta+\alpha
w(H^{*})\leq\gamma\cdot w(I^{*})+e^{-\gamma}\cdot
2(1-\varepsilon)w(I^{*})+\alpha w(I^{*})=(\gamma+e^{-\gamma}\cdot
2(1-\varepsilon)+\alpha)w(I^{*}).$

The ratio is

$\min_{\gamma\geq 0}\\{\gamma+e^{-\gamma}\cdot
2(1-\varepsilon)+\alpha\\}=\alpha+1+\ln 2+\ln(1-\varepsilon).$

Case 2. For hard instances, we have $w(I^{*})\geq(2/k)\Delta$ by Lemma 13.
Using the Hamiltonian cycle $H$ on $V\cup\\{v_{0}\\}$ in Lemma 55, we can get
that

$\gamma\cdot w(I^{*})+e^{-\gamma}\cdot(4/k)\Delta+w(H)\leq\gamma\cdot
w(I^{*})+e^{-\gamma}\cdot
2w(I^{*})+(1+f(\varepsilon))w(I^{*})=(\gamma+e^{-\gamma}\cdot
2+1+f(\varepsilon))w(I^{*}).$

The ratio is

$\min_{\gamma\geq 0}\\{\gamma+e^{-\gamma}\cdot 2+1+f(\varepsilon)\\}=2+\ln
2+f(\varepsilon).$

Therefore, the ratio is

$\min_{\varepsilon>0}\max\\{\alpha+1+\ln 2+\ln(1-\varepsilon),\ 2+\ln
2+f(\varepsilon)\\}=\alpha+1+\ln 2+\ln(1-\varepsilon^{*}),$

where $\varepsilon^{*}$ is the maximum value satisfying
$f(\varepsilon)-\ln(1-\varepsilon)\leq\alpha-1$. When $\alpha=3/2$, we also
have

$1.005/3000-6\times 10^{-9}<\varepsilon^{*}<1.005/3000-5\times 10^{-9}.$

Therefore, the ratio is at least $5/2+\ln 2+\ln(1-1.005/3000)$ and it holds
$\varepsilon^{*}<1.005/3000$.

###  C.2 A Tighter Analysis

In this subsection, using the stronger result $(4/k)\Delta+(1-2/k)w(H)$ of the
AG-ITP algorithm, we will show the ratio is at least $5/2+\ln
2+\ln(1-1.005/3000)-3/k$.

Case 1. For easy instances, by the definition, we have
$(1-\varepsilon)w(I^{*})\geq(2/k)\Delta$. Using an $\alpha$-approximate
Hamiltonian cycle on $V\cup\\{v_{0}\\}$, by Lemma 12, we can get that

$\gamma\cdot w(I^{*})+e^{-\gamma}\cdot(4/k)\Delta+(1-2/k)\alpha
w(H^{*})\leq(\gamma+e^{-\gamma}\cdot 2(1-\varepsilon)+(1-2/k)\alpha)w(I^{*}).$

The ratio is

$\min_{\gamma\geq 0}\\{\gamma+e^{-\gamma}\cdot
2(1-\varepsilon)+(1-2/k)\alpha\\}=\alpha+1+\ln
2+\ln(1-\varepsilon)-2\alpha/k.$

Case 2. For hard instances, we have $w(I^{*})\geq(2/k)\Delta$ by Lemma 13.
Using the Hamiltonian cycle $H$ on $V\cup\\{v_{0}\\}$ in Lemma 55, we can get
that

$\gamma\cdot
w(I^{*})+e^{-\gamma}\cdot(4/k)\Delta+(1-2/k)w(H)\leq(\gamma+e^{-\gamma}\cdot
2+(1-2/k)(1+f(\varepsilon)))w(I^{*}).$

The ratio is

$\min_{\gamma\geq 0}\\{\gamma+e^{-\gamma}\cdot
2+(1-2/k)(1+f(\varepsilon))\\}=1+\ln 2+(1-2/k)(1+f(\varepsilon)).$

Therefore, the ratio is

$\min_{\varepsilon>0}\max\\{\alpha+1+\ln 2+\ln(1-\varepsilon)-2\alpha/k,\
1+\ln 2+(1-2/k)(1+f(\varepsilon))\\}=\alpha+1+\ln
2+\ln(1-\varepsilon^{**})-2\alpha/k,$

where $\varepsilon^{**}$ is the maximum value satisfying
$(1-2/k)f(\varepsilon)-\ln(1-\varepsilon)\leq(1-2/k)(\alpha-1)$.

Recall that $\varepsilon^{*}$ is the maximum value satisfying
$f(\varepsilon)-\ln(1-\varepsilon)\leq\alpha-1$. Hence, we have
$f(\varepsilon^{*})-\ln(1-\varepsilon^{*})=\alpha-1$. Therefore, we can get
$(1-2/k)f(\varepsilon^{*})-\ln(1-\varepsilon^{*})=(1-2/k)(\alpha-1+\ln(1-\varepsilon^{*}))-\ln(1-\varepsilon^{*})>(1-2/k)(\alpha-1)$.
So, when $\alpha=3/2$, we have $\varepsilon^{**}<\varepsilon^{*}<1.005/3000$.
Therefore, the ratio is

$\alpha+1+\ln 2+\ln(1-\varepsilon^{**})-2\alpha/k>5/2+\ln
2+\ln(1-\varepsilon^{*})-3/k>5/2+\ln 2+\ln(1-1.005/3000)-3/k.$

Therefore, a tighter analysis shows the ratio in [25] is at least $5/2+\ln
2+\ln(1-1.005/3000)-3/k$ for unsplittable $k$-CVRP with even $k\geq 3$. Note
that for odd $k\geq 3$, using a similar argument, we know the ratio is at
least $5/2+\ln 2+\ln(1-1.005/3000)-1.5/k$. To show our result $5/2+\ln
2-\Theta(\sqrt{1/k})$ is better for any $k\leq 1.7\times 10^{7}$, it is
sufficient to show that it is better than $5/2+\ln 2+\ln(1-1.005/3000)-3/k$
for even $k\leq 1.7\times 10^{7}$ and better than $5/2+\ln
2+\ln(1-1.005/3000)-1.5/k$ for odd $k\leq 1.7\times 10^{7}$.

##  Appendix D The Function

Letting

$\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).$

There are two functions $f$ and $f^{\prime}$ in [15]. The first function $f$
proposed in an LP-based algorithm has a better result but runs in a slow
polynomial time. Note that we only use the function $f$. The function $f$,
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.$

Note that in their paper $\theta$ is let to be $1-\tau$ [15]. But it is
slightly better to be

$\theta=\min\left\\{\frac{1}{\sqrt{\frac{3\varepsilon}{2+\zeta}}+1},1-\tau\right\\}.$

The second result proposed in a combinatorial algorithm has a slightly worse
result but runs in a faster $O(n^{3})$ time. The function $f^{\prime}$
satisfies that

$f^{\prime}(\varepsilon)=\min_{\begin{subarray}{c}\gamma>2\\\ 0<\tau,\rho\leq
1/6\end{subarray}}\left\\{\frac{1+\zeta}{1-\tau}+\frac{8}{\gamma-2}+\varepsilon\cdot\left(4+\frac{8}{\gamma-2}+2\gamma-\frac{\tau}{\tau-1}\right)+\frac{3\rho}{(1-\rho)\cdot(1-\tau)}\right\\}-1.$

We can determine $\gamma$ to be

$\gamma=2\sqrt{1+\frac{1}{\varepsilon}}+2.$