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

Zipei Nie¹¹1Lagrange Mathematics and Computing Research Center, Huawei; Institut des Hautes Études Scientifiques, Paris, France, email: [email protected]. Hang Zhou²²2École Polytechnique, Institut Polytechnique de Paris, France, email: [email protected].

Abstract

We study the unit-demand capacitated vehicle routing problem in the random setting of the Euclidean plane. The objective is to visit $n$ random terminals in a square using a set of tours of minimum total length, such that each tour visits the depot and at most $k$ terminals.

We design an elegant algorithm combining the classical sweep heuristic and Arora’s framework for the Euclidean traveling salesman problem [Journal of the ACM 1998]. We show that our algorithm is a polynomial-time approximation of ratio at most $1.55$ asymptotically almost surely. This improves on previous approximation ratios of $1.995$ due to Bompadre, Dror, and Orlin [Journal of Applied Probability 2007] and $1.915$ due to Mathieu and Zhou [Random Structures and Algorithms 2022]. In addition, we conjecture that, for any $\varepsilon>0$ , our algorithm is a $(1+\varepsilon)$ -approximation asymptotically almost surely.

1 Introduction

In the unit-demand capacitated vehicle routing problem (CVRP), we are given a set $V$ of $n$ terminals and a depot $O$ . The terminals and the depot are located in some metric space. There is an unlimited number of identical vehicles, each of an integer capacity $k$ . The tour of a vehicle starts at the depot and returns there after visiting at most $k$ terminals. The objective is to visit every terminal, using a set of tours of minimum total length. Unless explicitly mentioned, for all CVRP instances in this paper, each terminal is assumed to have unit demand. Vehicle routing is a basic type of problems in operations research, and several books (see [4, 24, 31, 56] among others) have been written on those problems.

We study the Euclidean version of the CVRP, in which all locations (the terminals and the depot) lie in the two-dimensional plane, and the distances are given by the Euclidean metric. The Euclidean CVRP is a generalization of the Euclidean traveling salesman problem and is known to be NP-hard for all $k\geq 3$ (see [12]). Surprisingly, as stated in a survey of Arora [10], the Euclidean CVRP is the first problem resisting Arora’s famous framework on approximation schemes [9]. Whether there is a polynomial-time $(1+\varepsilon)$ -approximation for the Euclidean CVRP for any $\varepsilon>0$ is a fundamental question and remains open regardless of numerous efforts for several decades, e.g., [1, 10, 12, 26, 32, 33, 36, 39, 46].

Given the difficult challenges in the Euclidean CVRP, researchers turned to an analysis beyond worst case, by making some probabilistic assumptions on the distribution of the input instance. In 1985, Haimovich and Rinnooy Kan [33] first studied this problem in the random setting, where the terminals are $n$ independent, identically distributed (i.i.d.) uniform random points in $[0,1]^{2}$ . An event $\mathcal{E}$ occurs asymptotically almost surely (a.a.s.) if $\lim_{n\to\infty}\mathbb{P}[\mathcal{E}]=1$ . It is a long-standing open question whether, in the random setting, there is a polynomial-time $(1+\varepsilon)$ -approximation for the Euclidean CVRP a.a.s. for any $\varepsilon>0$ . Haimovich and Rinnooy Kan [33] introduced the classical iterated tour partitioning (ITP) algorithm, and they raised the question whether, in the random setting, ITP is a $(1+\varepsilon)$ -approximation a.a.s. for any $\varepsilon>0$ . Bompadre, Dror, and Orlin [21] showed that, in the random setting, the approximation ratio of ITP is at most 1.995 a.a.s. Recently, Mathieu and Zhou [45] showed that, in the random setting, the approximation ratio of ITP is at most 1.915 and at least $1+c_{0}$ , for some constant $c_{0}>0$ , a.a.s. Consequently, designing a $(1+\varepsilon)$ -approximation in the random setting for any $\varepsilon>0$ would require new algorithmic insights.

Theoretical and Practical Perspectives.

Almost all CVRP algorithms that have theoretical guarantees in the Euclidean plane are (either completely or partially) based on ITP, e.g. [1, 2, 3, 12, 19, 20, 21, 26, 28, 32, 42, 45]. However, ITP is seldom used in industry, because its practical performance is not as good as many other heuristics [50].

In this paper, we design an elegant algorithm (Algorithm 1) that is completely different from ITP. Our algorithm is inspired by the classical sweep heuristic (see Section 1.3), one of the most popular heuristics in practice. Interestingly, we show that, in the random setting, our algorithm achieves the best-to-date theoretical performance, and leads to a significant progress towards a $(1+\varepsilon)$ -approximation for any $\varepsilon>0$ . See Section 1.1.

1.1 Our Results

Algorithm.

We present a simple polynomial-time algorithm for the Euclidean CVRP. See Algorithm 1. For each terminal $v$ , let $\theta(v)\in[0,2\pi)$ denote the polar angle of $v$ with respect to $O$ . First, we sort all terminals in nondecreasing order of $\theta(v)$ . Let $M\geq 1$ be a constant integer parameter. Then we decompose the sorted sequence into subsequences, each consisting of $Mk$ consecutive terminals, except possibly for the last subsequence containing less terminals. Next, for the terminals in each subsequence, we compute a near-optimal solution to the CVRP using Arora’s framework for the Euclidean traveling salesman problem [9], see also Section 1.4.

Input: set

V

n

terminals in

\mathbb{R}^{2}

, depot

O\in\mathbb{R}^{2}

, capacity

k\in\{1,2,\dots,n\}

Output: set of tours covering all terminals in

V

1 Sort the terminals in

V

into

u_{1},u_{2},\dots,u_{n}

such that

\theta(u_{1})\leq\theta(u_{2})\leq\cdots\leq\theta(u_{n})

2for $i\leftarrow 1$ to $\left\lceil\frac{n}{Mk}\right\rceil$ do

V_{i}\leftarrow\left\{u_{j}:(i-1)\cdot Mk<j\leq i\cdot Mk\right\}

4 Compute a

\left(1+\frac{1}{M}\right)

-approximate solution

S_{i}

to the subproblem

(V_{i},O,k)

\triangleright

Lemma 7

return union of all

S_{i}

Algorithm 1 Algorithm for the CVRP in

\mathbb{R}^{2}

. Constant integer parameter

M\geq 1

Our main result shows that, in the random setting, Algorithm 1 has an approximation ratio at most $1.55$ a.a.s., see Theorem 1. This improves on previous ratios of $1.995$ due to Bompadre, Dror, and Orlin [21] and $1.915$ due to Mathieu and Zhou [45]. Furthermore, we conjecture that, in the random setting, Algorithm 1 is a $(1+\varepsilon)$ -approximation for any $\varepsilon>0$ a.a.s., see 2.

Theorem 1.

Consider the unit-demand Euclidean CVRP with a set $V$ of $n$ terminals that are i.i.d. uniform random points in $[0,1]^{2}$ , a fixed depot $O\in\mathbb{R}^{2}$ , and a capacity $k$ that takes an arbitrary value in $\{1,2,\dots,n\}$ . For any constant integer $M\geq 10^{5}$ , Algorithm 1 with parameter $M$ is a polynomial-time approximation of ratio at most $1.55$ asymptotically almost surely.

Conjecture 2.

Consider the unit-demand Euclidean CVRP with $V$ , $O$ , and $k$ defined in Theorem 1. For any $\varepsilon>0$ , there exists a positive constant integer $M$ depending on $\varepsilon$ , such that Algorithm 1 with parameter $M$ is a polynomial-time $(1+\varepsilon)$ -approximation asymptotically almost surely.

1.2 Overview of Techniques

A main contribution in our analysis is the novel concepts of $R$ -radial cost and $R$ -local cost. These are generalizations of the classical radial cost and local cost introduced by Haimovich and Rinnooy Kan [33].

Definition 3 ( $R$ -radial cost).

For any $R\in\mathbb{R}^{+}\cup\left\{0,\infty\right\}$ , define the $R$ -radial cost $\mathrm{rad}_{R}$ by

\mathrm{rad}_{R}:=\frac{2}{k}\sum_{v\in V}\min\left\{d(O,v),R\right\}.

Definition 4 ( $R$ -local cost).

For any $R\in\mathbb{R}^{+}\cup\left\{0,\infty\right\}$ , define the $R$ -local cost $T^{*}_{R}$ as the minimum cost of a traveling salesman tour on the set of points $\left\{v\in V:d(O,v)\geq R\right\}$ .

Using the $R$ -radial cost and the $R$ -local cost, we establish a new lower bound (Theorem 5) on the cost of an optimal solution. This lower bound is a main novelty of the paper. It unites both classical lower bounds from [33]: when $R=0$ , it leads asymptotically to one classical lower bound, which is the local cost; and when $R=\infty$ , it leads asymptotically to the other classical lower bound, which is the radial cost. The proof of Theorem 5 is in Section 2.

Theorem 5.

Consider the unit-demand Euclidean CVRP with any set $V$ of $n$ terminals in $\mathbb{R}^{2}$ , any depot $O\in\mathbb{R}^{2}$ , and any capacity $k\in\mathbb{N}^{+}$ . Let $\mathrm{opt}$ denote the cost of an optimal solution. For any $R\in\mathbb{R}^{+}\cup\left\{0,\infty\right\}$ , we have

\mathrm{opt}\geq T^{*}_{R}+\mathrm{rad}_{R}-{\frac{3\pi D}{2}},

where $D$ denotes the diameter of $V\cup\{O\}$ .

Next, we establish an upper bound (Theorem 6) on the cost of the solution in Algorithm 1 using the $0$ -local cost and the $\infty$ -radial cost. The proof of Theorem 6 is in Section 3.

Theorem 6.

Consider the unit-demand Euclidean CVRP with any set $V$ of $n$ terminals in $\mathbb{R}^{2}$ , any depot $O\in\mathbb{R}^{2}$ , and any capacity $k\in\mathbb{N}^{+}$ . For any positive integer $M$ , let $\mathrm{sol}(M)$ denote the cost of the solution returned by Algorithm 1 with parameter $M$ . Then we have

\mathrm{sol}(M)\leq\left(1+\frac{1}{M}\right)\left(T_{0}^{*}+\mathrm{rad}_{\infty}+\frac{3\pi D}{2}\left\lceil\frac{n}{Mk}\right\rceil\right),

where $D$ denotes the diameter of $V\cup\{O\}$ .

Note that both Theorem 5 and Theorem 6 hold for any set of terminals, not only in the random setting, and can be of independent interest.

In the random setting, in order to compute the approximation ratio of Algorithm 1, we set $R$ to be some well-chosen value so that the ratio between the upper bound (Theorem 6) and the lower bound (Theorem 5) is small. The proof of Theorem 1 is in Section 4 and relies on two technical inequalities proved in Appendix A.

Remark.

In the random setting, the term containing $D$ in the bound in Theorem 5 (resp. Theorem 6) becomes negligible. The upper bound in Theorem 6 is then asymptotically identical to the upper bound for the ITP algorithm established in [3]. As an immediate consequence, one can prove that the approximation ratio of ITP is at most $1.55$ using a similar analysis as in this paper. Note that the upper bound for ITP established in [3] is tight [45, Lemma 7], and the tightness is exploited to show that ITP is at best a $(1+c_{0})$ -approximation for some constant $c_{0}>0$ [45]. However, we are not aware of any instance on which the upper bound in Theorem 6 is tight for Algorithm 1, and we believe that the performance of Algorithm 1 is actually better than the announced upper bound.

1.3 Related Work

Sweep Heuristic.

The classical sweep heuristic is well-known and commercially available for vehicle routing problems in the plane. At the beginning, all terminals are sorted according to their polar angles with respect to the depot. For each $k$ consecutive terminals in the sorted sequence, a tour is obtained by computing a traveling salesman tour (exactly or approximately) on those terminals. Some implementations include a post-optimization phase in which vertices in adjacent tours may be exchanged to reduce the overall cost. The first mentions of this type of method are found in a book by Wren [57] and in a paper by Wren and Holliday [58], while the sweep heuristic is commonly attributed to Gillett and Miller [30] who popularized it. See also surveys [23, 40, 41] and the book [56].

Our algorithm (Algorithm 1) is an adaptation of the sweep heuristic: instead of forming groups each of $k$ consecutive terminals, we form groups each of $Mk$ consecutive terminals, for some positive constant integer $M$ . Then for each group, we compute a solution consisting of a constant number of tours using Arora’s framework [9]. Note that it is possible to replace Arora’s framework by a heuristic in order to make our algorithm more practical.

Our algorithm is simple, so it can be easily adapted to other vehicle routing problems, e.g., distance-constrained vehicle routing [27, 29, 43, 49].

Euclidean CVRP.

Despite the difficulty of the Euclidean CVRP, there has been progress on several special cases in the deterministic setting. A series of papers designed polynomial-time approximation schemes (PTAS’s) for small $k$ : Haimovich and Rinnooy Kan [33] gave a PTAS when $k$ is constant; Asano et al. [12] extended the techniques in [33] to achieve a PTAS for $k=O(\log n/\log\log n)$ ; and Adamaszek, Czumaj, and Lingas [1] designed a PTAS for $k\leq 2^{\log^{f(\varepsilon)}(n)}$ . For higher dimensional Euclidean metrics, Khachay and Dubinin [39] gave a PTAS for fixed dimension $\ell$ and $k=O(\log^{\frac{1}{\ell}}(n))$ . For arbitrary $k$ and the two-dimensional plane, Das and Mathieu [26] designed a quasi-polynomial time approximation scheme, whose running time was recently improved to $n^{O(\log^{6}(n)/\varepsilon^{5})}$ by Jayaprakash and Salavatipour [36].

Probabilistic Analyses.

The random setting in which the terminals are i.i.d. uniform random points is perhaps the most natural probabilistic setting. The Euclidean CVRP in the random setting has been studied in several special cases. In one special case when the capacity is infinite, Karp [37] gave a polynomial-time $(1+\varepsilon)$ -approximation a.a.s. for any $\varepsilon>0$ . In another special case when $k$ is fixed, Rhee [51] and Daganzo [25] analyzed the value of an optimal solution.

CVRP in Other Metrics.

The CVRP has been extensively studied on general metrics [3, 19, 20, 33, 42], trees and bounded treewidth [11, 14, 18, 36, 46], planar and bounded-genus graphs [15, 17, 22], graphic metrics [48], graphs of bounded highway dimension [16], and minor-free graphs [22].

CVRP with Arbitrary Demands.

A natural way to generalize the unit demand version of the CVRP is to allow terminals to have arbitrary unsplittable demands, which is called the unsplittable version of the CVRP. On general metrics, Altinkemer and Gavish [2] first studied the approximation of this problem. Recently, the approximation ratio was improved by Blauth, Traub, and Vygen [19], and further by Friggstad, Mousavi, Rahgoshay, and Salavatipour [28]. This problem has also been studied in the Euclidean plane by Grandoni, Mathieu, and Zhou [32] and on trees by Mathieu and Zhou [47].

1.4 Notations and Preliminaries

For any two points $u$ and $v$ in $\mathbb{R}^{2}$ , let $d(u,v)$ denote the distance between $u$ and $v$ in $\mathbb{R}^{2}$ . For any curve $s$ in $\mathbb{R}^{2}$ , let $\left\lVert s\right\lVert$ denote the length of $s$ ; and for any set $S$ of curves in $\mathbb{R}^{2}$ , let $\left\lVert S\right\lVert:=\sum_{s\in S}\left\lVert s\right\lVert$ . For any set $U$ of points in $\mathbb{R}^{2}$ , the convex hull of $U$ is the minimal convex set in $\mathbb{R}^{2}$ containing $U$ .

Arora’s Framework.

The following lemma gives a PTAS for the Euclidean CVRP when the capacity $k$ is at least a constant fraction of the number of terminals. Its proof is a straightforward adaptation of Arora’s framework [9] for the Euclidean TSP.

Lemma 7 (adaptation of [9]).

Let $M\geq 1$ be an integer constant. Consider the unit-demand Euclidean capacitated vehicle routing problem with any finite set $U$ of terminals in $\mathbb{R}^{2}$ , any depot $O\in\mathbb{R}^{2}$ , and any capacity $k$ such that $|U|\leq Mk$ . Then there exists a polynomial-time $\left(1+\frac{1}{M}\right)$ -approximation algorithm.

Proof.

Recall that Arora’s algorithm defines a randomized hierarchical quadtree decomposition, such that a near-optimal solution intersects the boundary of each square only $O_{M}(1)$ times and those crossings happen at one of a small set of prespecified points, called portals, and then uses a polynomial time dynamic program to find the best solution with this structure.

In [12] it was observed that, when the number of tours in an optimal solution is $O_{M}(1)$ , there is a near-optimal solution in which the overall number of subtours passing through each square (via portals) is $O_{M}(1)$ . Furthermore, one can guess the number of terminals covered by each such subtour within a polynomial number of options. This leads to a polynomial number of configurations of subtours inside each square, which ensures the polynomial running time of a natural dynamic program. ∎

2 Proof of Theorem 5

Let $\mathrm{OPT}$ denote an optimal solution to the CVRP. Let $C$ denote the circle centered at $O$ with radius $R$ . Suppose that the union of the tours in $\mathrm{OPT}$ intersects $C$ at $2t$ points, denoted by $y_{1},y_{2},\ldots,y_{2t}$ in clockwise order. For notational convenience, we let $y_{2t+1}:=y_{1}$ . Let $D^{\prime}$ denote the diameter³³3We adopt the convention that the diameter of an empty set is zero. of $\{y_{i}:1\leq i\leq 2t\}$ . Let $C_{1},C_{2},\ldots,C_{t}$ be $t$ continuous curves that correspond to the intersection between $\mathrm{OPT}$ and the closure of the exterior of $C$ .

Lemma 8.

We have

\sum_{i=1}^{t}\left\lVert C_{i}\right\lVert\geq T_{R}^{*}-\frac{3\pi D^{\prime}}{2}.

Proof.

Let $Z$ denote the set of segments $y_{i}y_{i+1}$ for all $1\leq i\leq 2t$ . Let $Z_{\rm{odd}}$ (resp. $Z_{\rm{even}}$ ) denote the set of segments $y_{i}y_{i+1}$ for all $1\leq i\leq 2t$ such that $i$ is odd (resp. even). Let $Z^{*}$ be one of $Z_{\rm{odd}}$ and $Z_{\rm{even}}$ that has a smaller total length, breaking ties arbitrarily. Let $W$ denote the union of the curves $C_{1},C_{2},\ldots,C_{t}$ , the segments in $Z$ , and the segments in $Z^{*}$ . Then $W$ is a connected graph with no odd degree vertices. So $W$ has an Eulerian path. Since $W$ visits all vertices $v\in V$ such that $d(O,v)\geq R$ , the total length of $W$ is at least $T_{R}^{*}$ by Definition 4. Hence

\left\lVert Z\right\lVert+\left\lVert Z^{*}\right\lVert+\sum_{i=1}^{t}\left\lVert C_{i}\right\lVert\geq T^{*}_{R}.

We note that $\left\lVert Z\right\lVert$ equals to the perimeter of the convex hull of $\{y_{i}:1\leq i\leq 2t\}$ , which is at most $\pi D^{\prime}$ by [55]. Since $\left\lVert Z^{*}\right\lVert\leq\frac{1}{2}\left\lVert Z\right\lVert$ , we have

\left\lVert Z\right\lVert+\left\lVert Z^{*}\right\lVert\leq\frac{3\left\lVert Z\right\lVert}{2}\leq\frac{3\pi D^{\prime}}{2}.

The claim follows. ∎

The following lemma introduces a key new idea in our paper.

Lemma 9.

Let $s$ be any tour in $\mathrm{OPT}$ . Let $V_{s}\subseteq V$ denote the set of points in $V$ that are visited by $s$ . Let $U_{s}\subseteq\left\{1,2,\ldots,t\right\}$ denote the set of indices $i$ such that $C_{i}$ is part of $s$ . We have

\left\lVert s\right\lVert\geq\sum_{i\in U_{s}}\left\lVert C_{i}\right\lVert+\frac{2}{k}\sum_{v\in V_{s}}\min\left\{d(O,v),R\right\}.

(1)

Proof.

There are two scenarios to consider.

First, if $U_{s}$ is empty, then we have

\left\lVert s\right\lVert\geq 2\max_{v\in V_{s}}d(O,v)\geq\frac{2}{|V_{s}|}\sum_{v\in V_{s}}\min\left\{d(O,v),R\right\}.

The claim follows since $|V_{s}|\leq k$ .

Second, if $U_{s}$ is nonempty, then the tour $s$ must first travel through a path to a point on $C$ , paying at least $R$ , then visit all curves $C_{i}$ for $i\in U_{s}$ , and finally, travel from a point on $C$ back to the depot, paying at least $R$ . Thus we have

\left\lVert s\right\lVert\geq 2R+\sum_{i\in U_{s}}\left\lVert C_{i}\right\lVert.

The claim follows since $\displaystyle 2R\geq\frac{2}{|V_{s}|}\sum_{v\in V_{s}}\min\left\{d(O,v),R\right\}$ and $|V_{s}|\leq k$ . ∎

Summing (1) over all tours $s\in\mathrm{OPT}$ , we have

	$\displaystyle\mathrm{opt}=$	$\displaystyle\sum_{s\in\mathrm{OPT}}\left\lVert s\right\lVert$
	$\displaystyle\geq$	$\displaystyle\sum_{s\in\mathrm{OPT}}\sum_{i\in U_{s}}\left\lVert C_{i}\right\lVert+\frac{2}{k}\sum_{s\in\mathrm{OPT}}\sum_{v\in V_{s}}\min\left\{d(O,v),R\right\}$
	$\displaystyle=$	$\displaystyle\sum_{i=1}^{t}\left\lVert C_{i}\right\lVert+\frac{2}{k}\sum_{v\in V}\min\left\{d(O,v),R\right\}$
	$\displaystyle\geq$	$\displaystyle T_{R}^{*}-\frac{3\pi D^{\prime}}{2}+\mathrm{rad}_{R},$

where the last inequality follows from LABEL:{lem:sum-Ci} and the definition of $R$ -radial cost (Definition 3). Since each $y_{i}$ lies in the convex hull of $V\cup O$ , we have $D^{\prime}\leq D$ , so the claim in Theorem 5 follows.

Remark.

One can show that $D^{\prime}$ is at most the diameter of $V$ . This is because each $y_{i}$ is contained in the projection of the convex hull of $V$ onto the disk enclosed by $C$ , and the projection onto any closed convex set is $1$ -Lipschitz⁴⁴4We say that a function $f$ is $1$ -Lipschitz if $d(f(x),f(y))\leq d(x,y)$ for all $x$ and $y$ .; see [53, Theorem 1.2.4] for example.

3 Proof of Theorem 6

Let $i$ be any integer with $1\leq i\leq\left\lceil\frac{n}{Mk}\right\rceil$ . Let the point set $V_{i}$ and the solution $S_{i}$ be defined in Algorithm 1. Let $S_{i}^{*}$ denote an optimal solution to the subproblem $(V_{i},O,k)$ . Since $S_{i}$ is a $\left(1+\frac{1}{M}\right)$ -approximate solution, we have $\left\lVert S_{i}\right\lVert\leq\left(1+\frac{1}{M}\right)\cdot\left\lVert S_{i}^{*}\right\lVert$ . Let $\mathrm{TSP}_{i}$ denote the minimum cost of a traveling salesman tour on the set of points $V_{i}\cup\{O\}$ . By [3, Lemma 2], we have

\left\lVert S_{i}^{*}\right\lVert\leq\mathrm{TSP}_{i}+\frac{2}{k}\sum_{v\in V_{i}}d(O,v).

Thus

\left\lVert S_{i}\right\lVert\leq\left(1+\frac{1}{M}\right)\left(\mathrm{TSP}_{i}+\frac{2}{k}\sum_{v\in V_{i}}d(O,v)\right).

(2)

Let $t^{*}$ be an optimal traveling salesman tour on the set of points $V$ . If the polar angles of points in $V_{i}$ have a span of at most $\pi$ , let $Y_{i}$ be the interior of the convex hull of $V_{i}\cup\{O\}$ ; otherwise, let $Y_{i}$ be the exterior of the convex hull of $(V\setminus V_{i})\cup\{O\}$ . By [37, Theorem 3]⁵⁵5Although [37, Theorem 3] assumes that $Y$ is a rectangle, the arguments extend trivially to any polygon or the exterior of any polygon., we have

\mathrm{TSP}_{i}-\left\lVert t^{*}\cap Y_{i}\right\lVert\leq\frac{3}{2}\;\mathrm{per}(Y_{i}),

where $\mathrm{per}(Y_{i})$ denotes the perimeter of $Y_{i}$ . Since either $Y_{i}$ or the complement of $Y_{i}$ is convex with diameter at most $D$ , the perimeter of $Y_{i}$ is at most $\pi D$ by [55]. Thus

\mathrm{TSP}_{i}\leq\left\lVert t^{*}\cap Y_{i}\right\lVert+\frac{3\pi D}{2}.

(3)

In order to bound $\sum_{i}\left\lVert t^{*}\cap Y_{i}\right\lVert$ , we need the following lemma.

Lemma 10.

For any $i$ and $j$ with $1\leq i<j\leq\left\lceil\frac{n}{Mk}\right\rceil$ , $Y_{i}$ and $Y_{j}$ do not intersect.

Proof.

For each $v\in V$ , let $\theta(v)\in[0,2\pi)$ denote the polar angle of $v$ respect to $O$ . By the definition of $V_{i}$ and $V_{j}$ , we have

0\leq\max_{v\in V_{i}}\theta(v)\leq\max_{v\in V_{j}}\theta(v)<2\pi.

(4)

Hence either

\max_{v\in V_{i}}\theta(v)-\min_{v\in V_{i}}\theta(v)\leq\pi

(5)

\max_{v\in V_{j}}\theta(v)-\min_{v\in V_{j}}\theta(v)\leq\pi.

(6)

If only (5) holds, then by definition, $Y_{i}$ is the interior of the convex hull of $V_{i}\cup\{O\}$ , which is contained in the exterior of the convex hull of $(V\setminus V_{j})\cup\{O\}$ . Thus $Y_{i}$ and $Y_{j}$ do not intersect.

If only (6) holds, then $Y_{i}$ and $Y_{j}$ do not intersect for the same argument.

Suppose that both (5) and (6) hold. Let $Z_{i}$ be the set

Z_{i}:=\left\{x\in\mathbb{R}^{2}:\max_{v\in V_{i}}\theta(v)<\theta(x)<\min_{v\in V_{i}}\theta(v)\right\},

and $Z_{j}$ be the set

Z_{j}:=\left\{x\in\mathbb{R}^{2}:\max_{v\in V_{j}}\theta(v)<\theta(x)<\min_{v\in V_{j}}\theta(v)\right\}.

Then by (5) and (6), $Z_{i}$ and $Z_{j}$ are convex sets. By the definition of $Y_{i}$ and $Y_{j}$ , we have $Y_{i}\subset Z_{i}$ and $Y_{j}\subset Z_{j}$ . Since $Z_{i}$ and $Z_{j}$ do not intersect, $Y_{i}$ and $Y_{j}$ do not intersect. ∎

Therefore, we have

	$\displaystyle\mathrm{sol}(M)=$	$\displaystyle\sum_{i=1}^{\left\lceil\frac{n}{Mk}\right\rceil}\left\lVert S_{i}\right\lVert$
	$\displaystyle\leq$	$\displaystyle\left(1+\frac{1}{M}\right)\left(\sum_{i=1}^{\left\lceil\frac{n}{Mk}\right\rceil}\mathrm{TSP}_{i}+\frac{2}{k}\sum_{v\in V}d(O,v)\right)$
	$\displaystyle\leq$	$\displaystyle\left(1+\frac{1}{M}\right)\left(\sum_{i=1}^{\left\lceil\frac{n}{Mk}\right\rceil}\left\lVert t^{*}\cap Y_{i}\right\lVert+\frac{3\pi D}{2}\left\lceil\frac{n}{Mk}\right\rceil+\mathrm{rad}_{\infty}\right),$

where the first inequality follows from (2) and the fact that $\bigcup_{i}V_{i}=V$ , and the last inequality follows from (3) and the definition of $\infty$ -radial cost (Definition 3). Using Lemma 10 and the definition of $0$ -local cost (Definition 4), we have

\sum_{i=1}^{\left\lceil\frac{n}{Mk}\right\rceil}\left\lVert t^{*}\cap Y_{i}\right\lVert\leq\left\lVert t^{*}\right\lVert=T_{0}^{*}.

The claim follows.

4 Proof of Theorem 1

In this section, we prove a strong law for the approximation ratio of Algorithm 1, as presented in Theorem 11. The setting is similar to those in the main results of [13] and [33]. Since almost sure convergence implies convergence in probability, Theorem 11 implies Theorem 1.

Theorem 11.

Let $v_{1},v_{2},\ldots$ be an infinite sequence of i.i.d. uniform random points in $[0,1]^{2}$ . Let $O$ be a point in $\mathbb{R}^{2}$ . Let $k_{1},k_{2},\ldots$ be an infinite sequence of positive integers. Let $M\geq 10^{5}$ be a positive integer. For each positive integer $n$ , consider the unit-demand Euclidean CVRP with the set of terminals $V=\{v_{1},\ldots,v_{n}\}$ , the depot $O$ , and the capacity $k_{n}$ . Let $\mathrm{opt}$ denote the cost of an optimal solution, and $\mathrm{sol}(M)$ denote the cost of the solution returned by Algorithm 1 with parameter $M$ . Then we have

\limsup_{n\to\infty}\frac{\mathrm{sol}(M)}{\mathrm{opt}}<1.55

almost surely.

Proof.

Let $v$ denote a uniform random point in $[0,1]^{2}$ . Throughout this section, we always take $R:=\frac{3}{4}\;\mathbb{E}\left(d(O,v)\right)$ and $D$ to be the diameter of $[0,1]^{2}\cup\{O\}$ . Note that $R$ and $D$ are deterministic real numbers which do not depend on $n$ . Let $T_{0}^{*}$ and $T_{R}^{*}$ denote the $0$ -local and $R$ -local costs respectively. Let $\mathrm{rad}_{\infty}$ and $\mathrm{rad}_{R}$ denote the $\infty$ -radial and $R$ -radial costs respectively. By Theorem 5 and Theorem 6, we have

		$\displaystyle\limsup_{n\to\infty}\frac{\mathrm{sol}(M)}{\mathrm{opt}}$
	$\displaystyle\leq$	$\displaystyle\limsup_{n\to\infty}\frac{\left(1+\frac{1}{M}\right)\left(T_{0}^{}+\mathrm{rad}_{\infty}+\frac{3\pi D}{2}\left(\frac{n}{Mk_{n}}+1\right)\right)}{T^{}_{R}+\mathrm{rad}_{R}-\frac{3\pi D}{2}}$
	$\displaystyle\leq$	$\displaystyle\limsup_{n\to\infty}\max\left\{\frac{\left(1+\frac{1}{M}\right)\left(T_{0}^{}+\frac{3\pi D}{2}\right)}{T_{R}^{}-\frac{3\pi D}{2}},\frac{\left(1+\frac{1}{M}\right)\left(\mathrm{rad}_{\infty}+\frac{3\pi Dn}{2Mk_{n}}\right)}{\mathrm{rad}_{R}}\right\}$
	$\displaystyle=$	$\displaystyle\left(1+\frac{1}{M}\right)\max\left\{\limsup_{n\to\infty}\frac{T_{0}^{}+\frac{3\pi D}{2}}{T_{R}^{}-\frac{3\pi D}{2}},\limsup_{n\to\infty}\frac{\mathrm{rad}_{\infty}+\frac{3\pi Dn}{2Mk_{n}}}{\mathrm{rad}_{R}}\right\}$

almost surely.

The validity of Theorem 11 relies on the upper bounds on both of the limit superiors. We will prove Lemma 12 and Lemma 13 in Section 4.1 and Section 4.2 respectively.

Lemma 12.

We have

\limsup_{n\to\infty}\frac{T_{0}^{*}+\frac{3\pi D}{2}}{T_{R}^{*}-\frac{3\pi D}{2}}\leq\frac{48}{31}

almost surely.

Lemma 13.

We have

\limsup_{n\to\infty}\frac{\mathrm{rad}_{\infty}+\frac{3\pi Dn}{2Mk_{n}}}{\mathrm{rad}_{R}}\leq\frac{48}{31}\left(1+\frac{15\pi}{4M}\right)

almost surely.

Assuming Lemma 12 and Lemma 13, for any $M\geq 10^{5}$ , we have

		$\displaystyle\limsup_{n\to\infty}\frac{\mathrm{sol}(M)}{\mathrm{opt}}$
	$\displaystyle\leq$	$\displaystyle\left(1+\frac{1}{M}\right)\max\left\{\limsup_{n\to\infty}\frac{T_{0}^{}+\frac{3\pi D}{2}}{T_{R}^{}-\frac{3\pi D}{2}},\limsup_{n\to\infty}\frac{\mathrm{rad}_{\infty}+\frac{3\pi Dn}{2Mk_{n}}}{\mathrm{rad}_{R}}\right\}$
	$\displaystyle\leq$	$\displaystyle\frac{48}{31}\left(1+\frac{1}{M}\right)\left(1+\frac{15\pi}{4M}\right)$
	$\displaystyle<$	$\displaystyle 1.55$

almost surely. ∎

4.1 Proof of Lemma 12

Let $\lambda_{R}$ denote the measure of the set $\left\{x\in[0,1]^{2}:d(O,x)>R\right\}$ . Let $S_{R}(n)$ denote the size of set $\{1\leq i\leq n:d(O,v_{i})>R\}$ . By the strong law of large numbers, we have

\lim_{n\to\infty}\frac{S_{R}(n)}{n}=\lambda_{R}

almost surely. We will prove the following bound on $\lambda_{R}$ in Appendix A.

Lemma 14.

For $R=\frac{3}{4}\;\mathbb{E}\left(d(O,v)\right)$ , we have $\lambda_{R}\geq\frac{31}{48}$ .

By Lemma 14, $S_{R}(n)\to\infty$ as $n\to\infty$ . By applying the main result of [13] to the infinite sequence $v_{1},v_{2},\ldots$ and its intersection with the set $\left\{x\in[0,1]^{2}:d(O,x)>R\right\}$ , we have

\lim_{n\to\infty}\frac{T_{0}^{*}}{\sqrt{n}}=\lim_{n\to\infty}\frac{T^{*}_{R}}{\sqrt{\lambda_{R}S_{R}(n)}}>0

almost surely. Thus

		$\displaystyle\lim_{n\to\infty}\frac{T_{0}^{}+\frac{3\pi D}{2}}{T_{R}^{}-\frac{3\pi D}{2}}$
	$\displaystyle=$	$\displaystyle\lim_{n\to\infty}\frac{\frac{T_{0}^{}}{\sqrt{n}}+\frac{3\pi D}{2\sqrt{n}}}{\lambda_{R}\sqrt{\frac{S_{R}(n)}{\lambda_{R}\,n}}\frac{T_{R}^{}}{\sqrt{\lambda_{R}S_{R}(n)}}-\frac{3\pi D}{2\sqrt{n}}}$
	$\displaystyle=$	$\displaystyle\frac{1}{\lambda_{R}}$

almost surely. By Lemma 14, the claim follows.

4.2 Proof of Lemma 13

By the strong law of large numbers, we have

\lim_{n\to\infty}\frac{k_{n}\;\mathrm{rad}_{\infty}}{2n}=\mathbb{E}\left(d(O,v)\right)

and

\lim_{n\to\infty}\frac{k_{n}\;\mathrm{rad}_{R}}{2n}=\mathbb{E}\left(\min\left\{d(O,v),R\right\}\right)

almost surely. Thus

		$\displaystyle\lim_{n\to\infty}\frac{\mathrm{rad}_{\infty}+\frac{3\pi Dn}{2Mk_{n}}}{\mathrm{rad}_{R}}$
	$\displaystyle=$	$\displaystyle\lim_{n\to\infty}\frac{\frac{k_{n}\;\mathrm{rad}_{\infty}}{2n}+\frac{3\pi D}{4M}}{\frac{k_{n}\;\mathrm{rad}_{R}}{2n}}$
	$\displaystyle=$	$\displaystyle\frac{\mathbb{E}\left(d(O,v)\right)+\frac{3\pi D}{4M}}{\mathbb{E}\left(\min\left\{d(O,v),R\right\}\right)}$

almost surely. We need the following inequality whose proof is in Appendix A.

Lemma 15.

For $R=\frac{3}{4}\;\mathbb{E}\left(d(O,v)\right)$ , we have

\mathbb{E}\left(\min\left\{d(O,v),R\right\}\right)\geq\frac{31}{48}\;\mathbb{E}\left(d(O,v)\right).

From Lemma 15, we obtain

\lim_{n\to\infty}\frac{\mathrm{rad}_{\infty}+\frac{3\pi Dn}{2Mk_{n}}}{\mathrm{rad}_{R}}\leq\frac{48\left(\mathbb{E}\left(d(O,v)\right)+\frac{3\pi D}{4M}\right)}{31\;\mathbb{E}\left(d(O,v)\right)}

(7)

almost surely.

Lemma 16.

We have

D\leq 5\;\mathbb{E}\left(d(O,v)\right).

Proof.

Let $O_{c}=\left(\frac{1}{2},\frac{1}{2}\right)\in\mathbb{R}^{2}$ denote the center of the square $[0,1]^{2}$ . Let $\overline{v}$ denote the reflection of $v$ across the point $O_{c}$ . Then we have

\frac{d(O,v)+d(O,\overline{v})}{2}\geq\frac{d(v,\overline{v})}{2}=d(O_{c},v).

Because $v$ and $\overline{v}$ have the same distribution, we have

\mathbb{E}\left(d(O,v)\right)\geq\mathbb{E}\left(d(O_{c},v)\right).

We use a closed-form formula of $\mathbb{E}\left(d(O_{c},v)\right)$ established in Section A.3 (Theorem 22) to obtain

\mathbb{E}\left(d(O_{c},v)\right)=\frac{\sqrt{2}+\log\left(1+\sqrt{2}\right)}{6}\geq\frac{\sqrt{2}}{4}.

Therefore, by the definition of $D$ , we have

D\leq\sqrt{2}+\mathbb{E}\left\{d(O,v)\right\}\leq 4\;\mathbb{E}\left(d(O_{c},v)\right)+\mathbb{E}\left\{d(O,v)\right\}\leq 5\;\mathbb{E}\left(d(O,v)\right).

∎

By Eq. 7 and Lemma 16, we proved Lemma 13.

Appendix A Proofs of Lemma 14 and Lemma 15

In this section, we prove two inequalities involving $\mathbb{E}\left(d(O,v)\right)$ , $\mathbb{E}\left(\min\{d(O,v),R\}\right)$ , and $\lambda_{R}$ . Here $v$ is a uniform random point in $[0,1]^{2}$ , $R$ is $\frac{3}{4}\;\mathbb{E}\left(d(O,v)\right)$ , and $\lambda_{R}$ is the measure of the set $\{x\in[0,1]^{2}:d(O,x)>R\}$ . For convenience, we rewrite these terms as explicit functions of $O$ , that is, we let

	$\displaystyle g_{1}(O)$	$\displaystyle:=\mathbb{E}\left(d(O,v)\right),$
	$\displaystyle g_{2}(O)$	$\displaystyle:=\mathbb{E}\left(\min\{d(O,v),R\}\right),$
	$\displaystyle g_{3}(O)$	$\displaystyle:=\lambda_{R}.$

The proofs of Lemma 14 and Lemma 15 consist of several steps. In Section A.1, we establish the Lipschitz conditions for $g_{1}$ , $g_{2}$ , and $g_{3}$ . In Section A.2, first, we prove the claims when $O$ is located far away from the unit square; next, we build a fixed-sized $\varepsilon$ -net $N$ of a bounded region, and use validated numerics to establish rigorous inequalities for all points in $N$ ; and finally, we prove the claims in Lemma 14 and Lemma 15 for any point $O$ in $\mathbb{R}^{2}$ . In Section A.3, we prove the closed-form formulas that are used in Section A.2.

A.1 Lipschitz Continuity of $g_{1}$ , $g_{2}$ , and $g_{3}$

In this subsection, we compute the Lipschitz constants of the functions $g_{1}$ , $g_{2}$ , and $g_{3}$ .

Lemma 17.

For any $O,O^{\prime}\in\mathbb{R}^{2}$ , we have

\left|g_{1}(O)-g_{1}(O^{\prime})\right|\leq d(O,O^{\prime}).

Proof.

We have

		$\displaystyle\left\|g_{1}(O)-g_{1}(O^{\prime})\right\|$
	$\displaystyle=$	$\displaystyle\left\|\mathbb{E}\left(d(O,v)-d(O^{\prime},v)\right)\right\|$
	$\displaystyle\leq$	$\displaystyle\mathbb{E}\left(\left\|d(O,v)-d(O^{\prime},v)\right\|\right)$
	$\displaystyle\leq$	$\displaystyle\mathbb{E}\left(d(O,O^{\prime})\right)$
	$\displaystyle=$	$\displaystyle d(O,O^{\prime}).$

∎

Lemma 18.

For any $O,O^{\prime}\in\mathbb{R}^{2}$ , we have

\left|g_{2}(O)-g_{2}(O^{\prime})\right|\leq d(O,O^{\prime}).

Proof.

By Lemma 17, we have

		$\displaystyle\left\|g_{2}(O)-g_{2}(O^{\prime})\right\|$
	$\displaystyle=$	$\displaystyle\left\|\mathbb{E}\left(\min\left\{d(O,v),\frac{3}{4}g_{1}(O)\right\}-\min\left\{d(O^{\prime},v),\frac{3}{4}g_{1}(O^{\prime})\right\}\right)\right\|$
	$\displaystyle\leq$	$\displaystyle\mathbb{E}\left(\left\|\min\left\{d(O,v),\frac{3}{4}g_{1}(O)\right\}-\min\left\{d(O^{\prime},v),\frac{3}{4}g_{1}(O^{\prime})\right\}\right\|\right)$
	$\displaystyle\leq$	$\displaystyle\mathbb{E}\left(\max\left\{\left\|d(O,v)-d(O^{\prime},v)\right\|,\frac{3}{4}\left\|g_{1}(O)-g_{1}(O^{\prime})\right\|\right\}\right)$
	$\displaystyle\leq$	$\displaystyle\mathbb{E}\left(\max\left\{d(O,O^{\prime}),\frac{3}{4}d(O,O^{\prime})\right\}\right)$
	$\displaystyle=$	$\displaystyle d(O,O^{\prime}).$

∎

Lemma 19.

For any $O,O^{\prime}\in\mathbb{R}^{2}$ , we have

\left|g_{3}(O)-g_{3}(O^{\prime})\right|\leq(3+\sqrt{2})\;d(O,O^{\prime}).

Proof.

For each $O\in\mathbb{R}$ and each $r\in\mathbb{R}^{+}$ , let $C(O,r)$ denote the circle $\{x\in\mathbb{R}^{2}:d(O,x)=r\}$ . Furthermore, let $B(O,r)$ denote the intersection of $[0,1]^{2}$ and the interior of $C(O,r)$ , and $\gamma(O,r)$ denote the intersection of $[0,1]^{2}$ and $C(O,r)$ .

Sincec $B(O,r)$ is a convex subset of the unit square $[0,1]^{2}$ , by an axiom⁶⁶6The axiom can be equivalently stated as follows: given two nested convex closed curves, the inner one is shorter. Archimedes applied this axiom to show that [8, 52] the ratio of a circle’s circumference to its diameter is a constant, namely Archimedes’ constant $\pi$ . He then obtained [8] the first rigorous approximation of $\pi$ . Nowadays, there are many modern proofs of this axiom. of Archimedes [7], the length of the boundary of $B(O,r)$ is at most $4$ . Because $\gamma(O,r)$ is part of the boundary of $B(O,r)$ , the length $\left\lVert\gamma(O,r)\right\lVert$ is at most $4$ . Since $\left\lVert\gamma(O,r)\right\lVert$ is the derivative of the measure of $B(O,r)$ with respect to $r$ , the difference between the measures of $B(O,r)$ and $B(O,r^{\prime})$ is at most $4|r-r^{\prime}|$ .

For each $O\in\mathbb{R}$ and each $r\in\mathbb{R}^{+}$ , let $\gamma_{i}(O,r)$ ( $i=1,2,3,4$ ) denote the intersection of an edge of $[0,1]^{2}$ (left, right, bottom, top) and $C(O,r)$ . Then the derivative of the measure of $B(O,r)$ with respect to $x$ -coordinate (resp. $y$ -coordinate) of $O$ is $\left\lVert\gamma_{1}\right\lVert-\left\lVert\gamma_{2}\right\lVert$ (resp. $\left\lVert\gamma_{3}\right\lVert-\left\lVert\gamma_{3}\right\lVert$ ). As a result, the difference between the measures of $B(O,r)$ and $B(O^{\prime},r)$ is at most $\sqrt{2}\;d(O,O^{\prime})$ .

By definition, the measure of $B\left(O,\frac{3}{4}g_{1}(O)\right)$ is $1-g_{3}(O)$ , and the measure of $B\left(O^{\prime},\frac{3}{4}g_{1}(O^{\prime})\right)$ is $1-g_{3}(O^{\prime})$ . Therefore, by Lemma 17, we have

		$\displaystyle\left\|g_{3}(O)-g_{3}(O^{\prime})\right\|$
	$\displaystyle\leq$	$\displaystyle\sqrt{2}\;d(O,O^{\prime})+3\left\|g_{1}(O)-g_{1}(O^{\prime})\right\|$
	$\displaystyle\leq$	$\displaystyle(3+\sqrt{2})\;d(O,O^{\prime}).$

∎

A.2 Proofs Using the $\varepsilon$ -Net

In this subsection, we prove Lemma 14 and Lemma 15. It suffices to show

g_{2}(O)\geq\frac{31}{48}g_{1}(O)

(8)

and

g_{3}(O)\geq\frac{31}{48}

(9)

for every $O\in\mathbb{R}^{2}$ .

Let $d(O,[0,1]^{2})$ denote the distance between $O$ and $[0,1]^{2}$ . Then we have

g_{1}(O)=\mathbb{E}\left(d(O,v)\right)\leq d(O,[0,1]^{2})+\sqrt{2}.

If $d(O,[0,1]^{2})$ is at least $3\sqrt{2}$ , then we have

R=\frac{3}{4}g_{1}(O)\leq\frac{3}{4}\left(d(O,[0,1]^{2})+\sqrt{2}\right)\leq d(O,[0,1]^{2}).

Thus by definition, we have $g_{2}(O)=\frac{3}{4}g_{1}(O)$ and $g_{3}(O)=1$ . Therefore, both Eq. 8 and Eq. 9 hold.

It remains to consider the case when $d(O,[0,1]^{2})$ is less than $3\sqrt{2}$ . Without loss of generality, we also assume that $O$ is located to the right of the vertical line $x=\frac{1}{2}$ and above the diagonal line $y=x$ .

Let $N$ denote the point set

N:=\left\{(a,b)\in\mathbb{R}^{2}:\left(\frac{a-0.5}{0.002},\frac{b-0.5}{0.002}\right)\in\{0,1,\ldots,2371\}^{2},a\leq b\right\}.

For each $O^{\prime}\in N$ , we have verified

g_{2}(O^{\prime})-\frac{31}{48}g_{1}(O^{\prime})\geq 0.0025

and

g_{3}(O^{\prime})-\frac{31}{48}\geq 0.0096.

This is done using a rigorous computer-assisted proof.⁷⁷7Lengthy discussions on rigorous computer-assisted proofs can be found in many works in the literature, see, e.g., Zwick’s discussion on the role of computer-assisted proofs in mathematics and computer science [59], the computer-assisted proofs for the four color theorem [5, 6] and Kepler’s conjecture [34]. For each $O^{\prime}\in N$ , we compute the values of $g_{1}(O^{\prime}),g_{2}(O^{\prime}),g_{3}(O^{\prime})$ using the closed-form formulas derived in Theorem 22 and Theorem 29; see Section A.3. Our computation⁸⁸8Our verification code is available at https://github.com/Zipei-Nie/CVRP-proofs. We use the kv library [38] for interval arithmetic. carefully accounts for all the rounding errors using interval arithmetic [35].

Consider a point $O$ in the set

\left\{(a,b)\in\mathbb{R}^{2}:d((a,b),[0,1]^{2})<3\sqrt{2},\frac{1}{2}\leq a\leq b\right\}.

By the construction of $N$ , there exists $O^{\prime}\in N$ such that $d(O,O^{\prime})\leq\frac{\sqrt{2}}{1000}$ . By Lemma 17 and Lemma 18, we have

		$\displaystyle g_{2}(O)-\frac{31}{48}g_{1}(O)$
	$\displaystyle=$	$\displaystyle g_{2}(O^{\prime})-\frac{31}{48}g_{1}(O^{\prime})+(g_{2}(O)-g_{2}(O^{\prime}))-\frac{31}{48}(g_{1}(O)-g_{1}(O^{\prime}))$
	$\displaystyle\geq$	$\displaystyle 0.0025-\frac{79}{48}d(O,O^{\prime})$
	$\displaystyle\geq$	$\displaystyle 0.0025-\frac{79\sqrt{2}}{48000}$
	$\displaystyle\geq$	$\displaystyle 0.$

By Lemma 19, we have

		$\displaystyle g_{3}(O)-\frac{31}{48}$
	$\displaystyle=$	$\displaystyle g_{3}(O^{\prime})-\frac{31}{48}+(g_{3}(O)-g_{3}(O^{\prime}))$
	$\displaystyle\geq$	$\displaystyle 0.0096-(3+\sqrt{2})d(O,O^{\prime})$
	$\displaystyle\geq$	$\displaystyle 0.0096-\frac{(3+\sqrt{2})\sqrt{2}}{1000}$
	$\displaystyle\geq$	$\displaystyle 0.$

Thus Eq. 8 and Eq. 9 hold.

We completed the proofs of Lemma 14 and Lemma 15.

A.3 Closed-Form Formulas for $g_{1}$ , $g_{2}$ , and $g_{3}$

In this subsection, we will derive closed-form formulas for the functions $g_{1}$ , $g_{2}$ , and $g_{3}$ .

First, we compute the integrations of $1$ and $\sqrt{x^{2}+y^{2}}$ over a right triangle.

Definition 20.

Define the functions $A_{0},A_{1}:\mathbb{R}^{2}\to\mathbb{R}$ by

A_{0}(a,b):=\begin{cases}\int_{0}^{a}\int_{0}^{\frac{bx}{a}}\,dy\,dx&\mbox{, if }a\neq 0,\\ 0&\mbox{, if }a=0\end{cases}

and

A_{1}(a,b):=\begin{cases}\int_{0}^{a}\int_{0}^{\frac{bx}{a}}\sqrt{x^{2}+y^{2}}\,dy\,dx&\mbox{, if }a\neq 0,\\ 0&\mbox{, if }a=0\end{cases}

for every $a,b\in\mathbb{R}$ .

Clearly, we have

A_{0}(a,b)=\frac{ab}{2}.

To obtain a closed-form formula for $A_{1}(a,b)$ , we can use the result derived by Stone [54]. See [44] for an alternative proof.

Lemma 21.

[54] For every $a,b\in\mathbb{R}$ with $a\neq 0$ , we have

A_{1}(a,b)=\begin{cases}\frac{a^{3}}{6}\log(\frac{b}{|a|}+\sqrt{1+\frac{b^{2}}{a^{2}}})+\frac{ab}{6}\sqrt{a^{2}+b^{2}}&\mbox{, if }a\neq 0,\\ 0&\mbox{, if }a=0.\end{cases}

Then we have the following closed-form formula for $g_{1}$ . See [54] for an alternative formulation of the result.

Theorem 22.

For any $O=(a,b)\in\mathbb{R}^{2}$ , we have

	$\displaystyle g_{1}(O)=$	$\displaystyle A_{1}(a,b)+A_{1}(b,a)+A_{1}(b,1-a)+A_{1}(1-a,b)$
		$\displaystyle+A_{1}(1-a,1-b)+A_{1}(1-b,1-a)+A_{1}(1-b,a)+A_{1}(a,1-b).$

Proof.

Divide the square $[0,1]^{2}$ into eight right triangles. Each triangle has one vertex at $O$ and one vertex at a corner of the square, and has one edge parallel to the $x$ -axis and one edge parallel to the $y$ -axis.

By the definition of $g_{1}(O)$ , we have

g_{1}(O)=\int_{0}^{1}\int_{0}^{1}\sqrt{(x-a)^{2}+(y-b)^{2}}\,dx\,dy.

We can break down this integration into eight separate ones, one for each of the right triangles formed by dividing the square. Since each integration has the form $A_{1}(\cdot,\cdot)$ , the closed-form formula for $g_{1}$ follows from Lemma 21. ∎

Then, we derive closed-form formulas for the integrations of $1$ and $\sqrt{x^{2}+y^{2}}$ over a disk segment.

Definition 23.

For each $h\in\mathbb{R}$ , let $S_{h}$ denote the disk segment

S_{h}:=\{(x,y)\in\mathbb{R}^{2}:x\leq h,x^{2}+y^{2}\leq 1\}.

We define the functions $B_{0},B_{1}:\mathbb{R}\to\mathbb{R}$ by

B_{0}(h):=\iint_{S_{h}}dx\,dy

and

B_{1}(h):=\iint_{S_{h}}\sqrt{x^{2}+y^{2}}\,dx\,dy

for every $h\in\mathbb{R}$ .

Lemma 24.

For each $i=0,1$ and each $h\in\mathbb{R}$ , we have

B_{i}(h)=\begin{cases}0&\mbox{, if }h<-1,\\ \frac{3-i}{3}\left(\pi-\arccos h\right)+2A_{i}\left(h,\sqrt{1-h^{2}}\right)&\mbox{, if }-1\leq h<1,\\ \frac{3-i}{3}\pi&\mbox{, if }h\geq 1.\end{cases}

Proof.

For $h<-1$ , the region $S_{h}$ is empty, so $B_{0}(h)=B_{1}(h)=0$ . For $h\geq-1$ , the region $S_{h}$ is the unit disk, so $B_{0}(h)=\pi$ and $B_{1}(h)=\frac{2\pi}{3}$ .

Suppose that $-1\leq h<1$ . Divide $S_{h}$ into a disk sector and two right triangles. Each triangle has one vertex at the origin and one vertex at an intersection point of the unit circle and the line $x=h$ , and has one edge on the $x$ -axis and one edge on the line $x=h$ .

We can break down the integrations over $S_{h}$ into three separate ones, one for the disk sector and one for each right triangle. The disk sector has central angle $2(\pi-\arccos h)$ and radius $1$ , so the area is $\pi-\arccos h$ . The average distance from a uniform random point on the disk sector to the center is $\frac{2}{3}$ times the radius, so the integration of $\sqrt{x^{2}+y^{2}}$ over the disk sector is $\frac{2}{3}(\pi-\arccos h)$ . The integrations over the right triangles have the form $A_{i}(\cdot,\cdot)$ ( $i=0,1$ ), so we can use Lemma 21 to derive the closed-form formulas for $B_{0}$ and $B_{1}$ . ∎

Next, we derive closed-form formulas for the integrations of $1$ and $\sqrt{x^{2}+y^{2}}$ over a region formed by the intersection of a disk and two half-planes.

Definition 25.

For each $h_{1},h_{2}\in\mathbb{R}$ , let $S_{h_{1},h_{2}}$ denote the region

S_{h_{1},h_{2}}:=\{(x,y)\in\mathbb{R}^{2}:x\leq h_{1},y\leq h_{2},x^{2}+y^{2}\leq 1\}.

We define the functions $C_{0},C_{1}:\mathbb{R}^{2}\to\mathbb{R}$ by

C_{0}(h_{1},h_{2}):=\iint_{S_{h_{1},h_{2}}}dx\,dy

and

C_{1}(h_{1},h_{2}):=\iint_{S_{h_{1},h_{2}}}\sqrt{x^{2}+y^{2}}\,dx\,dy

for every $h_{1},h_{2}\in\mathbb{R}$ .

Lemma 26.

For each $i=0,1$ and each $h_{1},h_{2}\in\mathbb{R}$ , we have

C_{i}(h_{1},h_{2})=\begin{cases}0&\mbox{, if }h_{1}^{2}+h_{2}^{2}>1,h_{1}\leq 0,h_{2}\leq 0,\\ B_{i}(h_{2})&\mbox{, if }h_{1}^{2}+h_{2}^{2}>1,h_{1}>0,h_{2}\leq 0,\\ B_{i}(h_{1})&\mbox{, if }h_{1}^{2}+h_{2}^{2}>1,h_{1}\leq 0,h_{2}>0,\\ B_{i}(h_{1})+B_{i}(h_{2})-\frac{3-i}{3}\pi&\mbox{, if }h_{1}^{2}+h_{2}^{2}>1,h_{1}>0,h_{2}>0,\\ {\frac{3-i}{6}\left(\frac{\pi}{2}+\arcsin h_{1}+\arcsin h_{2}\right)+A_{i}\left(h_{1},\sqrt{1-h_{1}^{2}}\right)}\\ {+A_{i}\left(h_{2},\sqrt{1-h_{2}^{2}}\right)+A_{i}(h_{1},h_{2})+A_{i}(h_{2},h_{1})}&\mbox{, if }h_{1}^{2}+h_{2}^{2}\leq 1.\\ \end{cases}

Proof.

The proof is very similar to those of Theorem 22 and Lemma 24.

For $h_{1}^{2}+h_{2}^{2}>1,h_{1}\leq 0,h_{2}\leq 0$ , the region $S_{h_{1},h_{2}}$ is empty. For $h_{1}^{2}+h_{2}^{2}>1,h_{1}>0,h_{2}\leq 0$ , the region $S_{h_{1},h_{2}}$ is a disk segment. The situation is symmetric when $h_{1}^{2}+h_{2}^{2}>1,h_{1}\leq 0,h_{2}>0$ .

For $h_{1}^{2}+h_{2}^{2}>1,h_{1}>0,h_{2}>0$ , we divide the region $S_{h_{1},h_{2}}$ into two disk segments and a negative disk. For $h_{1}^{2}+h_{2}^{2}\leq 1$ , we divide the region $S_{h_{1},h_{2}}$ into a disk sector and four right triangles.

In any case, we can use Lemma 21 and Lemma 24 to derive the closed-form formulas for $C_{0}$ and $C_{1}$ . ∎

Then, we obtain closed-form formulas for integrations directly related to the definitions of $g_{2}$ and $g_{3}$ .

Definition 27.

Define the functions $D_{0},D_{1}:\mathbb{R}^{2}\times\mathbb{R}^{+}\to\mathbb{R}$ by

D_{0}(a,b,R)=\frac{1}{R^{2}}\int_{0}^{1}\int_{0}^{1}\mathds{1}\left(d(O,v)\leq R\right)\,dx\,dy

and

D_{1}(a,b,R)=\frac{1}{R^{3}}\int_{0}^{1}\int_{0}^{1}d(O,v)\mathds{1}\left(d(O,v)\leq R\right)\,dx\,dy

for every $a,b\in\mathbb{R}$ and $R\in\mathbb{R}^{+}$ .

Lemma 28.

For each $i=0,1$ , each $a,b\in\mathbb{R}$ , and each $R\in\mathbb{R}^{+}$ , we have

D_{i}(a,b,R)=C_{i}\left(\frac{1-a}{R},\frac{1-b}{R}\right)-C_{i}\left(\frac{1-a}{R},\frac{-b}{R}\right)-C_{i}\left(\frac{-a}{R},\frac{1-b}{R}\right)+C_{i}\left(\frac{-a}{R},\frac{-b}{R}\right).

Proof.

We divide the unit square $[0,1]^{2}$ into two positive regions, $(-\infty,0)\times(-\infty,0)$ and $(-\infty,1]\times(-\infty,1]$ , and two negative regions, $(-\infty,1]\times(-\infty,0)$ and $(-\infty,0)\times(-\infty,1]$ . Over the positive regions, the integrations are $C_{i}\left(\frac{1-a}{R},\frac{1-b}{R}\right)$ and $+C_{i}\left(\frac{-a}{R},\frac{-b}{R}\right)$ respectively. Over the negative regions, the integrations are $-C_{i}\left(\frac{1-a}{R},\frac{-b}{R}\right)$ and $-C_{i}\left(\frac{-a}{R},\frac{1-b}{R}\right)$ respectively. We can use Lemma 26 to derive the closed-form formulas for $D_{0}$ and $D_{1}$ . ∎

Finally, we establish the closed-form formulas for $g_{2}$ and $g_{3}$ .

Theorem 29.

For any $O=(a,b)\in\mathbb{R}^{2}$ , we have

g_{2}(O)=R-R^{3}D_{0}(a,b,R)+R^{3}D_{1}(a,b,R)

and

g_{3}(O)=1-R^{2}D_{0}(a,b,R),

where

R=\frac{3}{4}g_{1}(O).

Proof.

By definition, we have

g_{2}(O)=\int_{0}^{1}\int_{0}^{1}\min\left\{d(O,v),R\right\}\,dx\,dy

and

g_{3}(O)=\int_{0}^{1}\int_{0}^{1}\mathds{1}\left(d(O,v)>R\right)\,dx\,dy.

The closed-form formulas for $g_{2}(O)$ and $g_{3}(O)$ follows from Theorem 22, Lemma 28, and the equations

\min\left\{d(O,v),R\right\}=R\;\mathds{1}\left(d(O,v)>R\right)+d(O,v)\mathds{1}\left(d(O,v)\leq R\right)

and

\mathds{1}\left(d(O,v)>R\right)=1-\mathds{1}\left(d(O,v)\leq R\right).

∎

Acknowledgments

We thank Claire Mathieu for helpful preliminary discussions.

References

[1] A. Adamaszek, A. Czumaj, and A. Lingas. PTAS for $k$ -tour cover problem on the plane for moderately large values of $k$ . International Journal of Foundations of Computer Science, 21(06):893–904, 2010.
[2] K. Altinkemer and B. Gavish. Heuristics for unequal weight delivery problems with a fixed error guarantee. Operations Research Letters, 6(4):149–158, 1987.
[3] K. Altinkemer and B. Gavish. Heuristics for delivery problems with constant error guarantees. Transportation Science, 24(4):294–297, 1990.
[4] S. P. Anbuudayasankar, K. Ganesh, and S. Mohapatra. Models for practical routing problems in logistics. Springer, 2016.
[5] K. Appel and W. Haken. Every planar map is four colorable. Part I: Discharging. Illinois Journal of Mathematics, 21(3):429 – 490, 1977.
[6] K. Appel, W. Haken, and J. Koch. Every planar map is four colorable. Part II: Reducibility. Illinois Journal of Mathematics, 21(3):491–567, 1977.
[7] Archimedes. On the sphere and cylinder, Book I. c. 225 BCE.
[8] Archimedes. Measurement of a Circle. c. 250 BCE.
[9] S. Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM (JACM), 45(5):753–782, 1998.
[10] S. Arora. Approximation schemes for NP-hard geometric optimization problems: A survey. Mathematical Programming, 97(1):43–69, 2003.
[11] T. Asano, N. Katoh, and K. Kawashima. A new approximation algorithm for the capacitated vehicle routing problem on a tree. Journal of Combinatorial Optimization, 5(2):213–231, 2001.
[12] T. Asano, N. Katoh, H. Tamaki, and T. Tokuyama. Covering points in the plane by $k$ -tours: towards a polynomial time approximation scheme for general $k$ . In ACM Symposium on Theory of Computing (STOC), pages 275–283, 1997.
[13] J. Beardwood, J. H. Halton, and J. M. Hammersley. The shortest path through many points. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 55, pages 299–327. Cambridge University Press, 1959.
[14] A. 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.
[15] A. Becker, P. N. Klein, and D. Saulpic. A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs. In 25th Annual European Symposium on Algorithms (ESA), 2017.
[16] A. Becker, P. N. Klein, and D. Saulpic. Polynomial-time approximation schemes for $k$ -center, $k$ -median, and capacitated vehicle routing in bounded highway dimension. In 26th Annual European Symposium on Algorithms (ESA), 2018.
[17] A. Becker, P. N. Klein, and A. Schild. A PTAS for bounded-capacity vehicle routing in planar graphs. In Workshop on Algorithms and Data Structures, pages 99–111. Springer, 2019.
[18] A. Becker and A. Paul. A framework for vehicle routing approximation schemes in trees. In Workshop on Algorithms and Data Structures, pages 112–125. Springer, 2019.
[19] J. Blauth, V. Traub, and J. Vygen. Improving the approximation ratio for capacitated vehicle routing. Mathematical Programming, 197(2):451–497, 2023.
[20] A. Bompadre, M. Dror, and J. B. Orlin. Improved bounds for vehicle routing solutions. Discrete Optimization, 3(4):299–316, 2006.
[21] A. Bompadre, M. Dror, and J. B. Orlin. Probabilistic analysis of unit-demand vehicle routeing problems. Journal of applied probability, 44(1):259–278, 2007.
[22] V. Cohen-Addad, A. Filtser, P. N. Klein, and H. Le. On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs. In Symposium on Foundations of Computer Science (FOCS), pages 589–600. IEEE, 2020.
[23] J.-F. Cordeau, G. Laporte, M. W. Savelsbergh, and D. Vigo. Vehicle routing. Handbooks in operations research and management science, 14:367–428, 2007.
[24] T. G. Crainic and G. Laporte. Fleet management and logistics. Springer Science & Business Media, 2012.
[25] C. F. Daganzo. The distance traveled to visit n points with a maximum of c stops per vehicle: An analytic model and an application. Transportation science, 18(4):331–350, 1984.
[26] A. Das and C. Mathieu. A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing. Algorithmica, 73(1):115–142, 2015.
[27] M. Dufay, C. Mathieu, and H. Zhou. An approximation algorithm for distance-constrained vehicle routing on trees. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), volume 254, pages 27:1–27:16, 2023.
[28] Z. Friggstad, R. Mousavi, M. Rahgoshay, and M. 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.
[29] Z. Friggstad and C. Swamy. Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing. In Proceedings of the forty-sixth annual ACM Symposium on Theory of Computing (STOC), pages 744–753, 2014.
[30] B. E. Gillett and L. R. Miller. A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 22(2):340–349, 1974.
[31] B. Golden, S. Raghavan, and E. Wasil. The vehicle routing problem: latest advances and new challenges, volume 43 of Operations Research/Computer Science Interfaces Series. Springer, 2008.
[32] F. Grandoni, C. Mathieu, and H. Zhou. Unsplittable Euclidean capacitated vehicle routing: A $(2+\varepsilon)$ -approximation algorithm. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251, pages 63:1–63:13, 2023.
[33] M. Haimovich and A. H. G. Rinnooy Kan. Bounds and heuristics for capacitated routing problems. Mathematics of operations Research, 10(4):527–542, 1985.
[34] T. C. Hales. A proof of the Kepler conjecture. Annals of mathematics, pages 1065–1185, 2005.
[35] E. Hansen and G. W. Walster. Global optimization using interval analysis: revised and expanded, volume 264. CRC Press, 2003.
[36] A. Jayaprakash and M. R. Salavatipour. Approximation schemes for capacitated vehicle routing on graphs of bounded treewidth, bounded doubling, or highway dimension. ACM Trans. Algorithms, 19(2), 2023.
[37] R. M. Karp. Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane. Mathematics of operations research, 2(3):209–224, 1977.
[38] M. Kashiwagi. kv – a C++ Library for Verified Numerical Computation. http://verifiedby.me/kv/index-e.html. Accessed April 2023.
[39] M. Khachay and R. Dubinin. PTAS for the Euclidean capacitated vehicle routing problem in $\mathbb{R}^{d}$ . In International Conference on Discrete Optimization and Operations Research, pages 193–205. Springer, 2016.
[40] G. Laporte. The vehicle routing problem: An overview of exact and approximate algorithms. European journal of operational research, 59(3):345–358, 1992.
[41] G. Laporte, M. Gendreau, J.-Y. Potvin, and F. Semet. Classical and modern heuristics for the vehicle routing problem. International transactions in operational research, 7(4-5):285–300, 2000.
[42] C. L. Li and D. Simchi-Levi. Worst-case analysis of heuristics for multidepot capacitated vehicle routing problems. ORSA Journal on Computing, 2(1):64–73, 1990.
[43] C.-L. Li, D. Simchi-Levi, and M. Desrochers. On the distance constrained vehicle routing problem. Operations Research, 40(4):790–799, 1992.
[44] H. Li and X. Qiu. Moments of distance from a vertex to a uniformly distributed random point within arbitrary triangles. Mathematical Problems in Engineering, 2016, 2016.
[45] C. Mathieu and H. Zhou. Iterated tour partitioning for Euclidean capacitated vehicle routing. Random Structures & Algorithms, pages 1–20, 2022. doi:10.1002/rsa.21130.
[46] C. Mathieu and H. Zhou. A PTAS for capacitated vehicle routing on trees. ACM Transactions on Algorithms (TALG), 19(2), 2023.
[47] C. Mathieu and H. Zhou. A tight $(1.5+\varepsilon)$ -approximation for unsplittable capacitated vehicle routing on trees. 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), 2023.
[48] T. Mömke and H. Zhou. Capacitated vehicle routing in graphic metrics. In Symposium on Simplicity in Algorithms (SOSA), pages 114–123. SIAM, 2023.
[49] V. Nagarajan and R. Ravi. Approximation algorithms for distance constrained vehicle routing problems. Networks, 59(2):209–214, 2012.
[50] Private communication with Fabien Viger at Google, 2022.
[51] W. T. Rhee. Probabilistic analysis of a capacitated vehicle routing problem II. The Annals of Applied Probability, 4(3):741–764, 1994.
[52] D. Richeson. Circular reasoning: who first proved that C divided by d is a constant? The College Mathematics Journal, 46(3):162–171, 2015.
[53] R. Schneider. Convex bodies: the Brunn–Minkowski theory. Number 151. Cambridge university press, 2014.
[54] R. E. Stone. Some average distance results. Transportation Science, 25(1):83–90, 1991.
[55] O. Szasz and A. Rosenthal. Eine extremaleigenschaft der kurven konstanter breite. Jahresbericht der Deutschen Mathematiker-Vereinigung, 25:278–282, 1917.
[56] P. Toth and D. Vigo. The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, 2002.
[57] A. Wren. Computers in Transport Planning and Operation. Allan, 1971.
[58] A. Wren and A. Holliday. Computer scheduling of vehicles from one or more depots to a number of delivery points. Journal of the Operational Research Society, 23(3):333–344, 1972.
[59] U. Zwick. Computer assisted proof of optimal approximability results. In SODA, pages 496–505, 2002.

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

Abstract

1 Introduction

Theoretical and Practical Perspectives.

1.1 Our Results

Algorithm.

Theorem 1.

Conjecture 2.

1.2 Overview of Techniques

Definition 3 (RR-radial cost).

Definition 4 (RR-local cost).

Theorem 5.

Theorem 6.

Remark.

1.3 Related Work

Sweep Heuristic.

Euclidean CVRP.

Probabilistic Analyses.

CVRP in Other Metrics.

CVRP with Arbitrary Demands.

1.4 Notations and Preliminaries

Arora’s Framework.

Lemma 7 (adaptation of [9]).

Proof.

2 Proof of Theorem 5

Lemma 8.

Proof.

Lemma 9.

Proof.

Remark.

3 Proof of Theorem 6

Lemma 10.

Proof.

4 Proof of Theorem 1

Theorem 11.

Proof.

Lemma 12.

Lemma 13.

4.1 Proof of Lemma 12

Lemma 14.

4.2 Proof of Lemma 13

Lemma 15.

Lemma 16.

Proof.

Appendix A Proofs of Lemma 14 and Lemma 15

A.1 Lipschitz Continuity of g1g_{1}, g2g_{2}, and g3g_{3}

Lemma 17.

Proof.

Lemma 18.

Proof.

Lemma 19.

Proof.

A.2 Proofs Using the ε\varepsilon-Net

A.3 Closed-Form Formulas for g1g_{1}, g2g_{2}, and g3g_{3}

Definition 20.

Lemma 21.

Theorem 22.

Proof.

Definition 23.

Lemma 24.

Proof.

Definition 25.

Lemma 26.

Proof.

Definition 27.

Lemma 28.

Proof.

Theorem 29.

Proof.

Acknowledgments

References

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

Definition 3 ( $R$ -radial cost).

Definition 4 ( $R$ -local cost).

A.1 Lipschitz Continuity of $g_{1}$ , $g_{2}$ , and $g_{3}$

A.2 Proofs Using the $\varepsilon$ -Net

A.3 Closed-Form Formulas for $g_{1}$ , $g_{2}$ , and $g_{3}$