Corresponding author

# The Traveling Tournament Problem: Improved Algorithms Based on Cycle Packing

Jingyang Zhao<EMAIL_ADDRESS>Mingyu Xiao<EMAIL_ADDRESS>Chao Xu<EMAIL_ADDRESS>School of Computer Science and Engineering,
University of Electronic Science and Technology of China, 2006 Xiyuan Ave,
Chengdu, 610054, Sichuan, China

###### Abstract

The Traveling Tournament Problem (TTP) is a well-known benchmark problem in
the field of tournament timetabling, which asks us to design a double round-
robin schedule such that each pair of teams plays one game in each other’s
home venue, minimizing the total distance traveled by all $n$ teams ($n$ is
even). TTP-$k$ is the problem with one more constraint that each team can have
at most $k$-consecutive home games or away games. In this paper, we
investigate schedules for TTP-$k$ and analyze the approximation ratio of the
solutions. Most previous schedules were constructed based on a Hamiltonian
cycle of the graph. We will propose a novel construction based on a $k$-cycle
packing. Then, combining our $k$-cycle packing schedule with the Hamiltonian
cycle schedule, we obtain improved approximation ratios for TTP-$k$ with deep
analysis. The case where $k=3$, TTP-3, is one of the most investigated cases.
We improve the approximation ratio of TTP-3 from $(1.667+\varepsilon)$ to
$(1.598+\varepsilon)$, for any $\varepsilon>0$. For TTP-$4$, we improve the
approximation ratio from $(1.750+\varepsilon)$ to $(1.700+\varepsilon)$. By a
refined analysis of the Hamiltonian cycle construction, we also improve the
approximation ratio of TTP-$k$ from $(\frac{5k-7}{2k}+\varepsilon)$ to
$(\frac{5k^{2}-4k+3}{2k(k+1)}+\varepsilon)$ for any constant $k\geq 5$. Our
methods can be extended to solve a variant called LDTTP-$k$ (TTP-$k$ where all
teams are allocated on a straight line). We show that the $k$-cycle packing
construction can achieve an approximation ratio of
$(\frac{3k-3}{2k-1}+\varepsilon)$, which improves the approximation ratio of
LDTTP-3 from $4/3$ to $(6/5+\varepsilon)$.

###### keywords:

Approximation Algorithms, Sports Scheduling, Traveling Tournament Problem,
Timetabling Combinatorial Optimization

##  1 Introduction

In the field of the tournament schedule, the traveling tournament problem
(TTP) is a widely known benchmark problem that was first systematically
introduced in [1]. This problem aims to find a double round-robin tournament
satisfying some constraints, minimizing the total distance traveled by all
participant teams. In a double round-robin tournament of $n$ teams, each team
will play 2 games against each of the other $n-1$ teams, one at its home venue
and one at its opponent’s home venue. Additionally, each team should play one
game a day, all games need to be scheduled on $2(n-1)$-consecutive days, and
so there are exactly $n/2$ games on each day. According to the definition, we
know that $n$ is always even. For TTP, we have the following two basic
constraints or assumptions on the double round-robin tournament.

Traveling Tournament Problem (TTP)

  * •

_No-repeat_ : Two teams cannot play against each other on two consecutive
days.

  * •

_Direct-traveling_ : Before the first game, all teams are at home, and they
will return home after the last game. Furthermore, a team travels directly
from its game venue on $i$th day to its game venue on $(i+1)$th day.

TTP-$k$, a well-known variant of TTP, is to add the following constraint on
the maximum number of consecutive home games and away games.

  * •

_Bounded-by- $k$_: Each team can have at most $k$-consecutive home games or
away games.

The smaller the value of $k$, the more frequently a team has to return home.
By contrast, if $k$ is very large, say $k=n-1$, then this constraint loses
meaning, and TTP-$k$ becomes TTP where a team can schedule their travel
distance as short as that in the traveling salesman problem (TSP).

A weight function $w$ on the complete undirected graph is called a _metric_ if
it satisfies the symmetry and triangle inequality properties: $w(a,b)=w(b,a)$
and $w(a,c)\leq w(a,b)+w(b,c)$ for all $a,b,c\in V$.

The input of TTP-$k$ contains a complete graph where each vertex is a team,
and the weight between two vertices $u$ and $v$ is the distance from the home
of team $u$ to the home of team $v$. In this paper, we only consider the case
when the weight function $w$ is a metric.

###  1.1 Related Work

TTP and TTP-$k$ are difficult optimization problems. The NP-hardness of TTP
and TTP-$k$ with $k\geq 3$ has been established [2, 3, 4]. Although the
hardness of TTP-2 is still not formally proved, it is believed that TTP-2 is
also hard since it is not easy to construct a feasible solution to it. In the
literature there is a large number of contributions on approximation
algorithms [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] and heuristic algorithms
[16, 17, 18, 19, 20, 21].

For heuristic algorithms, most known works are concerned with the case of
$k=3$. Since the search spaces of TTP and TTP-$k$ are very large, many
instances with more than 10 teams in the online benchmark [22, 23] have not
been completely solved even by using high-performance machines.

In terms of approximation algorithms, most results are based on the assumption
that the distance holds the symmetry and triangle inequality properties. This
is natural and practical in the sports schedule. For $k=2$, one significant
contribution to TTP-2 was done by Thielen and Westphal [5]. They proposed an
$(1+16/n)$-approximation algorithm for $n/2$ being even and a
$(3/2+O(1/n))$-approximation algorithm for $n/2$ being odd. Approximation
ratios for these two cases have been improved to $(1+3/n)$ and $(1+12/n)$,
respectively [8, 7]. For $k=3$, the first approximation algorithm, proposed by
Miyashiro _et al._ [10], admits a $2+O(1/n)$ approximation ratio by using the
Modified Circle Method. Then, the approximation ratio was improved to
$5/3+O(1/n)$ by Yamaguchi _et al._ [11]. Their approximation algorithm also
works for $3<k=o(n)$. For $k=4$, the ratio is $1.750+O(1/n)$, and for
$4<k=o(n)$, the ratio is $(5k-7)/(2k)+O(k/n)$ [11]. For $k=\Theta(n)$,
Westphal and Noparlik [13] proposed a $5.875$-approximation algorithm for any
choice of $k\geq 4$ and $n\geq 6$, and Imahori _et al._ [12] gave a
$2.75$-approximation algorithm for $k=n-1$ where they also proved that the
ratio could be improved to $2.25$ if the optimal TSP is given. In both of
their algorithms for $k=\Theta(n)$, the approximation ratios can be slightly
improved if they use the randomized $(3/2-\varepsilon_{0})$-approximation
algorithm for TSP [24]. The current best approximation ratio for $k=3$ is
still $5/3+O(1/n)$ [11].

We refer the readers to [23] for more variants of TTP (including the traveling
tournament problem with predefined venues, the time-relaxed traveling
tournament problem, etc.).

###  1.2 Our Contributions

In this paper, we consider approximation algorithms for TTP-$k$ with constant
$k\geq 3$. Our contributions are summarized as follows.

Firstly, we deeply analyze the structural properties, which leads us to
strengthen some of the current-known lower bounds and also to propose several
new lower bounds.

Secondly, we consider the constructions of feasible schedules for TTP-$k$. Our
algorithm will use two constructions. The first construction is based on a
Hamiltonian cycle, which is a known method. The Hamiltonian cycle used in the
literature is usually generated by the Christofides-Serdyukov algorithm [25,
26], while we propose a new Hamiltonian cycle that uses the minimum weight
perfect matching. The second construction is newly proposed by us, which is
based on a $k$-cycle packing. To get our claimed approximation ratios, we will
make a trade-off between the two constructions and do careful analysis.

Thirdly, based on careful analysis, we improve the approximation ratio from
$(5/3+\varepsilon)$ to $(139/87+\varepsilon)$ for TTP-3, and from
$(7/4+\varepsilon)$ to $(17/10+\varepsilon)$ for TTP-4.

Fourthly, we consider TTP-$k$ with $k\geq 5$. By a refined analysis of the
Hamiltonian construction, we improve the approximation ratio from
$(\frac{5k-7}{2k}+\varepsilon)$ to
$(\frac{5k^{2}-4k+3}{2k(k+1)}+\varepsilon)$.

Last, we show that the construction based on the $k$-cycle packing can also be
used to improve Linear Distance TTP-$k$ (LDTTP-$k$), which is a special case
of TTP-$k$ where all teams are on a line. We prove an approximation ratio of
$(\frac{3k-3}{2k-1}+\varepsilon)$ for this problem, which improves the
approximation ratio from $4/3$ [27] to $(6/5+\varepsilon)$ for the case of
$k=3$.

###  1.3 Paper Organization

The remaining parts of the paper are organized as follows. In Section 2, we
introduce basic notations. In Section 3, we propose several new lower bounds.
In Section 4, we introduce the construction methods for the schedules.
Specifically, in Section 4.1, we modify the known construction based on a
Hamiltonian cycle. In Section 4.2, we propose a new construction based on a
$k$-cycle/path packing. Although these two constructions cannot make any
improvement separately, in Section 5, we show that together they can guarantee
an improved approximation ratio for TTP-3 and TTP-4. In Section 5.1, we
analyze the approximation ratio of TTP-3. In Section 5.2, we improve the
approximation ratio for TTP-4. In Section 5.3, we give a refined analysis of
the Hamiltonian construction and improve the approximation ratio for TTP-$k$
with $k\geq 5$. In Section 6, we analyze the approximation ratio of our
algorithm for LDTTP-$k$ with $k\geq 3$. Finally, we make the concluding
remarks in Section 7.

Partial results of this paper were presented at the 47th International
Symposium on Mathematical Foundations of Computer Science (MFCS 2022) [28].

##  2 Preliminaries

We always use $n$ to denote the total number of teams in the problem, where
$n$ is even. The set of $n$ teams is denoted by
$V=\\{t_{1},t_{2},\ldots,t_{n}\\}$. We use $G=(V,E)$ to denote the complete
graph on the $n$ vertices representing the $n$ teams. There is a positive
weight function $w:E\to\mathbb{R}_{\geq 0}$ on the edges of $G$. We often
write $w(u,v)$ to denote the weight of the edge $(u,v)$, which is the distance
between the home of team $u$ and the home of team $v$. For any weight function
$w:X\to\mathbb{R}_{\geq 0}$, we extend it to subsets of $X$. Define
$w(Y)=\sum_{x\in Y}w(x)$ for $Y\subseteq X$. For the sake of analysis, we will
always consider that $k$ is a constant not smaller than 3. Then, in the
following, we also assume that $n\geq 8k^{2}$. Otherwise, since $k$ is a
constant, we can solve TTP-$k$ in constant time.

The following notations work for any graph. We consider w.l.o.g. a graph
$G=(V,E)$. For any $V^{\prime}\subseteq V$, the induced graph of $G$ by
$V^{\prime}$ is denoted as $G[V^{\prime}]$. The weight of a minimum weight
spanning tree in $G$ is denoted by $\mbox{MST}(G)$. We use $\delta_{G}(u)$ to
denote the set of edges incident on a vertex $u$ in $G$. When the graph is an
edge-weighted graph, we use $\deg_{G}(u)$ to denote the weighted degree of a
vertex, i.e., sum of the weights of all edges incident on $u$. We also let
$\Delta_{G}$ be the sum of weighted degrees in $G$, i.e.,

$\Delta_{G}=\sum_{u\in V}\deg_{G}(u)=2w(E).$

Let $m=2\lfloor\frac{n}{4k}\rfloor$. Let $S$ be the set of $2mk$ vertices of
$V$ such that the sum of the weighted degrees of vertices in $S$ is maximized.
The set $S$ can be found in $O(n^{2})$ time by greedily selecting the vertex
with maximum weighted degree. We always use $H=G[S]$ to denote the complete
graph induced by $S$ in $G$. We have

$\displaystyle\sum_{v\in S}\deg_{G}(v)\geq\frac{2mk}{n}\sum_{v\in
V}\deg_{G}(v)=\frac{2mk}{n}\Delta_{G}.$ (1)

We let $\overline{S}=V\setminus S$, $n_{S}=2mk$ and
$n_{\overline{S}}=n-n_{S}=n-4k\lfloor\frac{n}{4k}\rfloor$. Then, there are
$n_{S}$ vertices in $S$. Note that $n_{\overline{S}}<4k$. Since $n\geq
8k^{2}$, we have

$\displaystyle\frac{1}{n_{S}}=\frac{1}{n-n_{\overline{S}}}<\frac{1}{n-4k}<\frac{2}{n}.$
(2)

By (1), we have

$\displaystyle\sum_{v\in\overline{S}}\deg_{G}(v)\leq\frac{n_{\overline{S}}}{n}\sum_{v\in
V}\deg_{G}(v)\leq\frac{4k}{n}\Delta_{G}.$ (3)

Two subgraphs or sets of edges are _vertex-disjoint_ if they do not share a
common vertex. A simple path on $k$ different vertices
$\\{v_{1},v_{2},\dots,v_{k}\\}$ is called a _$k$ -path_ and denoted by
$(v_{1},v_{2},\dots,v_{k})$. A simple cycle on $k$ different vertices
$\\{v_{1},v_{2},\dots,v_{k}\\}$ is called a _$k$ -cycle_ and denoted by
$(v_{1},v_{2},\dots,v_{k},v_{1})$. An $l$-cycle is called a _mod $k$-cycle_ if
$l\bmod k=0$. Hence, a $k$-cycle is also a mod $k$-cycle. A _$k$ -path
packing_ (resp., _(mod) $k$-cycle packing_) in a graph is a set of edges such
that each component is a $k$-path (resp., (mod) $k$-cycle) and all vertices in
the graph are covered. A 2-path packing is also called a _perfect matching_.

We can obtain a $k$-cycle packing from a $k$-path packing by connecting the
first and last vertices of each $k$-path in the packing. We refer to this
operation as _completing the $k$-path packing_. Since $n_{S}\bmod k=0$ and
$n_{S}\bmod 2=0$, there must exist a $k$-cycle packing, $k$-path packing, and
a perfect matching in $H$. Usually, we let $\mathcal{P}_{k}$ denote a $k$-path
packing in $H$, $\mathcal{C}_{k}$ denote a $k$-cycle packing in $H$,
$\mathcal{C}_{\bmod k}$ denote a mod $k$-cycle packing in $H$, and $M_{H}$
denote a perfect matching in $H$.

Recall that $m=\frac{n_{S}}{2k}$. For a $k$-cycle packing $\mathcal{C}_{k}$ in
graph $H$, there are exactly $2m$ $k$-cycles in $\mathcal{C}_{k}$. We assume
that the $2m$ $k$-cycles are $\\{C_{1},\dots,C_{2m}\\}$ and
$C_{i}=(t_{k(i-1)+1},\dots,t_{k(i-1)+k},t_{k(i-1)+1})$ for each $1\leq i\leq
2m$. In our algorithm, we may consider the set of teams in each cycle $C_{i}$
together. For the sake of presentation, we take each cycle $C_{i}$ as a
_cycle-team_ $u_{i}$, which is the set of teams in $C_{i}$, i.e.,
$u_{i}=\\{t_{k(i-1)+1},\dots,t_{k(i-1)+k}\\}$. Each cycle-team contains
exactly $k$ (normal) teams. Furthermore, we also call $U_{i}=u_{2i-1}\cup
u_{2i}$ $(1\leq i\leq m)$ a _super-team_. Each supper-team contains exactly
$2k$ (normal) teams. Let $\mathcal{U}=\\{U_{1},\dots,U_{m}\\}$ denote the set
of all super-teams.

According to the $2m$ cycle-teams $\mathcal{V}=\\{u_{1},\dots,u_{2m}\\}$, we
define a compete graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where we let
$w(u_{i},u_{j})=\sum_{t_{i^{\prime}}\in u_{i}\&t_{j^{\prime}}\in
u_{j}}w(t_{i^{\prime}},t_{j^{\prime}})$ for $i\neq j$ and $w(u_{i},u_{i})=0$.
According to the $m$ super-teams $\mathcal{U}=\\{U_{1},\dots,U_{m}\\}$, we
similarly define another compete graph
$\mathcal{H}=(\mathcal{U},\mathcal{F})$, where we let
$w(U_{i},U_{j})=\sum_{u_{i^{\prime}}\in U_{i}\&u_{j^{\prime}}\in
U_{j}}w(u_{i^{\prime}},u_{j^{\prime}})=\sum_{t_{i^{\prime}}\in
U_{i}\&t_{j^{\prime}}\in U_{j}}w(t_{i^{\prime}},t_{j^{\prime}})$ for $i\neq j$
and $w(U_{i},U_{i})=0$. We also define
$w(u_{i})=\sum_{t_{i^{\prime}},t_{j^{\prime}}\in
C_{i}}w(t_{i^{\prime}},t_{j^{\prime}})$ and
$w(U_{i})=\sum_{t_{i^{\prime}},t_{j^{\prime}}\in
U_{i}}w(t_{i^{\prime}},t_{j^{\prime}})$. Note that $w(X,Y)$ can be seen as the
sum of the weights of edges in the cut $(X,Y)$ of graph $G[X\cup Y]$ and
$w(X)$ can be seen as the sum of the weights of edges in the graph $G[X]$.
Recall that $\Delta_{H}$ is the sum of weighted degrees in $H$. We use $E_{H}$
to denote the set of edges in graph $H$. We can get

$\displaystyle\frac{1}{2}\Delta_{H}=w(E_{H})=w(\mathcal{V})+w(\mathcal{E}).$
(4)

##  3 The Independent Lower Bounds

For TTP and TTP-$k$, a well-known method to obtain the lower bounds is to use
an independent relaxation [29, 1]. The basic idea is to obtain a lower bound
on the traveling distance of each team independently without considering the
feasibility of other teams and then sum them together. Although there exist
many independent lower bounds for TTP-$k$ [10, 11, 13], we cannot use them
directly to get our results. We are interested in a stronger bound. Before we
make some observations on the independent lower bounds, we first need to
explore some properties of TTP-$k$.

For TTP-$k$, each team needs to visit each other team’s home once in the
tournament. A _road trip_ of a team $v$ is a simple cycle starting and ending
at $v$. An _itinerary_ of team $v\in V$ on $G$ is a connected subgraph of $G$
that consists of road trips with each simple cycle of length at most $k+1$,
and each vertex in $V$ other than $v$ has degree $2$. An itinerary is
_optimal_ for a team if it is the itinerary of minimum weight. Considering an
optimal itinerary $I_{v}$ for team $v$, we use $\psi_{v}=w(I_{v})$ to denote
the weight of the optimal itinerary for team $v$. Then, $\psi=\sum_{v\in
V}\psi_{v}$ is a simple independent lower bound for the minimum weight
solution of TTP-$k$. Note that this lower bound was also used in the
experiment [1]. However, it is NP-hard to compute $\psi_{v}$ since it involves
solving the $k$-tour problem and this problem is NP-hard for any fixed $k\geq
3$ [30]. Hence, we want to find an alternative lower bound for each team’s
optimal itinerary.

When $n\bmod{k}=0$, we can prove that there always exists an optimal itinerary
with no 2-cycles.

######  Lemma 1.

For TTP-$k$ with $k\geq 3$, when $n\bmod{k}=0$, there exists an optimal
itinerary with no 2-cycles for each team.

###### Proof.

Consider an optimal itinerary $I_{v}$ of team $v$ with the minimum number of
2-cycles. Assume $I_{v}$ contains a 2-cycle. Since all cycles share the vertex
$v$, by the triangle inequality, we can get a $(k^{\prime}+1)$-cycle by
shortcutting one 2-cycle and one $k^{\prime}$-cycle, and the
$(k^{\prime}+1)$-cycle has a weight of no greater than the sum of the weights
of the two cycles. This shows that $I_{v}$ contains no $k^{\prime}$-cycles
($3\leq k^{\prime}\leq k$) and at most one $2$-cycle if it contains one
2-cycle. Thus, $I_{v}$ contains only one 2-cycle, and the rest cycles are all
$(k+1)$-cycles. We get $n\bmod k=2$, a contradiction to $n\bmod k=0$. ∎

The number of vertices in graph $H$ is $n_{S}=2mk$, which is divisible by $k$.
We may consider an optimal itinerary of a team $v\in S$ on graph $H$, denoted
by $I^{H}_{v}$. Recall that $I_{v}$ is an optimal itinerary of the team $v$ on
graph $G$. By the triangle inequality, it is easy to see that
$w(I^{H}_{v})\leq w(I_{v})$. Next, we consider several lower bounds on
$w(I^{H}_{v})$, which can also be used as lower bounds of $w(I_{v})$.

###  3.1 Bounds on the Optimal Itinerary

In this subsection, we fix a single team $v\in S$ and consider the optimal
itinerary $I^{H}_{v}$ on graph $H$ for this team. We will give a more refined
analysis than that in the previous paper [11].

By Lemma 1, there exists an optimal itinerary $I^{H}_{v}$ with no 2-cycles,
and it consists of a set of $(k+1)$-cycles and a set of $k^{\prime}$-cycles
($3\leq k^{\prime}\leq k$). Hence we will partition $I^{H}_{v}$ into two sets:

  1. 1.

$I^{H}_{v,1}$ consists of all $(k+1)$-cycles; and

  2. 2.

$I^{H}_{v,2}$ consists of the other $k^{\prime}$-cycles.

Define $0\leq\gamma_{v}\leq 1$, such that

$w(I^{H}_{v,1})=\gamma_{v}w(I^{H}_{v}),\quad\mbox{and}\quad
w(I^{H}_{v,2})=(1-\gamma_{v})w(I^{H}_{v}).$

Hence $\gamma_{v}$ measures the proportion of weights of the $(k+1)$-cycles
compared to the entire itinerary. The edges in graph $H$ incident to $v$ in
$I^{H}_{v}$ are called _home-edges_ , which is the same as $\delta_{H}(v)\cap
I^{H}_{v}$. Let $\alpha_{v}$ and $\beta_{v}$ be the proportion of weights of
the home-edges in $I^{H}_{v,1}$ and $I^{H}_{v,2}$, respectively. Namely,

$\alpha_{v}w(I^{H}_{v,1})=w(I^{H}_{v,1}\cap\delta_{H}(v))$

is the weight of all home-edges in $I^{H}_{v,1}$, and

$\beta_{v}w(I^{H}_{v,2})=w(I^{H}_{v,2}\cap\delta_{H}(v))$

is the weight of all home-edges in $I^{H}_{v,2}$.

Now, we are ready to give bounds for the optimal itinerary $I^{H}_{v}$.

######  Lemma 2.

Let $C_{H}$ be a minimum weight Hamiltonian cycle in graph $H$. It holds that
$w(I^{H}_{v})\geq w(C_{H})$.

###### Proof.

According to the definition of the itinerary, we know that each vertex in
$I^{H}_{v}$ has an even degree. Then, we can get an Eulerian tour in
$I^{H}_{v}$ and obtain a Hamiltonian cycle in graph $H$ by shortcutting
$I^{H}_{v}$. Hence $w(I^{H}_{v})\geq w(C_{H})$. ∎

We also recall the following result.

######  Lemma 3 ([25, 26]).

For graph $H$, let $C_{H}$ be a minimum weight Hamiltonian cycle and
$C^{\prime}_{H}$ be a Hamiltonian cycle obtained by the Christofides-Serdyukov
algorithm. It holds that
$w(C^{\prime}_{H})\leq\mbox{MST}(H)+\frac{1}{2}w(C_{H})$.

For ease of proofs in the rest of the section, we also define $S_{v,1}$ and
$S_{v,2}$ that partition the vertices in $S\setminus\\{v\\}$, where $S_{v,1}$
consists of all vertices in $I^{H}_{v,1}$ except $v$, and $S_{v,2}$ consists
of all vertices in $I^{H}_{v,2}$ except $v$. Our results are mostly simple
counting arguments.

######  Lemma 4.

It holds that
$(\frac{k-1}{2}-\frac{1}{2}\gamma_{v}+\alpha_{v}\gamma_{v})w(I^{H}_{v})\geq(\frac{k-2}{2}+\alpha_{v})\gamma_{v}w(I^{H}_{v})+(\frac{k-3}{2}+\beta_{v})(1-\gamma_{v})w(I^{H}_{v})\geq\deg_{H}(v)$.

###### Proof.

By the definition of $\beta_{v}$, we have $1\geq\beta_{v}$. Hence, we have

$\displaystyle\left(\frac{k-1}{2}-\frac{1}{2}\gamma_{v}+\alpha_{v}\gamma_{v}\right)w(I^{H}_{v})$
$\displaystyle=\left(\frac{k-2}{2}+\alpha_{v}\right)\gamma_{v}w(I^{H}_{v})+\left(\frac{k-3}{2}+1\right)(1-\gamma_{v})w(I^{H}_{v})$
$\displaystyle\geq\left(\frac{k-2}{2}+\alpha_{v}\right)\gamma_{v}w(I^{H}_{v})+\left(\frac{k-3}{2}+\beta_{v}\right)(1-\gamma_{v})w(I^{H}_{v}).$

The left inequality holds. Now we consider the right inequality.

First, we can see $\deg_{H}(v)=\sum_{u\in S_{v,1}}w(u,v)+\sum_{u\in
S_{v,2}}w(u,v)$.

Next, recall that
$\alpha_{v}\gamma_{v}w(I^{H}_{v})=w(I^{H}_{v,1}\cap\delta_{H}(v))$ is the
total weight of all home-edges in $(k+1)$-cycles. For any $(k+1)$-cycle
$C=(v,v_{1},\dots,v_{k},v)$ in $I^{H}_{v,1}$, note that the edges $(v,v_{1})$
and $(v,v_{k})$ are home-edges which can be counted by
$w(I^{H}_{v,1}\cap\delta_{H}(v))$, but the edges $(v,v_{i})$ with $2\leq i\leq
k-1$ are not home-edges. By the triangle inequality, we know that
$w(v,v_{i})\leq\frac{1}{2}w(C)$. Therefore, the weight of the uncounted edges
are at most $\frac{k-2}{2}w(C)$. Thus, we have

$\sum_{u\in
S_{v,1}}w(u,v)\leq\left(\frac{k-2}{2}+\alpha_{v}\right)\gamma_{v}w(I^{H}_{v}).$

Similarly,
$\beta_{v}(1-\gamma_{v})w(I^{H}_{v})=w(I^{H}_{v,2}\cap\delta_{H}(v))$ is the
weight of all home-edges in $k^{\prime}$-cycles. For any $k^{\prime}$-cycle
$C=(v,v_{1},\dots,v_{k^{\prime}-1},v)$ in $I^{H}_{v,2}$, the home-edges
$(v,v_{1})$ and $(v,v_{k^{\prime}-1})$ can be counted by
$w(I^{H}_{v,2}\cap\delta_{H}(v))$. The weight of the uncounted edges are at
most $\frac{k^{\prime}-3}{2}w(C)\leq\frac{k-3}{2}w(C)$. Thus, we have

$\sum_{u\in
S_{v,2}}w(u,v)\leq\left(\frac{k-3}{2}+\beta_{v}\right)\gamma_{v}w(I^{H}_{v}).$

Then, we have

$\displaystyle\left(\frac{k-2}{2}+\alpha_{v}\right)\gamma_{v}w(I^{H}_{v})+\left(\frac{k-3}{2}+\beta_{v}\right)(1-\gamma_{v})w(I^{H}_{v})$
$\displaystyle\geq\sum_{u\in S_{v,1}}w(u,v)+\sum_{u\in
S_{v,2}}w(u,v)=\deg_{H}(v).$

∎

######  Lemma 5.

It holds that
$(1-\frac{1}{2}\alpha_{v})\gamma_{v}w(I^{H}_{v})+(1-\frac{1}{2}\beta_{v})(1-\gamma_{v})w(I^{H}_{v})\geq\mbox{MST}(H)$.

###### Proof.

In the optimal itinerary of $v$ on $H$, the total weight of all home-edges is

$\alpha_{v}\gamma_{v}w(I^{H}_{v})+\beta_{v}(1-\gamma_{v})w(I^{H}_{v}).$

For each cycle, there are exactly two home-edges. We can delete the longer
edge from each cycle from $I^{H}_{v}$, and get a spanning tree with a total
weight of at most

$\left(1-\frac{1}{2}\alpha_{v}\right)\gamma_{v}w(I^{H}_{v})+\left(1-\frac{1}{2}\beta_{v}\right)(1-\gamma_{v})w(I^{H}_{v}).$

Since the weight of a minimum spanning tree in graph $H$ is $\mbox{MST}(H)$,
we have that

$\left(1-\frac{1}{2}\alpha_{v}\right)\gamma_{v}w(I^{H}_{v})+\left(1-\frac{1}{2}\beta_{v}\right)(1-\gamma_{v})w(I^{H}_{v})\geq\mbox{MST}(H).$

The lemma holds. ∎

The new bounds in Lemmas 4 and 5 are stronger than that in [11]. Next, we
propose two new lower bounds on the minimum weight perfect matching and
$k$-cycle/path packing. The lower bound related to the minimum weight perfect
matching works only for TTP-3.

######  Lemma 6.

Let $M_{H}$ be a minimum weight perfect matching in graph $H$. For TTP-3, we
have that
$\frac{1}{2}\gamma_{v}w(I^{H}_{v})+(1-\beta_{v})(1-\gamma_{v})w(I^{H}_{v})\geq
w(M_{H})$.

###### Proof.

We assume that $k=3$ and consider TTP-3. Note that $I^{H}_{v,1}$ is a set of
4-cycles and $I^{H}_{v,2}$ is a set of 3-cycles. Since $n_{S}=2mk=6m$, we know
that the number of vertices in $S_{v,1}$ is odd but even in $S_{v,2}$. Since
any pair of 3-cycles only share one common vertex $v$, after we delete both of
home-edges of each 3-cycle, we can get a perfect matching $M^{\prime}_{H}$ in
graph $H[S_{v,2}]$ with a total weight of
$(1-\beta_{v})(1-\gamma_{v})w(I^{H}_{v})$.

Then, by a similar argument in the proof of Lemma 2, we know that
$\gamma_{v}w(I^{H}_{v})=w(I^{H}_{v,1})$ is greater than the weight of the
minimum weight Hamiltonian cycle in graph $H[S_{v,1}\cup\\{v\\}]$. Since the
number of vertices in this graph is even, any Hamiltonian cycle in this graph
can be decomposed into two perfect matchings. Thus, we can get a perfect
matching $M^{\prime\prime}_{H}$ in this graph with a total weight of at most
$\frac{1}{2}\gamma_{v}w(I^{H}_{v})$. Therefore, $M^{\prime}_{H}\cup
M^{\prime\prime}_{H}$ is a perfect matching in graph $H$, and then we have
$w(M_{H})\leq w(M^{\prime}_{H}\cup
M^{\prime\prime}_{H})\leq\frac{1}{2}\gamma_{v}w(I^{H}_{v})+(1-\beta_{v})(1-\gamma_{v})w(I^{H}_{v})$.
∎

######  Lemma 7.

For graph $H$, let $\mathcal{P}^{*}_{k}$ be a minimum weight $k$-path packing,
and $\mathcal{C}^{*}_{k}$ be a minimum weight $k$-cycle packing. It holds that
$\left(\frac{k-1}{k}+\frac{1}{k}\gamma_{v}-\alpha_{v}\gamma_{v}\right)w(I^{H}_{v})=(1-\alpha_{v})\gamma_{v}w(I^{H}_{v})+\frac{k-1}{k}(1-\gamma_{v})w(I^{H}_{v})\geq
w(\mathcal{P}^{*}_{k})\geq\frac{1}{2}w(\mathcal{C}^{*}_{k})$.

###### Proof.

First, we consider
$w(\mathcal{P}^{*}_{k})\geq\frac{1}{2}w(\mathcal{C}^{*}_{k})$. Let
$\mathcal{C}^{\prime}_{k}$ be the $k$-cycle packing obtained by completing the
$k$-path packing. For any $k$-path in $\mathcal{P}^{*}_{k}$, saying
$P=(v_{1},\dots,v_{k})$, we obtain $w(P)\geq w(v_{1},v_{k})$ by the triangle
inequality. This shows $2w(\mathcal{P}^{*}_{k})\geq
w(\mathcal{C}^{\prime}_{k})\geq w(\mathcal{C}^{*}_{k})$, and we are done.

We note that the number of vertices is divisible by $k$ in $S_{v,1}$ but not
in $S_{v,2}$. Since any pair of $(k+1)$-cycles only share one common vertex
$v$, after we delete both of home-edges for each $(k+1)$-cycle, we can get a
$k$-path packing $\mathcal{P}^{\prime}_{k}$ in graph $H[S_{v,1}]$ such that
$w(\mathcal{P}^{\prime}_{k})=(1-\alpha_{v})\gamma_{v}w(I^{H}_{v})$.

Then, by a similar argument in the proof of Lemma 2, we know that
$(1-\gamma_{v})w(I^{H}_{v})=w(I^{H}_{v,2})\geq w(C)$ where $C$ is the minimum
weight Hamiltonian cycle in graph $H[S_{v,2}\cup\\{v\\}]$. Since the number of
vertices in this graph equals $n_{S}$ minus the number of vertices in
$S_{v,1}$, which is divisible by $k$, it is easy to see that we can delete an
edge every $k-1$ edges along $C$ to get a $k$-path packing
$\mathcal{P}^{\prime\prime}_{k}$ such that
$w(\mathcal{P}^{\prime\prime}_{k})\leq\frac{k-1}{k}w(C)$. Note that
$\mathcal{P}^{\prime}_{k}\cup\mathcal{P}^{\prime\prime}_{k}$ is a $k$-path
packing in graph $H$. Thus, we have that
$(1-\alpha_{v})\gamma_{v}w(I^{H}_{v})+\frac{2}{3}(1-\gamma_{v})w(I^{H}_{v})\geq
w(\mathcal{P}^{\prime}_{k}\cup\mathcal{P}^{\prime\prime}_{k})\geq
w(\mathcal{P}^{*}_{k})$. ∎

Then, we propose a new lower bound related to the minimum weight mod $k$-cycle
packing, a stronger lower bound related to the minimum weight $k$-cycle
packing, and a lower bound related to the minimum weight perfect matching for
any $k\geq 3$.

######  Lemma 8.

For graph $H$, let $\mathcal{C}^{*}_{\bmod k}$ be a minimum weight mod
$k$-cycle packing. It holds that
$\min\\{2(1-\alpha_{v}),1\\}\cdot\gamma_{v}w(I^{H}_{v})+(1-\gamma_{v})w(I^{H}_{v})\geq
w(\mathcal{C}^{*}_{\bmod k})$.

###### Proof.

We first construct a $k$-cycle packing in $H[S_{v,1}]$. For any $(k+1)$-cycle
$C=(v,v_{1},\dots,v_{k},v)$ in $I^{H}_{v,1}$, we can get a $(k+1)$-cycle
$C^{\prime}=(v_{1},\dots,v_{k},v_{1})$ with a weight of
$\sum_{i=1}^{k-1}w(v_{i},v_{i+1})+w(v_{1},v_{k})=w(C)-w(v,v_{1})-w(v,v_{k})+w(v_{1},v_{k})$.
By the triangle inequality, we have

$w(v_{1},v_{k})\leq\min\\{w(C)-w(v,v_{1})-w(v,v_{k}),\
w(v,v_{1})+w(v,v_{k})\\}.$

Hence, we have

$w(C^{\prime})\leq\min\\{2(w(C)-w(v,v_{1})-w(v,v_{k})),\ w(C)\\}.$

Since $(v,v_{1})$ and $(v,v_{k})$ are home-edges, we can get a $k$-cycle
packing $\mathcal{C}^{\prime}_{k}$ in $H[S_{v,1}]$ such that

$\displaystyle w(\mathcal{C}^{\prime}_{k})$
$\displaystyle\leq\min\\{2(w(I^{H}_{v,1})-w(I^{H}_{v,1}\cap\delta_{H}(v))),\
w(I^{H}_{v,1})\\}$ $\displaystyle=\min\\{2(1-\alpha_{v})w(I^{H}_{v,1}),\
w(I^{H}_{v,1})\\}$
$\displaystyle=\min\\{2(1-\alpha_{v}),1\\}\cdot\gamma_{v}w(I^{H}_{v}),$

where the first equality follows from
$w(I^{H}_{v,1}\cap\delta_{H}(v))=\alpha_{v}w(I^{H}_{v,1})$, and the second
follows from $w(I^{H}_{v,1})=\gamma_{v}w(I^{H}_{v})$.

Then, by the proof of Lemma 7, we know that $(1-\gamma_{v})w(I^{H}_{v})\geq
w(C^{\prime\prime})$, where $C^{\prime\prime}$ is the minimum weight
Hamiltonian cycle in graph $H[S_{v,2}\cup\\{v\\}]$ and the number of vertices
in $C$ is divisible by $k$. Hence, we can get a mod $k$-cycle packing
$\mathcal{C}^{\prime\prime}_{\bmod k}=\\{C^{\prime\prime}\\}$ in
$H[S_{v,2}\cup\\{v\\}]$ such that

$w(\mathcal{C}^{\prime\prime}_{\bmod k})\leq(1-\gamma_{v})w(I^{H}_{v}).$

Since $\mathcal{C}^{\prime}_{k}\cup\mathcal{C}^{\prime\prime}_{\bmod k}$ is a
mod $k$-cycle packing in $H$ and $\mathcal{C}^{*}_{\bmod k}$ is a minimum
weight mod $k$-cycle packing in $H$, $\mathcal{C}^{*}_{\bmod k}$ has a weight
of at most
$\min\\{2(1-\alpha_{v}),1\\}\cdot\gamma_{v}w(I^{H}_{v})+(1-\gamma_{v})w(I^{H}_{v})$.
∎

######  Lemma 9.

For graph $H$, let $\mathcal{C}^{*}_{k}$ be a minimum weight $k$-cycle
packing. It holds that
$\min\\{2(1-\alpha_{v}),1\\}\cdot\gamma_{v}w(I^{H}_{v})+\frac{2(k-1)}{k}(1-\gamma_{v})w(I^{H}_{v})\geq
w(\mathcal{C}^{*}_{k})$.

###### Proof.

By the proof of Lemma 8, we can get a $k$-cycle packing
$\mathcal{C}^{\prime}_{k}$ in $H[S_{v,1}]$ with a weight of at most
$\min\\{2(1-\alpha_{v}),1\\}\cdot\gamma_{v}w(I^{H}_{v})$. By the proof of
Lemma 7, we can get a $k$-cycle packing $\mathcal{C}^{\prime\prime}_{k}$ with
a weight of at most $\frac{2(k-1)}{k}(1-\gamma_{v})w(I^{H}_{v})$. Therefore,
there is a $k$-cycle packing
$\mathcal{C}^{\prime}_{k}\cup\mathcal{C}^{\prime\prime}_{k}$ in $H$ with a
weight of at most
$\min\\{2(1-\alpha_{v}),1\\}\cdot\gamma_{v}w(I^{H}_{v})+\frac{2(k-1)}{k}(1-\gamma_{v})w(I^{H}_{v})$.
Since $\mathcal{C}^{*}_{k}$ is the minimum weight $k$-cycle packing in $H$,
the lemma holds. ∎

######  Lemma 10.

Let $C_{H}$ be a minimum weight Hamiltonian cycle, $\mathcal{C}^{*}_{\bmod k}$
is a minimum weight mod $k$-cycle packing, and $M_{H}$ be a minimum weight
perfect matching in graph $H$. For TTP-$k$ with $k\geq 3$, we have $w(H)\geq
2w(M_{H})$. Moreover, if $k$ is even, we have $w(\mathcal{C}^{*}_{\bmod
k})\geq 2w(M_{H})$.

###### Proof.

Since the number of vertices in $H$ is even, the edges of $C_{H}$ can be
decomposed into two perfect matchings. The one with a smaller weight has a
weight of at most $w(C_{H})$. So, $w(H)\geq 2w(M_{H})$.

If $k$ is even, the number of vertices on each cycle
$C\in\mathcal{C}^{*}_{\bmod k}$ is also even. Similarly, for each cycle
$C\in\mathcal{C}^{*}_{\bmod k}$, we can obtain a perfect matching $M_{C}$ in
the graph induced by the vertices of $C$ with a weight of at most
$\frac{1}{2}w(C)$. Hence, we obtain a perfect matching in $H$ with a weight of
at most $\frac{1}{2}w(\mathcal{C}^{*}_{\bmod k})$. So, we have
$w(\mathcal{C}^{*}_{\bmod k})\geq 2w(M_{H})$. ∎

###  3.2 Independent Lower Bounds

Now, we are ready to consider the independent lower bounds, which are found by
summing the individual optimal itineraries of teams in $S$ on graph $H$.

For each team $v\in S$, $I_{v}$ (resp., $I^{H}_{v}$) is the optimal itinerary
of team $v$ on graph $G$ (resp., $H$). Recall that $\psi=\sum_{v\in
V}\psi_{v}$ and $\psi_{v}=w(I_{v})$. We define

$\psi^{H}=\sum_{v\in
S}\psi^{H}_{v}\mbox{~{}~{}and~{}~{}}\psi^{H}_{v}=w(I^{H}_{v}).$

Then, we can get

$\psi=\sum_{v\in V}w(I_{v})\geq\sum_{v\in S}w(I_{v})\geq\sum_{v\in
S}w(I^{H}_{v})=\psi^{H},$

i.e., $\psi^{H}$ is a lower bound of TTP-$k$.

Define $\gamma$, $\alpha$ and $\beta$ such that it holds

$\gamma\psi^{H}=\sum_{v\in S}w(I^{H}_{v,1})=\sum_{v\in
S}\gamma_{v}w(I^{H}_{v}),$ $\alpha\gamma\psi^{H}=\sum_{v\in
S}w(\delta_{H}(v)\cap I^{H}_{v,1})=\sum_{v\in
S}\alpha_{v}\gamma_{v}w(I^{H}_{v}),$

and

$\beta(1-\gamma)\psi^{H}=\sum_{v\in S}w(\delta_{H}(v)\cap
I^{H}_{v,2})=\sum_{v\in S}\beta_{v}(1-\gamma_{v})w(I^{H}_{v}).$

We have $0\leq\gamma,\alpha,\beta\leq 1$.

The lemmas we proved previously can be summed together to obtain different
lower bounds.

######  Lemma 11.

Let $C_{H}$ be a minimum weight Hamiltonian cycle in graph $H$. It holds that

$\psi\geq n_{S}w(C_{H}).$

###### Proof.

Since $\psi\geq\psi^{H}=\sum_{v\in S}w(I^{H}_{v})$, by Lemma 2, we have
$\psi\geq\sum_{v\in S}w(I^{H}_{v})\geq n_{S}w(C_{H})$. ∎

######  Lemma 12.

$(\frac{k-1}{2}-\frac{1}{2}\gamma+\alpha\gamma)\psi\geq(\frac{k-2}{2}+\alpha)\gamma\psi+(\frac{k-3}{2}+\beta)(1-\gamma)\psi\geq\Delta_{H}$.

###### Proof.

Since $\psi\geq\psi^{H}$, it is sufficient to prove

$\left(\frac{k-1}{2}-\frac{1}{2}\gamma+\alpha\gamma\right)\psi^{H}\geq\left(\frac{k-2}{2}+\alpha\right)\gamma\psi^{H}+\left(\frac{k-3}{2}+\beta\right)(1-\gamma)\psi^{H}\geq\Delta_{H}.$

By the definitions of $\gamma$, $\alpha$ and $\beta$, we have

$\left(\frac{k-1}{2}-\frac{1}{2}\gamma+\alpha\gamma\right)\psi^{H}=\sum_{v\in
S}\left(\frac{k-1}{2}-\frac{1}{2}\gamma_{v}+\alpha_{v}\gamma_{v}\right)w(I^{H}_{v})$

and

$\displaystyle\left(\frac{k-2}{2}+\alpha\right)\gamma\psi^{H}+\left(\frac{k-3}{2}+\beta\right)(1-\gamma)\psi^{H}$
$\displaystyle\ =\sum_{v\in
S}\left(\left(\frac{k-2}{2}+\alpha_{v}\right)\gamma_{v}w(I^{H}_{v})+\left(\frac{k-3}{2}+\beta_{v}\right)(1-\gamma_{v})w(I^{H}_{v})\right).$

Recall that $\Delta_{H}=\sum_{v\in S}\deg_{H}(v)$. By Lemma 4, it holds that

$\displaystyle\sum_{v\in
S}\left(\frac{k-1}{2}-\frac{1}{2}\gamma_{v}+\alpha_{v}\gamma_{v}\right)w(I^{H}_{v})$
$\displaystyle\geq\sum_{v\in
S}\left(\left(\frac{k-2}{2}+\alpha_{v}\right)\gamma_{v}w(I^{H}_{v})+\left(\frac{k-3}{2}+\beta_{v}\right)(1-\gamma_{v})w(I^{H}_{v})\right)$
$\displaystyle\geq\sum_{v\in S}\deg_{H}(v)=\Delta_{H}.$

Then, we have

$\left(\frac{k-1}{2}-\frac{1}{2}\gamma+\alpha\gamma\right)\psi^{H}\geq\left(\frac{k-2}{2}+\alpha\right)\gamma\psi^{H}+\left(\frac{k-3}{2}+\beta\right)(1-\gamma)\psi^{H}\geq\Delta_{H}.$

∎

Note that
$\Delta_{H}\leq(\frac{k-1}{2}-\frac{1}{2}\gamma+\alpha\gamma)\psi\leq\frac{k}{2}\psi$.
The lower bound $\Delta_{H}\leq\frac{k}{2}\psi$ can be extended to the graph
$G$. We have the following lemma.

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

$\frac{k}{2}\psi\geq\Delta_{G}$.

Note that $\Delta_{G}\leq\Delta_{H}+2\sum_{v\in\overline{S}}\deg_{G}(v)$. By
(3) and Lemma 13, we have that

$\Delta_{G}\leq\Delta_{H}+\frac{4k^{2}}{n}\psi.$ (5)

######  Lemma 14.

It holds that

$\left(1-\frac{1}{2}\alpha\right)\gamma\psi+\left(1-\frac{1}{2}\beta\right)(1-\gamma)\psi\geq
n_{S}\mbox{MST}(H).$

###### Proof.

We will prove
$(1-\frac{1}{2}\alpha)\gamma\psi^{H}+(1-\frac{1}{2}\beta)(1-\gamma)\psi^{H}\geq
n_{S}\mbox{MST}(H)$.

Note that

$\displaystyle\left(1-\frac{1}{2}\alpha\right)\gamma\psi^{H}+\left(1-\frac{1}{2}\beta\right)(1-\gamma)\psi^{H}$
$\displaystyle=\sum_{v\in
S}\left(\left(1-\frac{1}{2}\alpha_{v}\right)\gamma_{v}w(I^{H}_{v})+\left(1-\frac{1}{2}\beta_{v}\right)(1-\gamma_{v})w(I^{H}_{v})\right).$

By Lemma 5, we know that

$\sum_{v\in
S}\left(\left(1-\frac{1}{2}\alpha_{v}\right)\gamma_{v}w(I^{H}_{v})+\left(1-\frac{1}{2}\beta_{v}\right)(1-\gamma_{v})w(I^{H}_{v})\right)\geq
n_{S}\mbox{MST}(H).$

Thus, we have

$\left(1-\frac{1}{2}\alpha\right)\gamma\psi^{H}+\left(1-\frac{1}{2}\beta\right)(1-\gamma)\psi^{H}\geq
n_{S}\mbox{MST}(H).$

∎

By Lemmas 12 and 14, we have that

$\left(\frac{k+1}{4}+\frac{1}{4}\gamma\right)\psi\geq\frac{1}{2}\Delta_{H}+n_{S}\mbox{MST}(H).$
(6)

######  Lemma 15.

Let $M_{H}$ be a minimum weight perfect matching in graph $H$. For TTP-3, we
have that

$\frac{1}{2}\gamma\psi+(1-\beta)(1-\gamma)\psi\geq n_{S}w(M_{H}).$

###### Proof.

We will prove $\frac{1}{2}\gamma\psi^{H}+(1-\beta)(1-\gamma)\psi^{H}+\geq
n_{S}w(M_{H})$.

Note that

$\frac{1}{2}\gamma\psi^{H}+(1-\beta)(1-\gamma)\psi^{H}=\sum_{v\in
S}\left(\frac{1}{2}\gamma_{v}w(I^{H}_{v})+(1-\beta_{v})(1-\gamma_{v})w(I^{H}_{v})\right).$

By Lemma 6, we know that

$\sum_{v\in
S}\left(\frac{1}{2}\gamma_{v}w(I^{H}_{v})+(1-\beta_{v})(1-\gamma_{v})w(I^{H}_{v})\right)\geq
n_{S}w(M_{H}).$

Thus, we have

$\frac{1}{2}\gamma\psi^{H}+(1-\beta)(1-\gamma)\psi^{H}\geq n_{S}w(M_{H}).$

∎

By Lemmas 12 and 15, for TTP-3, we have that

$(1+\alpha\gamma)\psi\geq\Delta_{H}+n_{S}w(M_{H})$ (7)

for a minimum weight perfect matching $M_{H}$ in graph $H$.

######  Lemma 16.

For graph $G$, let $\mathcal{P}^{*}_{k}$ be a minimum weight $k$-path packing,
and $\mathcal{C}^{*}_{k}$ be a minimum weight $k$-cycle packing. It holds that

$\left(\frac{k-1}{k}+\frac{1}{k}\gamma-\alpha\gamma\right)\psi=(1-\alpha)\gamma\psi+\frac{k-1}{k}(1-\gamma)\psi\geq
n_{S}w(\mathcal{P}^{*}_{k})\geq\frac{1}{2}n_{S}w(\mathcal{C}^{*}_{k}).$

###### Proof.

We will prove
$(\frac{k-1}{k}+\frac{1}{k}\gamma-\alpha\gamma)\psi^{H}=(1-\alpha)\gamma\psi^{H}+\frac{k-1}{k}(1-\gamma)\psi^{H}\geq
n_{S}w(\mathcal{P}^{*}_{k})\geq\frac{1}{2}n_{S}w(\mathcal{C}^{*}_{k})$.

Note that

$\left(\frac{k-1}{k}+\frac{1}{k}\gamma-\alpha\gamma\right)\psi^{H}=\sum_{v\in
S}\left(\frac{k-1}{k}+\frac{1}{k}\gamma_{v}-\alpha_{v}\gamma_{v}\right)w(I^{H}_{v})$

and

$(1-\alpha)\gamma\psi^{H}+\frac{k-1}{k}(1-\gamma)\psi^{H}=\sum_{v\in
S}\left((1-\alpha_{v})\gamma_{v}w(I^{H}_{v})+\frac{k-1}{k}(1-\gamma_{v})w(I^{H}_{v})\right).$

By Lemma 7, it holds that

$\displaystyle\sum_{v\in
S}\left(\frac{k-1}{k}+\frac{1}{k}\gamma_{v}-\alpha_{v}\gamma_{v}\right)w(I^{H}_{v})\geq$
$\displaystyle\ \sum_{v\in
S}\left((1-\alpha_{v})\gamma_{v}w(I^{H}_{v})+\frac{k-1}{k}(1-\gamma_{v})w(I^{H}_{v})\right)$
$\displaystyle\geq$ $\displaystyle\
n_{S}w(\mathcal{P}^{*}_{k})\geq\frac{1}{2}n_{S}w(\mathcal{C}^{*}_{k}).$

Therefore, we have that

$\left(\frac{k-1}{k}+\frac{1}{k}\gamma-\alpha\gamma\right)\psi^{H}=(1-\alpha)\gamma\psi^{H}+\frac{k-1}{k}(1-\gamma)\psi^{H}\geq
n_{S}w(\mathcal{P}^{*}_{k})\geq\frac{1}{2}n_{S}w(\mathcal{C}^{*}_{k}).$

∎

######  Lemma 17.

For graph $H$, let $\mathcal{C}^{*}_{\bmod k}$ be a minimum weight mod
$k$-cycle packing. It holds that

$\min\\{2(1-\alpha),1\\}\cdot\gamma\psi+(1-\gamma)\psi\geq
n_{S}w(\mathcal{C}^{*}_{\bmod k}).$

###### Proof.

The proof follows from a similar analysis in the proof of Lemma 16. ∎

######  Lemma 18.

For graph $H$, let $\mathcal{C}^{*}_{k}$ be a minimum weight $k$-cycle
packing. It holds that

$\min\\{2(1-\alpha),1\\}\cdot\gamma\psi+\frac{2(k-1)}{k}(1-\gamma)\psi\geq
n_{S}w(\mathcal{C}^{*}_{k}).$

###### Proof.

The proof follows from a similar analysis in the proof of Lemma 16. ∎

######  Lemma 19.

Let $M_{H}$ be a minimum weight perfect matching in graph $H$. For TTP-$k$
with $k\geq 3$, we have $\frac{1}{2}\psi\geq n_{S}w(M_{H})$. Moreover, if $k$
is even, we have

$\frac{1}{2}\cdot\min\\{2(1-\alpha),1\\}\cdot\gamma\psi+\frac{1}{2}(1-\gamma)\psi\geq
n_{S}w(M_{H}).$

###### Proof.

It follows directly from Lemmas 10, 11, and 17. ∎

Next, we will describe our algorithm. Our algorithm consists of two
constructions, where the first is based on the Hamiltonian cycle and the
second is based on the $k$-cycle/path packing. The quality of each will be
analyzed after showing the construction. At last, we will analyze the
approximation quality of each, make a trade-off between them, and then get the
final approximation ratio.

##  4 The Constructions

In this section, we introduce the methods to construct feasible schedules for
TTP-$k$. We have two construction methods. The first construction is based on
a given Hamiltonian cycle of the graph. This method has been widely used in
the literature and we will not repeat all the details. The second construction
is based on a given cycle packing of the graph. This can be considered as a
new method. We need to use the two methods to do some trade-offs in the
analysis.

###  4.1 The Hamiltonian Cycle Construction

The idea of Hamiltonian cycle construction is to make use of the canonical
schedule [31, 32] and a Hamiltonian cycle. For TTP-$k$, many previous
schedules were constructed by using this method [11, 13, 12]. In our
algorithm, we will also directly use the well-analyzed schedule in [11]. Next,
we give a brief introduction to this construction.

Roughly speaking, this schedule is generated by a rotation scheme that can
make sure that almost all road trips of each team are $(k+1)$-cycles and in
each road trip, the team visits a set of consecutive teams along the
Hamiltonian cycle used. For the quality of this construction, we have the
following lemma.

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

Let $C$ be a Hamiltonian cycle in graph $G$. For TTP-$k$ with any constant
$k\geq 3$, there is a polynomial-time algorithm that can generate a solution
with a total weight of at most

$\frac{k-1}{k}nw(C)+\frac{2}{k}\Delta_{G}+O(k/n)\psi.$

We cannot use this result directly since most of our previous lower bounds are
based on the graph $H$. To get a similar result based on a given Hamiltonian
cycle in graph $H$, we prove the following lemma.

######  Lemma 21.

Let $C_{H}$ be a Hamiltonian cycle in graph $H$ such that $n_{S}w(C_{H})\leq
O(1)\psi$. For TTP-$k$ with any constant $k\geq 3$, there is a polynomial-time
algorithm that can generate a solution with a total weight of at most

$\frac{k-1}{k}n_{S}w(C_{H})+\frac{2}{k}\Delta_{H}+O(k^{2}/n)\psi.$

###### Proof.

Given a Hamiltonian cycle $C_{H}$ in graph $H$, we can construct a graph by
adding two copies of edge $(u,v)$ for each $u\in\overline{S}$, where
$v=\arg\min_{v^{\prime}\in S}w(u,v^{\prime})$. So, it holds that

$w(u,v)\leq\frac{1}{n_{S}}\sum_{v^{\prime}\in S}w(u,v^{\prime}).$

The new graph is a connected Eulerian graph on vertex set $V$, and the total
weight of edges in this graph is at most

$w(C_{H})+\sum_{u\in\overline{S}}\left(\frac{2}{n_{S}}\sum_{v\in
S}w(u,v)\right)\leq
w(C_{H})+\frac{2}{n_{S}}\sum_{u\in\overline{S}}\deg_{G}(u)\leq
w(C_{H})+\frac{16k}{n^{2}}\Delta_{G},$ (8)

where the first inequality follows from $\sum_{v\in S}w(u,v)\leq\sum_{v\in
V}w(u,v)=\deg_{G}(u)$, and the second follows from Lemma 3 and (2). By
shortcutting this Eulerian graph, we can get a Hamiltonian cycle $C$ in graph
$G$ with a weight of at most

$w(C_{H})+\frac{16k}{n^{2}}\Delta_{G}\leq w(C_{H})+\frac{8k^{2}}{n^{2}}\psi$

by Lemma 13 and (8). Using this cycle, by Lemma 20, we can generate a solution
with a total weight of at most

$\displaystyle\frac{k-1}{k}n\left(w(C_{H})+\frac{8k^{2}}{n^{2}}\psi\right)+\frac{2}{k}\Delta_{G}+O(k/n)\psi$
$\displaystyle\leq\frac{k-1}{k}nw(C_{H})+\frac{2}{k}\Delta_{G}+\frac{8k^{2}}{n}\psi+O(k/n)\psi.$

Note that

$\frac{k-1}{k}nw(C_{H})\leq\frac{k-1}{k}n_{S}w(C_{H})+n_{\overline{S}}w(C_{H})\leq\frac{k-1}{k}n_{S}w(C_{H})+\frac{8k}{n}n_{S}w(C_{H}),$

where the first inequality follows from $n=n_{S}+n_{\overline{S}}$, and the
second follows from $n_{\overline{S}}<4k$ and $1/n_{S}<2/n$ by (2). By (5), we
also have

$\frac{2}{k}\Delta_{G}=\frac{2}{k}\Delta_{H}+\frac{8k}{n}\psi.$

Based on the condition that $n_{S}w(C_{H})\leq O(1)\psi$, we know that the
total weight of the solution is at most

$\displaystyle\frac{k-1}{k}nw(C_{H})+\frac{2}{k}\Delta_{G}+\frac{8k^{2}}{n}\psi+O(k/n)\psi$
$\displaystyle\
\leq\frac{k-1}{k}n_{S}w(C_{H})+\frac{2}{k}\Delta_{H}+\frac{8k}{n}n_{S}w(C_{H})+\frac{8k}{n}\psi+\frac{8k^{2}}{n}\psi+O(k/n)\psi$
$\displaystyle\
\leq\frac{k-1}{k}n_{S}w(C_{H})+\frac{2}{k}\Delta_{H}+O(k^{2}/n)\psi.$

∎

Note that the condition $n_{S}w(C_{H})\leq O(1)\psi$ in Lemma 21 is easy to
satisfy. For example, if the Hamiltonian cycle $C_{H}$ is obtained by the
Christofides-Serdyukov algorithm (a $3/2$-approximation algorithm for TSP)
[25, 26], then we have $n_{S}w(C_{H})\leq\frac{3}{2}\psi=O(1)\psi$ by Lemma
11.

###  4.2 The Cycle Packing Construction

In this subsection, we will construct a feasible schedule based on a given
$k$-cycle packing of the graph. We will also show that the construction works
for a given $k$-path packing. One challenge for the construction is to build a
feasible schedule for $n$ not being divisible by $k$. We introduce the
construction in detail.

####  4.2.1 The construction

Given a $k$-cycle packing $\mathcal{C}_{k}=\\{C_{1},\dots,C_{2m}\\}$ in graph
$H$. Recall that the $k$-cycles were arbitrarily labeled. There are $2m$
cycle-teams $\\{u_{1},\dots,u_{2m}\\}$ and $m$ super-teams
$\\{U_{1},\dots,U_{m}\\}$, where $U_{i}=u_{2i-1}\cup u_{2i}$ and
$u_{i}=\\{t_{k(i-1)+1},\dots,t_{k(i-1)+k}\\}$. There are still
$n_{\overline{S}}$ normal teams in $\overline{S}$, which will be arbitrarily
divided into $n_{\overline{S}}/2$ pairs, denoted by $r$ _team-pairs_
$\\{R_{1},\dots,R_{r}\\}$, where $R_{i}=\\{t_{n_{S}+2i-1},t_{n_{S}+2i}\\}$ and
$r=n_{\overline{S}}/2$. The packing construction is to first arrange _super-
games_ for super-teams (including the $r$ team-pairs) and then extend the
super-games into a double round-robin for normal teams.

Recall that $n\geq 8k^{2}$, $n_{S}=2mk$, and $n_{\overline{S}}=n-n_{S}$.
Hence, we have $m=2\lfloor\frac{n}{4k}\rfloor\geq 4k>n_{\overline{S}}=2r$.
Each super-team will first attend $m-1$ super-games in $m-1$ time slots. Each
super-game will be extended to normal games between normal teams that span
$4k$ days. So each normal team will attend $4k(m-1)$ normal games. Note that
each normal team should attend $2n-2$ normal games in TTP-$k$. Recall that
$n=2mk+2r$. Hence, there are still $2n-2-4k(m-1)=4k+4r-2$ days of normal
games, called _unarranged normal games_ , which will be designed after the
super-games in the last time slot.

We will construct the schedule for super-teams from the first time slot to the
last time slot. In each of the $m-1$ time slots, we have $m/2$ super-games.
The schedule in the last time slot, which also contains the design of
unarranged normal games, is different from the schedules in the first $m-2$
time slots.

For the first time slot, the $m/2$ super-games are arranged as shown in Figure
1. The most left super-game including two super-teams is called _left super-
game_ , it contains two super-teams, and we put a letter ‘L’ on the edge to
indicate it. The most right $r$ super-games are called _right super-games_ ,
each of them contains two super-teams and one team-pair, and we put a letter
‘R’ on the edge to indicate it. The middle $m/2-r-1$ super-games are called
_normal super-games_ and each of them contains two super-teams. Each super-
game contains a directed edge between the two super-teams, where a directed
edge from $U_{i}$ to $U_{j}$ means a super-game between them at the home of
$U_{j}$.

Figure 1: The schedule in the first time slot for an instance with $m=10$ and
$r=2$

In Figure 1, we can see that the last super-team $U_{m}$ and the $r$ team-
pairs are denoted as dark nodes and all other super-teams
$\\{U_{1},\dots,U_{m-1}\\}$ are denoted as white nodes which form a cycle
$(U_{1},\dots,U_{m-1},U_{1})$. In the second time slot, we fix the positions
of dark nodes and change the positions of white super-teams in the cycle by
moving one position in the clockwise direction, and we also change the
direction of each edge. In the second time slot, there is still $1$ left
super-game, $m/2-r-1$ normal super-games and $r$ right super-games. An
illustration of the schedule in the second time slot is shown in Figure 2.

Figure 2: The schedule in the second time slot for an instance with $m=10$ and
$r=2$

The schedules for the other middle slots are derived analogously. Before we
introduce the super-games in the last time slot, we first explain how to
extend the super-games in the first $m-2$ time slots to normal games. In these
time slots, we have three different kinds of super-games: normal super-games,
left super-games and right super-games. We first consider normal super-games.

Normal super-games: Assume that there is a normal super-game $U_{i}\rightarrow
U_{j}$, i.e., a normal super-game between super-teams $U_{i}$ and $U_{j}$ at
the home of $U_{j}$. Recall that $U_{i}$ represents cycle-teams $u_{2i-1}\cup
u_{2i}$ and $U_{j}$ represents cycle-teams $u_{2j-1}\cup u_{2j}$. The normal
super-game will be extended to _cycle-games_ in two _sub-time slots_ : in the
first sub-time slot, there are two _normal cycle-games_ :
$\\{u_{2i-1}\rightarrow u_{2j-1},\ u_{2i}\rightarrow u_{2j}\\}$, where
$u_{i^{\prime}}\rightarrow u_{i^{\prime\prime}}$ means a normal cycle-game
between cycle-teams $u_{i^{\prime}}$ and $u_{i^{\prime\prime}}$ at the home of
$u_{i^{\prime\prime}}$; in the second sub-time slot, there are still two
normal cycle-games: $\\{u_{2i-1}\rightarrow u_{2j},\ u_{2i}\rightarrow
u_{2j-1}\\}$.

Next, we only need to explain the design of normal cycle-games.

Assume that there is a normal cycle-game $u_{i}\rightarrow u_{j}$, i.e., a
normal cycle-game between cycle-teams $u_{i}$ and $u_{j}$ at the home of
$u_{j}$. Recall that $u_{i}$ represents normal teams
$\\{t_{k(i-1)+1},\dots,t_{k(i-1)+k}\\}$ and $u_{j}$ represents normal teams
$\\{t_{k(j-1)+1},\dots,t_{k(j-1)+k}\\}$. For the sake of presentation, we let
$t_{k(i-1)+i^{\prime}}=x_{i^{\prime}}$ and
$t_{k(j-1)+i^{\prime}}=y_{i^{\prime}}$, i.e., $u_{i}=\\{x_{1},\dots,x_{k}\\}$
and $u_{j}=\\{y_{1},\dots,y_{k}\\}$. Let $p_{l}$ denote the $k$ normal games
in $\\{x_{i}\rightarrow y_{(i+l-2)\bmod k)+1}\\}_{i=1}^{k}$, where
$x_{i^{\prime}}\rightarrow y_{i^{\prime\prime}}$ means a normal game between
normal teams $x_{i^{\prime}}$ and $y_{i^{\prime\prime}}$ at the home of
$y_{i^{\prime\prime}}$. In the following, we also use $\overline{p_{l}}$ to
denote the $k$ normal games of $p_{l}$, but with all venues reversed. The
normal cycle-game will be extended to normal games on $2k$ days, which can can
be presented by

$\left(p_{1}\cdots p_{k-2}\cdot p_{k-1}\cdot
p_{k}\right)\cdot\left(\overline{p_{1}\cdots p_{k-2}\cdot p_{k-1}\cdot
p_{k}}\right).$

An example of a normal super-game with $k=3$ is shown in Table 1. We can see
that each normal super-game will be extended to normal games on $4k$ days.
There are at most $k$-consecutive home/away normal games. The normal games
between normal teams in $U_{i}$ and normal teams in $U_{j}$, which can be seen
as a directed complete bipartite graph $B(U_{i},U_{j})$, are all arranged.

| $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$
---|---|---|---|---|---|---|---|---|---|---|---|---
$x_{1}$ | $y_{1}$ | $y_{2}$ | $y_{3}$ | $\boldsymbol{y_{1}}$ | $\boldsymbol{y_{2}}$ | $\boldsymbol{y_{3}}$ | $y_{4}$ | $y_{5}$ | $y_{6}$ | $\boldsymbol{y_{4}}$ | $\boldsymbol{y_{5}}$ | $\boldsymbol{y_{6}}$
$x_{2}$ | $y_{2}$ | $y_{3}$ | $y_{1}$ | $\boldsymbol{y_{2}}$ | $\boldsymbol{y_{3}}$ | $\boldsymbol{y_{1}}$ | $y_{5}$ | $y_{6}$ | $y_{4}$ | $\boldsymbol{y_{5}}$ | $\boldsymbol{y_{6}}$ | $\boldsymbol{y_{4}}$
$x_{3}$ | $y_{3}$ | $y_{1}$ | $y_{2}$ | $\boldsymbol{y_{3}}$ | $\boldsymbol{y_{1}}$ | $\boldsymbol{y_{2}}$ | $y_{6}$ | $y_{4}$ | $y_{5}$ | $\boldsymbol{y_{6}}$ | $\boldsymbol{y_{4}}$ | $\boldsymbol{y_{5}}$
$x_{4}$ | $y_{4}$ | $y_{5}$ | $y_{6}$ | $\boldsymbol{y_{4}}$ | $\boldsymbol{y_{5}}$ | $\boldsymbol{y_{6}}$ | $y_{1}$ | $y_{2}$ | $y_{3}$ | $\boldsymbol{y_{1}}$ | $\boldsymbol{y_{2}}$ | $\boldsymbol{y_{3}}$
$x_{5}$ | $y_{5}$ | $y_{6}$ | $y_{4}$ | $\boldsymbol{y_{5}}$ | $\boldsymbol{y_{6}}$ | $\boldsymbol{y_{4}}$ | $y_{2}$ | $y_{3}$ | $y_{1}$ | $\boldsymbol{y_{2}}$ | $\boldsymbol{y_{3}}$ | $\boldsymbol{y_{1}}$
$x_{6}$ | $y_{6}$ | $y_{4}$ | $y_{5}$ | $\boldsymbol{y_{6}}$ | $\boldsymbol{y_{4}}$ | $\boldsymbol{y_{5}}$ | $y_{3}$ | $y_{1}$ | $y_{2}$ | $\boldsymbol{y_{3}}$ | $\boldsymbol{y_{1}}$ | $\boldsymbol{y_{2}}$
$y_{1}$ | $\boldsymbol{x_{1}}$ | $\boldsymbol{x_{3}}$ | $\boldsymbol{x_{2}}$ | $x_{1}$ | $x_{3}$ | $x_{2}$ | $\boldsymbol{x_{4}}$ | $\boldsymbol{x_{6}}$ | $\boldsymbol{x_{5}}$ | $x_{4}$ | $x_{6}$ | $x_{5}$
$y_{2}$ | $\boldsymbol{x_{2}}$ | $\boldsymbol{x_{1}}$ | $\boldsymbol{x_{3}}$ | $x_{2}$ | $x_{1}$ | $x_{3}$ | $\boldsymbol{x_{5}}$ | $\boldsymbol{x_{4}}$ | $\boldsymbol{x_{6}}$ | $x_{5}$ | $x_{4}$ | $x_{6}$
$y_{3}$ | $\boldsymbol{x_{3}}$ | $\boldsymbol{x_{2}}$ | $\boldsymbol{x_{1}}$ | $x_{3}$ | $x_{2}$ | $x_{1}$ | $\boldsymbol{x_{6}}$ | $\boldsymbol{x_{5}}$ | $\boldsymbol{x_{4}}$ | $x_{6}$ | $x_{5}$ | $x_{4}$
$y_{4}$ | $\boldsymbol{x_{4}}$ | $\boldsymbol{x_{6}}$ | $\boldsymbol{x_{5}}$ | $x_{4}$ | $x_{6}$ | $x_{5}$ | $\boldsymbol{x_{1}}$ | $\boldsymbol{x_{3}}$ | $\boldsymbol{x_{2}}$ | $x_{1}$ | $x_{3}$ | $x_{2}$
$y_{5}$ | $\boldsymbol{x_{5}}$ | $\boldsymbol{x_{4}}$ | $\boldsymbol{x_{6}}$ | $x_{5}$ | $x_{4}$ | $x_{6}$ | $\boldsymbol{x_{2}}$ | $\boldsymbol{x_{1}}$ | $\boldsymbol{x_{3}}$ | $x_{2}$ | $x_{1}$ | $x_{3}$
$y_{6}$ | $\boldsymbol{x_{6}}$ | $\boldsymbol{x_{5}}$ | $\boldsymbol{x_{4}}$ | $x_{6}$ | $x_{5}$ | $x_{4}$ | $\boldsymbol{x_{3}}$ | $\boldsymbol{x_{2}}$ | $\boldsymbol{x_{1}}$ | $x_{3}$ | $x_{2}$ | $x_{1}$
Table 1: Extending the normal super-game $U_{i}\rightarrow U_{j}$ between
super-teams $u_{i}$ and $U_{j}$, where $U_{i}=u_{2i-1}\cup
u_{2i}=\\{x_{1},x_{2},x_{3}\\}\cup\\{x_{4},x_{5},x_{6}\\}$,
$U_{j}=u_{2j-1}\cup
u_{2j}=\\{y_{1},y_{2},y_{3}\\}\cup\\{y_{4},y_{5},y_{6}\\}$, and home games are
marked in bold

Left super-games: Assume that there is a left super-game
$U_{i}\xrightarrow{L}U_{j}$, i.e., a left super-game between super-teams
$U_{i}$ and $U_{j}$ at the home of $U_{j}$. Recall that $U_{i}$ represents
cycle-teams $u_{2i-1}\cup u_{2i}$ and $U_{j}$ represents cycle-teams
$u_{2j-1}\cup u_{2j}$. The left super-game will be extended to cycle-games in
two sub-time slots: in the first sub-time slot, there are two _left cycle-
games_ : $\\{u_{2i-1}\xrightarrow{L}u_{2j-1},\
u_{2i}\xrightarrow{L}u_{2j}\\}$, where
$u_{i^{\prime}}\xrightarrow{L}u_{i^{\prime\prime}}$ means a left cycle-game
between cycle-teams $u_{i^{\prime}}$ and $u_{i^{\prime\prime}}$ at the home of
$u_{i^{\prime\prime}}$; in the second sub-time slot, there are still two left
cycle-games: $\\{u_{2i-1}\xrightarrow{L}u_{2j},\
u_{2i}\xrightarrow{L}u_{2j-1}\\}$.

Next, we only need to explain the design of left cycle-games.

Assume that there is a left cycle-game $u_{i}\xrightarrow{L}u_{j}$, i.e., a
left cycle-game between cycle-teams $u_{i}$ and $u_{j}$ at the home of
$u_{j}$. Let $u_{i}=\\{x_{1},\dots,x_{k}\\}$ and
$u_{j}=\\{y_{1},\dots,y_{k}\\}$. Let $p_{l}$ denote the $k$ normal games in
$\\{x_{i}\rightarrow y_{(i+l-2)\bmod k)+1}\\}_{i=1}^{k}$. The left cycle-game
will be extended to normal games on $2k$ days, which can can be presented by

$\left(p_{1}\cdots p_{k-2}\cdot
p_{k-1}\cdot\overline{p_{k}}\right)\cdot\left(\overline{p_{1}\cdots
p_{k-2}\cdot p_{k-1}\cdot\overline{p_{k}}}\right).$

An example of a left super-game with $k=3$ is shown in Table 2. We can see
that each left super-game will be extended to normal games on $4k$ days. There
are at most $k$-consecutive home/away normal games. The normal games between
normal teams in $U_{i}$ and normal teams in $U_{j}$, which can be seen as a
directed complete bipartite graph $B(U_{i},U_{j})$, are all arranged.

| $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$
---|---|---|---|---|---|---|---|---|---|---|---|---
$x_{1}$ | $y_{1}$ | $y_{2}$ | $\boldsymbol{y_{3}}$ | $\boldsymbol{y_{1}}$ | $\boldsymbol{y_{2}}$ | $y_{3}$ | $y_{4}$ | $y_{5}$ | $\boldsymbol{y_{6}}$ | $\boldsymbol{y_{4}}$ | $\boldsymbol{y_{5}}$ | $y_{6}$
$x_{2}$ | $y_{2}$ | $y_{3}$ | $\boldsymbol{y_{1}}$ | $\boldsymbol{y_{2}}$ | $\boldsymbol{y_{3}}$ | $y_{1}$ | $y_{5}$ | $y_{6}$ | $\boldsymbol{y_{4}}$ | $\boldsymbol{y_{5}}$ | $\boldsymbol{y_{6}}$ | $y_{4}$
$x_{3}$ | $y_{3}$ | $y_{1}$ | $\boldsymbol{y_{2}}$ | $\boldsymbol{y_{3}}$ | $\boldsymbol{y_{1}}$ | $y_{2}$ | $y_{6}$ | $y_{4}$ | $\boldsymbol{y_{5}}$ | $\boldsymbol{y_{6}}$ | $\boldsymbol{y_{4}}$ | $y_{5}$
$x_{4}$ | $y_{4}$ | $y_{5}$ | $\boldsymbol{y_{6}}$ | $\boldsymbol{y_{4}}$ | $\boldsymbol{y_{5}}$ | $y_{6}$ | $y_{1}$ | $y_{2}$ | $\boldsymbol{y_{3}}$ | $\boldsymbol{y_{1}}$ | $\boldsymbol{y_{2}}$ | $y_{3}$
$x_{5}$ | $y_{5}$ | $y_{6}$ | $\boldsymbol{y_{4}}$ | $\boldsymbol{y_{5}}$ | $\boldsymbol{y_{6}}$ | $y_{4}$ | $y_{2}$ | $y_{3}$ | $\boldsymbol{y_{1}}$ | $\boldsymbol{y_{2}}$ | $\boldsymbol{y_{3}}$ | $y_{1}$
$x_{6}$ | $y_{6}$ | $y_{4}$ | $\boldsymbol{y_{5}}$ | $\boldsymbol{y_{6}}$ | $\boldsymbol{y_{4}}$ | $y_{5}$ | $y_{3}$ | $y_{1}$ | $\boldsymbol{y_{2}}$ | $\boldsymbol{y_{3}}$ | $\boldsymbol{y_{1}}$ | $y_{2}$
$y_{1}$ | $\boldsymbol{x_{1}}$ | $\boldsymbol{x_{3}}$ | $x_{2}$ | $x_{1}$ | $x_{3}$ | $\boldsymbol{x_{2}}$ | $\boldsymbol{x_{4}}$ | $\boldsymbol{x_{6}}$ | $x_{5}$ | $x_{4}$ | $x_{6}$ | $\boldsymbol{x_{5}}$
$y_{2}$ | $\boldsymbol{x_{2}}$ | $\boldsymbol{x_{1}}$ | $x_{3}$ | $x_{2}$ | $x_{1}$ | $\boldsymbol{x_{3}}$ | $\boldsymbol{x_{5}}$ | $\boldsymbol{x_{4}}$ | $x_{6}$ | $x_{5}$ | $x_{4}$ | $\boldsymbol{x_{6}}$
$y_{3}$ | $\boldsymbol{x_{3}}$ | $\boldsymbol{x_{2}}$ | $x_{1}$ | $x_{3}$ | $x_{2}$ | $\boldsymbol{x_{1}}$ | $\boldsymbol{x_{6}}$ | $\boldsymbol{x_{5}}$ | $x_{4}$ | $x_{6}$ | $x_{5}$ | $\boldsymbol{x_{4}}$
$y_{4}$ | $\boldsymbol{x_{4}}$ | $\boldsymbol{x_{6}}$ | $x_{5}$ | $x_{4}$ | $x_{6}$ | $\boldsymbol{x_{5}}$ | $\boldsymbol{x_{1}}$ | $\boldsymbol{x_{3}}$ | $x_{2}$ | $x_{1}$ | $x_{3}$ | $\boldsymbol{x_{2}}$
$y_{5}$ | $\boldsymbol{x_{5}}$ | $\boldsymbol{x_{4}}$ | $x_{6}$ | $x_{5}$ | $x_{4}$ | $\boldsymbol{x_{6}}$ | $\boldsymbol{x_{2}}$ | $\boldsymbol{x_{1}}$ | $x_{3}$ | $x_{2}$ | $x_{1}$ | $\boldsymbol{x_{3}}$
$y_{6}$ | $\boldsymbol{x_{6}}$ | $\boldsymbol{x_{5}}$ | $x_{4}$ | $x_{6}$ | $x_{5}$ | $\boldsymbol{x_{4}}$ | $\boldsymbol{x_{3}}$ | $\boldsymbol{x_{2}}$ | $x_{1}$ | $x_{3}$ | $x_{2}$ | $\boldsymbol{x_{1}}$
Table 2: Extending the left super-game $U_{i}\xrightarrow{L}U_{j}$ between
super-teams $u_{i}$ and $U_{j}$, where $U_{i}=u_{2i-1}\cup
u_{2i}=\\{x_{1},x_{2},x_{3}\\}\cup\\{x_{4},x_{5},x_{6}\\}$,
$U_{j}=u_{2j-1}\cup
u_{2j}=\\{y_{1},y_{2},y_{3}\\}\cup\\{y_{4},y_{5},y_{6}\\}$, and home games are
marked in bold

Right super-games: Assume that there is a right super-game
$\\{U_{i}\xrightarrow{R}U_{j}\\}$, i.e., a right super-game between super-
teams $U_{i}$ and $U_{j}$ at the home of $U_{j}$. There also should be a team-
pair $R_{i^{\prime}}$. Recall that $U_{i}$ represents cycle-teams
$u_{2i-1}\cup u_{2i}$, $U_{j}$ represents cycle-teams $u_{2j-1}\cup u_{2j}$,
and $R_{i}=\\{t_{n_{S}+2i^{\prime}-1},t_{n_{S}+2i^{\prime}}\\}$. The super-
game will be directly extended to normal-games on $4k$ days. Let
$U_{i}=\\{x_{1},\dots,x_{k}\\}\cup\\{x_{k+1},\dots,x_{2k}\\}$ and
$U_{j}=\\{y_{1},\dots,y_{k}\\}\cup\\{y_{k+1},\dots,y_{2k}\\}$. In the
schedule, if the position of $U_{i}$ is above $U_{j}$ (for example, the
position of $U_{4}$ is above $U_{5}$ while the position of $U_{6}$ is below
$U_{3}$ in Figure 1), we let $t_{n_{S}+2i^{\prime}-1}=x_{2k+1}$ and
$t_{n_{S}+2i^{\prime}}=y_{2k+1}$, otherwise, we let
$t_{n_{S}+2i^{\prime}-1}=y_{2k+1}$ and $t_{n_{S}+2i^{\prime}}=x_{2k+1}$.
Moreover, let $p_{l}$ denote the $2k+1$ normal games in $\\{x_{i}\rightarrow
y_{(2k+2l-i)\bmod(2k+1)+1}\\}_{i=1}^{2k+1}$. The right super-game will be
extended to normal games on $2k$ days, which can can be presented by

$\displaystyle\left(p_{1}\cdots p_{k-2}\cdot\overline{p_{k-1}}\cdot
p_{k}\right)\cdot\left(\overline{p_{1}\cdots
p_{k-2}\cdot\overline{p_{k-1}}\cdot p_{k}}\right)$
$\displaystyle\cdot\left(p_{k+1}\cdots p_{2k-2}\cdot\overline{p_{2k-1}}\cdot
p_{2k}\right)\cdot\left(\overline{p_{k+1}\cdots
p_{2k-2}\cdot\overline{p_{2k-1}}\cdot p_{2k}}\right).$

An example of a right super-game with $k=3$ is shown in Table 3. We can see
that each right super-game will be extended to normal games on $4k$ days.
There are at most $k$-consecutive home/away normal games. Comparing with
normal/left super-games, there are two more normal teams in $R_{i^{\prime}}$,
and hence two days of normal games, $p_{2k+1}\cup\overline{p_{2k+1}}$, are not
arranged. We will arrange them after the super-games in the last time slot.

| $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$
---|---|---|---|---|---|---|---|---|---|---|---|---
$x_{1}$ | $y_{1}$ | $\boldsymbol{y_{3}}$ | $y_{5}$ | $\boldsymbol{y_{1}}$ | $y_{3}$ | $\boldsymbol{y_{5}}$ | $y_{7}$ | $\boldsymbol{y_{2}}$ | $y_{4}$ | $\boldsymbol{y_{7}}$ | $y_{2}$ | $\boldsymbol{y_{4}}$
$x_{2}$ | $y_{7}$ | $\boldsymbol{y_{2}}$ | $y_{4}$ | $\boldsymbol{y_{7}}$ | $y_{2}$ | $\boldsymbol{y_{4}}$ | $y_{6}$ | $\boldsymbol{y_{1}}$ | $y_{3}$ | $\boldsymbol{y_{6}}$ | $y_{1}$ | $\boldsymbol{y_{3}}$
$x_{3}$ | $y_{6}$ | $\boldsymbol{y_{1}}$ | $y_{3}$ | $\boldsymbol{y_{6}}$ | $y_{1}$ | $\boldsymbol{y_{3}}$ | $y_{5}$ | $\boldsymbol{y_{7}}$ | $y_{2}$ | $\boldsymbol{y_{5}}$ | $y_{7}$ | $\boldsymbol{y_{2}}$
$x_{4}$ | $y_{5}$ | $\boldsymbol{y_{7}}$ | $y_{2}$ | $\boldsymbol{y_{5}}$ | $y_{7}$ | $\boldsymbol{y_{2}}$ | $y_{4}$ | $\boldsymbol{y_{6}}$ | $y_{1}$ | $\boldsymbol{y_{4}}$ | $y_{6}$ | $\boldsymbol{y_{1}}$
$x_{5}$ | $y_{4}$ | $\boldsymbol{y_{6}}$ | $y_{1}$ | $\boldsymbol{y_{4}}$ | $y_{6}$ | $\boldsymbol{y_{1}}$ | $y_{3}$ | $\boldsymbol{y_{5}}$ | $y_{7}$ | $\boldsymbol{y_{3}}$ | $y_{5}$ | $\boldsymbol{y_{7}}$
$x_{6}$ | $y_{3}$ | $\boldsymbol{y_{5}}$ | $y_{7}$ | $\boldsymbol{y_{3}}$ | $y_{5}$ | $\boldsymbol{y_{7}}$ | $y_{2}$ | $\boldsymbol{y_{4}}$ | $y_{6}$ | $\boldsymbol{y_{2}}$ | $y_{4}$ | $\boldsymbol{y_{6}}$
$x_{7}$ | $y_{2}$ | $\boldsymbol{y_{4}}$ | $y_{6}$ | $\boldsymbol{y_{2}}$ | $y_{4}$ | $\boldsymbol{y_{6}}$ | $y_{1}$ | $\boldsymbol{y_{3}}$ | $y_{5}$ | $\boldsymbol{y_{1}}$ | $y_{3}$ | $\boldsymbol{y_{5}}$
$y_{1}$ | $\boldsymbol{x_{1}}$ | $x_{3}$ | $\boldsymbol{x_{5}}$ | $x_{1}$ | $\boldsymbol{x_{3}}$ | $x_{5}$ | $\boldsymbol{x_{7}}$ | $x_{2}$ | $\boldsymbol{x_{4}}$ | $x_{7}$ | $\boldsymbol{x_{2}}$ | $x_{4}$
$y_{2}$ | $\boldsymbol{x_{7}}$ | $x_{2}$ | $\boldsymbol{x_{4}}$ | $x_{7}$ | $\boldsymbol{x_{2}}$ | $x_{4}$ | $\boldsymbol{x_{6}}$ | $x_{1}$ | $\boldsymbol{x_{3}}$ | $x_{6}$ | $\boldsymbol{x_{1}}$ | $x_{3}$
$y_{3}$ | $\boldsymbol{x_{6}}$ | $x_{1}$ | $\boldsymbol{x_{3}}$ | $x_{6}$ | $\boldsymbol{x_{1}}$ | $x_{3}$ | $\boldsymbol{x_{5}}$ | $x_{7}$ | $\boldsymbol{x_{2}}$ | $x_{5}$ | $\boldsymbol{x_{7}}$ | $x_{2}$
$y_{4}$ | $\boldsymbol{x_{5}}$ | $x_{7}$ | $\boldsymbol{x_{2}}$ | $x_{5}$ | $\boldsymbol{x_{7}}$ | $x_{2}$ | $\boldsymbol{x_{4}}$ | $x_{6}$ | $\boldsymbol{x_{1}}$ | $x_{4}$ | $\boldsymbol{x_{6}}$ | $x_{1}$
$y_{5}$ | $\boldsymbol{x_{4}}$ | $x_{6}$ | $\boldsymbol{x_{1}}$ | $x_{4}$ | $\boldsymbol{x_{6}}$ | $x_{1}$ | $\boldsymbol{x_{3}}$ | $x_{5}$ | $\boldsymbol{x_{7}}$ | $x_{3}$ | $\boldsymbol{x_{5}}$ | $x_{7}$
$y_{6}$ | $\boldsymbol{x_{3}}$ | $x_{5}$ | $\boldsymbol{x_{7}}$ | $x_{3}$ | $\boldsymbol{x_{5}}$ | $x_{7}$ | $\boldsymbol{x_{2}}$ | $x_{4}$ | $\boldsymbol{x_{6}}$ | $x_{2}$ | $\boldsymbol{x_{4}}$ | $x_{6}$
$y_{7}$ | $\boldsymbol{x_{2}}$ | $x_{4}$ | $\boldsymbol{x_{6}}$ | $x_{2}$ | $\boldsymbol{x_{4}}$ | $x_{6}$ | $\boldsymbol{x_{1}}$ | $x_{3}$ | $\boldsymbol{x_{5}}$ | $x_{1}$ | $\boldsymbol{x_{3}}$ | $x_{5}$
Table 3: Extending the right super-game $U_{i}\xrightarrow{R}U_{j}$ between
super-teams $u_{i}$ and $U_{j}$ with a team-pair $R_{i^{\prime}}$, where
$U_{i}=u_{2i-1}\cup
u_{2i}=\\{x_{1},x_{2},x_{3}\\}\cup\\{x_{4},x_{5},x_{6}\\}$,
$U_{j}=u_{2j-1}\cup
u_{2j}=\\{y_{1},y_{2},y_{3}\\}\cup\\{y_{4},y_{5},y_{6}\\}$,
$R_{i^{\prime}}=\\{x_{2k+1},y_{2k+1}\\}$, and home games are marked in bold

The first $m-2$ time slots will be extended to $4k(m-2)$ days. Recall that
$n=2km+2r$. Each normal team will have $2n-2-4k(m-2)=8k+4r-2$ remaining normal
games, which correspond to the normal games in the last time slot.

The last time slot. In the last time slot, we will first design $m/2$ super-
games, and then we will design the unarranged normal games. Figure 3 shows the
$m/2$ super-games of our schedule in the last time slot. Except for the $r$
right super-games, the rest super-games are all left super-games.

Figure 3: The schedule in the last time slot for an instance with $m=10$ and
$r=2$

We use $H$ and $A$ to denote a home and an away normal game, respectively. An
advantage of left/right super-games is that: by the design of left/right
super-games as shown in Tables 2 and 3, all normal teams play $AH$ or $HA$ on
the last two days of the super-games. It can help us to combine the unarranged
normal games without creating more than $k$-consecutive home/away normal
games.

Next, we will design the unarranged normal games. Since the $m/2$ super-games
in the last time slot have already spanned $4k$ days, the unarranged normal
games will span $4k+4r-2$ days. To design unarranged normal games, we will
consider two cases of normal teams.

Case 1: We first consider the normal teams in super-team $U_{m}$ and the $r$
team-pairs $\\{R_{1},\dots,R_{r}\\}$. By the design of left, normal, and right
super-games, we have not arranged the normal games between normal teams in
each super-team and team-pair. Note that the positions of super-team $U_{m}$
and the $r$ team-pairs are fixed, and hence they never meet each other in the
schedule. The normal games between normal teams in $U_{m}$ and normal teams in
$R_{i}$, and the normal games between normal teams in $R_{i}$ and normal teams
in $R_{i^{\prime}}$, are unarranged. There are $2k$ normal teams in $U_{m}$
and $2$ normal teams in each team-pair. The normal games between normal teams
in $U_{m}\cup R_{1}\cup\cdots R_{r}$, which can seen as a directed complete
graph, form a double round-robin on these $2k+2r$ (even) normal teams. Hence,
we can take $2\cdot(2k+2r-1)=4k+4r-2$ days to arrange a double-round robin for
them. That is exactly the number of left days. To design a double round-robin,
we need to make sure that it can combine well with the super-games in the last
time-slot, i.e., without creating more than $k$-consecutive home/away normal
games. Since all of them play $AH$ or $HA$ on the last two days of the super-
games in the last time slot, we can call an algorithm of TTP-2 to satisfy the
bounded-by-$k$ and no-repeat constraints [5, 8]. Since there are at most two
consecutive home/away normal games for TTP-2, we can put the TTP-2 double-
round robin behind the super-games in the last time slot, which will not
create more than three consecutive home/away normal games.

Case 2: Next, we consider the normal teams in super-teams $U_{1}\cup\cdots
U_{m-1}$. The unarranged normal games can be summarized as two parts. Recall
that there are two days of normal games $p_{2k+1}\cup\overline{p_{2k+1}}$
unarranged in each right super-game. These unarranged normal games are
regarded as the first part. The normal games between normal teams in each
super-team are regarded as the second part.

The first part. Since there are $r$ team-pairs $\\{R_{1},\dots,R_{r}\\}$, we
have $r$ kinds of right super-games. The right super-game including team-pair
$R_{i^{\prime}}$ is called the $i^{\prime}$-th right super-game. We use an
super-edge $(U_{i},U_{j})_{i^{\prime}}$ to denote an $i^{\prime}$-th right
super-game between super-teams $U_{i}$ and $U_{j}$. In our schedule, each
super-team has exactly two $i^{\prime}$-th right super-games. Hence, the
super-edges representing the $i^{\prime}$-th right super-games is a set of
cycles, denoted by $\mathcal{C}_{<i^{\prime}>}$. Whether there exists an
$i^{\prime}$-th right super-game between super-teams $U_{i}$ and $U_{j}$ is
due to their relative positions. It is easy to see that
$\mathcal{C}_{<i^{\prime}>}$ is a cycle packing, i.e., each cycle in
$\mathcal{C}_{<i^{\prime}>}$ has the same length. Note that there are $m-1$
super-teams in $\mathcal{C}_{<i^{\prime}>}$. Then, the length of each cycle in
$\mathcal{C}_{<i^{\prime}>}$ is $(m-1)/|\mathcal{C}_{<i^{\prime}>}|$, which is
odd since $m-1$ is odd. Hence, $\mathcal{C}_{<i^{\prime}>}$ is an odd cycle
packing. For example, when $m=10$ and $r=2$ as shown in Figure 1,
$\mathcal{C}_{<1>}$ contains one (odd) cycle
$(U_{1},U_{2},\dots,U_{9},U_{1})_{1}$, and $\mathcal{C}_{<2>}$ contains three
(odd) cycles $(U_{1},U_{4},U_{7},U_{1})_{2}$, $(U_{2},U_{5},U_{8},U_{2})_{2}$
and $(U_{3},U_{6},U_{9},U_{3})_{2}$.

Then, we analyze the unarranged normal games in the $i^{\prime}$-right super-
games. Take an arbitrary odd cycle in $\mathcal{C}_{<i^{\prime}>}$, denoted by
$C=(U_{i^{\prime}_{1}},U_{i^{\prime}_{2}},\dots,U_{i^{\prime}_{p}},U_{i^{\prime}_{1}})_{i^{\prime}}$,
where $p$ is odd. Let
$U_{i^{\prime}_{i}}=\\{x^{i}_{1},\dots,x^{i}_{k}\\}\cup\\{x^{i}_{k+1},\dots,x^{i}_{2k}\\}$.
Assume that there is an $i^{\prime}$-th right super-game between super-teams
$U_{i^{\prime}_{i}}$ and $U_{i^{\prime}_{j}}$, and let the team-pair
$R_{i^{\prime}}=\\{x^{i}_{2k+1},x^{j}_{2k+1}\\}$. By the design of right
super-games, the unarranged normal games are
$p_{2k+1}\cup\overline{p_{2k+1}}=\\{x^{i}_{i^{\prime\prime}}\leftrightarrow
x^{j}_{(2k-i^{\prime\prime})\bmod(2k+1)+1}\\}_{i^{\prime\prime}=1}^{2k}\cup\\{x^{i}_{2k+1}\leftrightarrow
x^{j}_{2k+1}\\}$. Note that the normal games $\\{x^{i}_{2k+1}\leftrightarrow
x^{j}_{2k+1}\\}$ between normal teams in team-pair $R_{i^{\prime}}$ have been
arranged when we consider the super-team $U_{m}$ and the $r$ team-pairs in
Case 1. Hence, we need to arrange the normal games
$\\{x^{i}_{i^{\prime\prime}}\leftrightarrow
x^{j}_{(2k-i^{\prime\prime})\bmod(2k+1)+1}\\}_{i^{\prime\prime}=1}^{2k}$. An
example of these unarranged normal games for $k=3$ is shown in Figure 4.

Figure 4: The unarranged normal games between super-teams
$U_{i}=\\{x^{i}_{1},x^{i}_{2},x^{i}_{3}\\}\cup\\{x^{i}_{4},x^{i}_{5},x^{i}_{6}\\}$,
$U_{j}=\\{x^{j}_{1},x^{j}_{2},x^{j}_{3}\\}\cup\\{x^{j}_{4},x^{j}_{5},x^{j}_{6}\\}$

We can see that the structure has a symmetric property. In the following, we
only consider two normal teams $\\{x^{i}_{1},x^{i}_{2k}\\}$ for each super-
team $U_{i^{\prime}_{i}}$. The unarranged normal games on the cycle
$C=(U_{i^{\prime}_{1}},U_{i^{\prime}_{2}},\dots,U_{i^{\prime}_{p}},U_{i^{\prime}_{1}})_{i^{\prime}}$
can be presented by a bi-directed cycle

$x^{1}_{0}\leftrightarrow x^{2}_{2k}\leftrightarrow
x^{3}_{0}\cdots\leftrightarrow x^{p}_{0}\leftrightarrow
x^{1}_{2k}\leftrightarrow x^{2}_{0}\leftrightarrow x^{3}_{2k}\cdots
x^{p}_{2k}\leftrightarrow x^{1}_{0}.$

An example of these $4p$ unarranged normal games for $k=3$ and $p=9$ is shown
in Figure 5.

Figure 5: The unarranged normal games on the cycle
$C=(U_{i^{\prime}_{1}},U_{i^{\prime}_{2}},\dots,U_{i^{\prime}_{p}},U_{i^{\prime}_{1}})_{i^{\prime}}$,
where we only consider two normal teams $\\{x^{i}_{1},x^{i}_{2k}\\}$ for each
super-team $U_{i^{\prime}_{i}}$, $p=9$, and $k=3$

Let $s_{1}$ and $s_{2}$ be the $p$ normal games $\\{x^{i}_{1}\rightarrow
x^{(i+p)\bmod p+1}_{2k}\\}_{i=1}^{i=p}$ and $\\{x^{i}_{2k}\rightarrow
x^{(i+p)\bmod p+1}_{1}\\}_{i=1}^{i=p}$, respectively. Then, the $4p$
unarranged normal games can be arranged as $(s_{1}\cdot
s_{2})\cdot(\overline{s_{1}\cdot s_{2}})$. An example of the $p$ normal games
of $s_{1}$ and $s_{2}$ for $k=3$ and $p=9$ is shown in Figure 6. Note that we
can design the unarranged normal games over the cycles in
$\mathcal{C}_{<i^{\prime}>}$ simultaneously. Moreover, all normal teams in
$U_{1}\cup U_{2}\cup\cdots U_{m-1}$ play $AHHA$ or $HAAH$.

Figure 6: The unarranged normal games on the cycle
$C=(U_{i^{\prime}_{1}},U_{i^{\prime}_{2}},\dots,U_{i^{\prime}_{p}},U_{i^{\prime}_{1}})_{i^{\prime}}$,
where we only consider two normal teams $\\{x^{i}_{1},x^{i}_{2k}\\}$ for each
super-team $U_{i^{\prime}_{i}}$, $p=9$, and $k=3$

Since there are $r$ kinds of right super-games, we can design the unarranged
normal games related to the cycle packing $\mathcal{C}_{<i^{\prime}>}$,
respectively, and hence the unarranged normal games in the first part need to
span $4r$ days. Recall that all normal teams play $HA$ or $AH$ on the last two
days of the super-games in the last time slot. Putting the first part behind
the super-games will not create more than three consecutive home/away normal
games.

The second part. Recall that the second part contains the normal games between
normal teams in each super-team $U_{i}$ ($i<m$). For each super-team $U_{i}$,
there are $2k$ (even) normal teams, and the unarranged normal games form a
double round robin for them. Similarly, we can call an algorithm of TTP-2 to
arrange a double round-robin for them. The second part spans $4k-2$ days.

For normal teams in $U_{1}\cup U_{2}\cup\cdots U_{m-1}$, the normal games in
these two parts span $4k+4r-2$ days, which is exactly the number of remaining
days. Note that all normal teams in $U_{1}\cup U_{2}\cup\cdots U_{m-1}$ play
$AH$ or $HA$ on the last two days of the first part. Hence, putting the TTP-2
double round-robins behind the first part will not create more than three
consecutive home/away normal games.

Note that there are at most $k$-consecutive home/away normal games in the
super-games of the last time slot. Putting the unarranged normal games behind
the super-games will not create more than three consecutive home/away normal
games.

######  Theorem 22.

For TTP-$k$ with any $k\geq 3$, when $n\geq 8k^{2}$, the $k$-cycle packing
construction can generate a feasible schedule.

###### Proof.

First, we show that our schedule is a complete double round-robin.

We use $(X,Y)$ to denote the normal games between normal teams in $X$ and
normal teams in $Y$, and $(X)$ to denote the normal games between normal teams
in $X$, where $X,Y\subseteq\\{t_{1},\dots,t_{n}\\}$ and $X\cap Y=\emptyset$.
For each team-pair $R_{i^{\prime}}$, it plays two right super-games with each
super-team $U_{i}\in\\{U_{1},\dots,U_{m-1}\\}$. Then, the normal games
$(R_{i^{\prime}},U_{i})$ are arranged. For super-teams $U_{i}$ and $U_{j}$,
there is a normal/left/right super-game between them, and then the normal
games $(U_{i},U_{j})$ are arranged (for the right super-game, the two days of
unarranged normal games are designed in Case 2). The normal games
$(R_{1}\cup\cdots R_{r}\cup U_{m})$ are arranged in Case 1. Hence, the
schedule is complete.

Next, we show that the no-repeat property holds.

It is easy to see that the two normal games between any pair of normal teams
are designed in a super-game or a TTP-2 double round-robin (see Case 1 and the
second part in Case 2) or the first part in Case 2. By the design of super-
games and the first part in Case 2, it is easy to see that there are no-repeat
normal games. For a TTP-2 double round-robin, it is clear that the normal
games satisfy the no-repeat property. So, the no-repeat property holds.

Then, we prove the bounded-by-$k$ property.

Recall that putting the unarranged normal games behind the super-games in the
last time slot will not create more than three consecutive home/away normal
games. Hence, we can assume that the schedule in the last time slot only
contains the $m/2$ super-games. For super-team $U_{m}$, it plays away and home
left super-games alternatively. For super-team $U_{i}$ ($i<m$), it always play
away (resp., home) normal/right super-games until it plays the first away
(resp., a home) left super-game. After playing the first away (resp., home)
left super-game, it will always play home (resp., away) normal/left/right
super-games. Note that a super-team can have at most two left super-games, and
the second left super-game must appear in the last time slot. For each team-
pair $R_{i^{\prime}}$, there are two normal teams
$\\{t_{n_{S}+2i^{\prime}-1},t_{n_{S}+2i^{\prime}}\\}$. In the right super-
games, the normal team $t_{n_{S}+2i^{\prime}-1}$ always belongs to the upper
super-team, while the normal team $t_{n_{S}+2i^{\prime}}$ always belongs to
the lower super-team. Hence, both of them play home and away right super-games
alternatively. For the sake of presentation, we use $H^{l}$ (resp., $A^{l}$)
to denote $l$-consecutive home (resp., away) normal games. If a super-team
plays an away (resp., a home) normal super-game, we know that the normal teams
in it will play $A^{k}\cdot H^{k}\cdot A^{k}\cdot H^{k}$ (resp., $H^{k}\cdot
A^{k}\cdot H^{k}\cdot A^{k}$). If a super-team plays an away (resp., a home)
left super-game, we know that the normal teams in it will play $A^{k-1}\cdot
H^{k}\cdot A^{k}\cdot H^{k}\cdot A$ (resp., $H^{k-1}\cdot A^{k}\cdot
H^{k}\cdot A^{k}\cdot H$). If a super-team plays an away (resp., a home) right
super-game, we know that the normal teams in it will play $(A^{k-2}\cdot
H\cdot A\cdot H^{k-2}\cdot A\cdot H)\cdot(A^{k-2}\cdot H\cdot A\cdot
H^{k-2}\cdot A\cdot H)$ (resp., $(H^{k-2}\cdot A\cdot H\cdot A^{k-2}\cdot
H\cdot A)\cdot(H^{k-2}\cdot A\cdot H\cdot A^{k-2}\cdot H\cdot A)$). We can see
that there are no more than $k$-consecutive home/away normal games. ∎

####  4.2.2 Analyzing the quality of the construction

Recall the three complete graphs $H=(S,E_{H})$,
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, and
$\mathcal{H}=(\mathcal{U},\mathcal{F})$, where $S=\\{t_{1},\dots,t_{n_{S}}\\}$
representing the $n_{S}$ normal teams, $\mathcal{V}=\\{u_{1},\dots,u_{2m}\\}$
representing the $2m$ cycle-teams, and $\mathcal{U}=\\{U_{1},\dots,U_{m}\\}$
representing the $m$ super-teams.

Given a $k$-cycle packing $\mathcal{C}_{k}=\\{C_{1},\dots,C_{2m}\\}$, where
the indies are arbitrarily labeled. The construction can generate a feasible
solution, but it may not be good enough. Hence, to get a schedule with a small
total traveling distance, we need to find a good way to label the cycles. To
do this, we use the random method: cycles are labeled using
$\\{C_{1},\dots,C_{2m}\\}$ uniformly at random. Note that the
$n_{\overline{S}}$ normal teams in $\overline{S}$ are still divided into $r$
team-pairs arbitrarily. We will calculate the expected weight of our schedule.

Note that $\mathcal{E}$ contains $\frac{2m(2m-1)}{2}$ edges, where
$\frac{2m(2m-1)}{2}\geq m^{2}$ since $m=2\lfloor\frac{n}{4k}\rfloor>1$. For an
edge $(u_{i},u_{j})\in\mathcal{E}$, by (4), we have that

$\mathbb{E}[w(u_{i},u_{j})]=\frac{2}{2m(2m-1)}w(\mathcal{E})\leq\frac{1}{m^{2}}w(\mathcal{E})=\frac{1}{2m^{2}}\Delta_{H}.$
(9)

Recall that $w(U_{i},U_{j})=\sum_{u_{i^{\prime}}\in U_{i}\&u_{j^{\prime}}\in
U_{j}}w(u_{i^{\prime}},u_{j^{\prime}})$ for $i\neq j$. For an edge
$(U_{i},U_{j})\in\mathcal{F}$, we have that

$\mathbb{E}[w(U_{i},U_{j})]=\sum_{u_{i^{\prime}}\in U_{i}\&u_{j^{\prime}}\in
U_{j}}\mathbb{E}[w(u_{i^{\prime}},u_{j^{\prime}})]\leq\sum_{u_{i^{\prime}}\in
U_{i}\&u_{j^{\prime}}\in
U_{j}}\frac{1}{2m^{2}}\Delta_{H}=\frac{2}{m^{2}}\Delta_{H}.$ (10)

######  Lemma 23.

Assume that there is a normal cycle-game between cycle-teams $u_{i}$ and
$u_{j}$. There is an $O(k^{2})$-time algorithm ensuring that the total weight
of all normal games in the cycle game is at most
$(4/k)w(u_{i},u_{j})+(k-1)(w(C_{i})+w(C_{j}))$.

###### Proof.

Assume w.l.o.g. that the normal cycle-game is at the home of $u_{j}$. By the
design of normal cycle-games, all normal teams in $u_{i}$ (resp., $u_{j}$)
play $A^{k}\cdot H^{k}$ (resp., $H^{k}\cdot A^{k}$). Hence, each normal team
in $u_{i}\cup u_{j}$ has exactly one road trip visiting $k$ normal teams.
Recall that $u_{i}=\\{t_{k(i-1)+1},\dots,t_{k(i-1)+k}\\}$ and
$u_{j}=\\{t_{k(j-1)+1},\dots,t_{k(j-1)+k}\\}$. For the sake of presentation,
we let $t_{k(i-1)+i^{\prime}}=x_{i^{\prime}}$ and
$t_{k(j-1)+i^{\prime}}=y_{i^{\prime}}$, i.e., $u_{i}=\\{x_{1},\dots,x_{k}\\}$
and $u_{j}=\\{y_{1},\dots,y_{k}\\}$. By the design of normal cycle-games, the
weight of these $2k$ road trips are

$\displaystyle\sum_{i^{\prime}=1}^{k}(w(x_{i^{\prime}},y_{i^{\prime}})+w(x_{i^{\prime}},y_{(i^{\prime}+k-2)\bmod
k+1}))+(k-1)(w(C_{i})+w(C_{j})).$

Before extending the normal cycle-game into normal games, we may change the
labels of normal teams in the $k$-cycle $C_{j}$ by setting
$y^{l}_{i^{\prime}}=y_{(i^{\prime}+l-2)\bmod k+1}$, where
$l\in\\{1,2,\dots,k\\}$. Note that after extending the normal cycle-game, we
can recover the previous labels of normal teams in $C_{j}$, which does not
effect the feasibility of teams since all normal teams in $u_{i}$ (resp.,
$u_{j}$) play $A^{k}\cdot H^{k}$ (resp., $H^{k}\cdot A^{k}$). Note that

$\displaystyle\sum_{l=1}^{k}\sum_{i^{\prime}=1}^{k}(w(x_{i^{\prime}},y^{l}_{i^{\prime}})+w(x_{i^{\prime}},y^{l}_{(i^{\prime}+k-2)\bmod
k+1}))=2w(u_{i},u_{j}).$

Hence, for all $k$ cases of $l$, there must be one case $l=l_{0}$ such that

$\sum_{i^{\prime}=1}^{k}(w(x_{i^{\prime}},y^{l_{0}}_{i^{\prime}})+w(x_{i^{\prime}},y^{l_{0}}_{(i^{\prime}+k-2)\bmod
k+1}))\leq(4/k)w(u_{i},u_{j}).$

The best label of the $k$ cases can be found in $O(k^{2})$ time. ∎

Note that the algorithm in Lemma 23 runs in constant time if $k=O(1)$.

Next, we are ready to analyze the total weight of schedule. For the sake of
analysis, we make the following assumption.

######  Assumption 24.

We assume that all normal teams return home before and after every normal game
in left/right super-games and the unarranged normal games in the last time
slot.

We will consider the following five parts of our schedule:

  * •

$W_{a}$: the weight of normal games involving normal teams in $R_{1}\cup\cdots
R_{r}$;

  * •

$W_{b}$: the weight of normal games between normal teams in each super-team of
$\\{U_{1},\dots,U_{m}\\}$;

  * •

$W_{c}$: the weight of normal games in left super-games;

  * •

$W_{d}$: the weight of the rest normal games in right super-games with the
unarranged normal games in each right super-game;

  * •

$W_{e}$: the weight of normal games in normal super-games.

Case 1: $W_{a}$. The normal games appear in right super-games and Case 1 of
the unarranged normal games. Recall that $R_{1}\cup\cdots R_{r}=\overline{S}$.
By Assumption 24, the weight of normal games involving the normal team
$v\in\overline{S}$ is $4\deg_{G}(v)$. Thus, we have that

$\mathbb{E}[W_{a}]=W_{a}\leq\sum_{v\in\overline{S}}4\deg_{G}(v)\leq(16k/n)\Delta_{G}\leq(8k^{2}/n)\psi,$
(11)

where the second inequality follows from (3) and the last follows from Lemma
13.

Case 2: $W_{b}$. The normal games appear in the second part of Case 2 of the
unarranged normal games. By Assumption 24, the weight of normal games between
normal teams in super-team $U_{i}\in\mathcal{U}$ is $4w(U_{i})$. Recall that
$U_{i}=u_{2i-1}\cup u_{2i}$. By the definition,
$w(U_{i})=w(u_{2i-1})+w(u_{2i})+w(u_{2i-1},u_{2i})$. By the triangle
inequality, we have $w(u_{2i-1})\leq w(u_{2i-1},u_{2i})$ and $w(u_{2i})\leq
w(u_{2i-1},u_{2i})$. Hence, we have $w(U_{i})\leq 3w(u_{2i-1},u_{2i})$. Thus,
we have that

$\mathbb{E}[W_{b}]=\sum_{U_{i}\in\mathcal{U}}4\mathbb{E}[w(U_{i})]\leq\sum_{U_{i}\in\mathcal{U}}12\mathbb{E}[w(u_{2i-1},u_{2i})]\leq(6/m)\Delta_{H}\leq(12k^{2}/n)\psi,$
(12)

where the third inequality follows from (9), and the last follows from
$m=2\lfloor\frac{n}{4k}\rfloor>2(\frac{n}{4k}-1)\geq\frac{n}{4k}$ (since
$n\geq 8k^{2}$) and Lemma 12.

Case 3: $W_{c}$. The normal games appear in left super-games. Assume that
there is a left super-game between super-teams $U_{i}$ and $U_{j}$. By
Assumption 24, the weight of normal games in the left super-game is
$4w(U_{i},U_{j})$. By (10), the expected weight is
$4w(U_{i},U_{j})=(8/m^{2})\Delta_{H}$. There are $(m-2)+(m/2-r)\leq(3/2)m$
left super-games in our schedule. Thus, we have that

$\mathbb{E}[W_{c}]\leq(12/m)\Delta_{H}=(24k^{2}/n)\psi.$ (13)

Case 4: $W_{d}$. The normal games appear in right super-games and the first
part of Case 1. There should be a team-pair. Note that the weight of normal
games related to the team-pair has been analyzed in $W_{a}$. We only consider
the rest normal games. Assume that there is a right super-game between super-
teams $U_{i}$ and $U_{j}$. By Assumption 24, the weight of the normal games in
the right super-game with the unarranged normal games is $4w(U_{i},U_{j})$.
The expected weight is $(8/m^{2})\Delta_{H}$. There are $(m-1)r\leq mr\leq
2mk$ right super-games in our schedule since $r<2k$ by our setting. Thus, we
have that

$\mathbb{E}[W_{d}]\leq(16k/m)\Delta_{H}=(32k^{3}/n)\psi.$ (14)

Case 5: $W_{e}$. Assume that there is a normal super-game between super-teams
$U_{i}$ and $U_{j}$. There are four normal cycle-games. By Lemma 23, the total
weight of these four normal cycle-games are $\sum_{u_{i^{\prime}}\in
U_{i}\&u_{j^{\prime}}\in
U_{j}}(\frac{4}{k}w(u_{i^{\prime}},u_{j^{\prime}}))+(k-1)(w(C_{i^{\prime}})+w(C_{j^{\prime}}))$.
It is easy to see that
$\mathbb{E}[w(C_{i^{\prime}})]=\mathbb{E}[w(C_{j^{\prime}})]=\frac{1}{2m}w(\mathcal{C}_{k})$.
By (9) and $(\ref{eqn_GH})$, we have that
$\mathbb{E}[w(u_{i},u_{j})]=\frac{2}{2m(2m-1)}w(\mathcal{E})\leq\frac{1}{2m(2m-1)}\Delta_{H}\leq\frac{1}{4m(m-1)}\Delta_{H}$.
Hence, the expected weight of the normal super-game is
$\frac{4}{m(m-1)k}\Delta_{H}+\frac{4(k-1)}{m}w(\mathcal{C}_{k})$. Note that
there are at most $m(m-1)/2$ normal super-games since there are $m$ super-
teams and there is exactly one super-game between each pair super-team. The
total expected weight of all normal super-games are
$\frac{2}{k}\Delta_{H}+2(k-1)(m-1)w(\mathcal{C}_{k})\leq\frac{2}{k}\Delta_{H}+2(k-1)mw(\mathcal{C}_{k})$.
Since $n_{S}=2mk$, we have that

$\mathbb{E}[W_{e}]\leq(2/k)\Delta_{H}+(1-1/k)n_{S}w(\mathcal{C}_{k}).$ (15)

Thus, the expected weight of our schedule is bounded by

$(2/k)\Delta_{H}+(1-1/k)n_{S}w(\mathcal{C}_{k})+(44k^{2}/n)\psi+(32k^{3}/n)\psi.$

Recall that our schedule requires $n\geq 8k^{2}$. If $n\leq 8k^{2}=O(1)$, we
can find an optimal solution by brute force, which takes constant time. Hence,
we can get the following theorem.

######  Theorem 25.

Let $\mathcal{C}_{k}$ be a $k$-cycle packing in graph $H$. For TTP-$k$ with
any constant $k\geq 3$, there is a randomized polynomial-time algorithm that
can generate a solution with a total weight of at most
$\frac{k-1}{k}n_{S}w(\mathcal{C}_{k})+\frac{2}{k}\Delta_{H}+O(k^{3}/n)\psi$.

Given a $k$-path packing $\mathcal{P}_{k}$ in graph, we can obtain a $k$-cycle
packing $\mathcal{C}_{k}$ by completing the $k$-paths in the packing, such
that $w(\mathcal{C}_{k})\leq 2w(\mathcal{P}_{k})$ by the triangle inequality.
By Theorem 25, we can use this packing $\mathcal{C}_{k}$ to get a solution of
TTP-$k$. Hence, we can get the following corollary.

######  Corollary 26.

Let $\mathcal{P}_{k}$ be a $k$-path packing in graph $H$. For TTP-$k$ with any
constant $k\geq 3$, there is a randomized polynomial-time algorithm that can
generate a solution with a total weight of at most
$\frac{2k-2}{k}n_{S}w(\mathcal{P}_{k})+\frac{2}{k}\Delta_{H}+O(k^{3}/n)\psi$.

Our algorithm is randomized since we label the $2m$ cycle-teams by
$\\{C_{1},\dots,C_{2m}\\}$ randomly. It can be derandomized efficiently by the
classic method of conditional expectations [33].

Next, we give a brief introduction to the derandomization.

According to the previous analysis, it is easy to see that there is an upper
bound of the weight of our schedule, denoted by $W$, such that it is a linear
function on variables $w(u_{i},u_{j})$ and $w(C_{i})$ for $1\leq i,j\leq 2m$.
In Theorem 25, we have proved that
$\mathbb{E}[W]\leq\frac{k-1}{k}n_{S}w(\mathcal{C}_{k})+\frac{2}{k}\Delta_{H}+O(k^{3}/n)\psi$.
Recall that the algorithm takes a $k$-cycle packing $\mathcal{C}_{k}$ as a
part of the input, where $|\mathcal{C}_{k}|=2m$. Let the $2m$ cycle teams be
$\\{C^{*}_{1},\dots,C^{*}_{2m}\\}$. The main idea is to find a permutation
$\sigma:(1,2,\dots,2m)\leftrightarrow(\sigma_{1},\sigma_{2},\dots,\sigma_{2m})$
such that

$\mathbb{E}[W|C_{1}=C^{*}_{\sigma_{1}},\dots,C_{2m}=C^{*}_{\sigma_{2m}}]\leq\mathbb{E}[W].$

We can determine each $\sigma_{i}$ sequentially. Assume that we have
determined $(\sigma_{1},\dots,\sigma_{s-1})$ such that

$\mathbb{E}[W|C_{1}=C^{*}_{\sigma_{1}},\dots,C_{s-1}=C^{*}_{\sigma_{s-1}}]\leq\mathbb{E}[W].$

To determine $\sigma_{s}$, we can simply let $\sigma_{s}$ be

$\sigma_{s}=\arg\min_{\sigma_{s}\in\\{1,2,\dots,2m\\}\setminus\\{\sigma_{1},\sigma_{2},\dots,\sigma_{s-1}\\}}\mathbb{E}[W|C_{1}=C^{*}_{\sigma_{1}},\dots,C_{s}=C^{*}_{\sigma_{s}}]\leq\mathbb{E}[W].$
(16)

Then, we can get

$\mathbb{E}[W|C_{1}=C^{*}_{\sigma_{1}},\dots,C_{s}=C^{*}_{\sigma_{s}}]\leq\mathbb{E}[W|C_{1}=C^{*}_{\sigma_{1}},\dots,C_{s-1}=C^{*}_{\sigma_{s-1}}]\leq\mathbb{E}[W].$
(17)

Therefore, we can repeat this procedure to determine the permutation $\sigma$.

Now, we consider the running time. We need to determine $2m$ labels
respectively. For each label, we need to compute the expected conditional
weight of $W$ at most $2m$ times. Hence, we need to compute the expected
conditional weight of $W$ at most $4m^{2}=O(n^{2})$ times. To compute the
expected conditional weight of $W$, we need to first compute the expected
conditional weight of each variable. There are
$\frac{2m(2m-1)}{2}+2m=2m^{2}+m=O(n^{2})$ variables. It is easy to see that
the expected conditional weight of each variable can be computed in $O(n^{2})$
time, and hence the expected conditional weight of $W$ can be computed in
$O(n^{4})$ time. Therefore, the derandomization takes $O(n^{6})$ extra time.

Next, we are ready to analyze the approximation qualities of these two
constructions. We will consider TTP-3, TTP-4, TTP-$k$ with $k\geq 5$, and
LDTTP-$k$ with $k\geq 3$, respectively.

##  5 The Approximation Ratio of TTP-$k$

###  5.1 TTP-3

####  5.1.1 The Approximation Quality of the Hamiltonian Cycle Construction

Note that the Hamiltonian cycle they used is generated by the Christofides-
Serdyukov algorithm. In our algorithm, we also consider another Hamiltonian
cycle that uses the minimum weight perfect matching. For TTP-3, we will select
the better one between these two cycles.

######  Lemma 27.

Let $M_{H}$ be a perfect matching in graph $H$. There is a polynomial-time
algorithm that can generate a Hamiltonian cycle $C_{H}$ in $H$ with a weight
of at most $w(M_{H})+\frac{1}{2n_{S}}\Delta_{H}+O(1/n^{2}_{S})\Delta_{H}$.

###### Proof.

The perfect matching $M_{H}$ contains $n_{S}/2$ edges. We can list the edges
of $M_{H}$ in a random way, and connect them from first to last to form a
Hamiltonian cycle $C_{H}$ in graph $H$, respectively. For example, suppose
$n_{S}=4$, the listed two edges (in a random way) are denoted by
$(v_{1},v_{2})$ and $(v_{3},v_{4})$, and then we can construct a Hamiltonian
cycle $(v_{1},v_{2},v_{3},v_{4},v_{1})$.

Recall that the edge set of graph $H$ is denoted by $E_{H}$. There are
$n_{S}/2$ newly added edges, belonging to the edge set $E_{H}\setminus M_{H}$.
Every edge in the set is selected with the same probability
$\frac{1}{|E_{H}\setminus M_{H}|}=\frac{2}{n_{S}(n_{S}-2)}$. The expected
weight of newly added edges is
$(\frac{n_{S}}{2})\cdot\frac{2}{n_{S}(n_{S}-2)}w(E_{H}\setminus
M_{H})\leq\frac{1}{2(n_{S}-2)}\Delta_{H}=\frac{1}{2n_{S}}\Delta_{H}+\frac{1}{n_{S}(n_{S}-2)}\Delta_{H}\leq\frac{1}{2n_{S}}\Delta_{H}+\frac{2}{n^{2}_{S}}\Delta_{H}$,
where the first inequality follows from $w(E_{H}\setminus M_{H})\leq
w(E_{H})=\frac{1}{2}\Delta_{H}$ by (4), and the second follows from
$n_{S}=n-n_{\overline{S}}\geq 8k^{2}-4k>4$. Hence, the Hamiltonian cycle
$C_{H}$ has an expected weight of at most

$w(M_{H})+\frac{1}{2n_{S}}\Delta_{H}+\frac{2}{n^{2}_{S}}\Delta_{H}=w(M_{H})+\frac{1}{2n_{S}}\Delta_{H}+O(1/n^{2}_{S})\Delta_{H}.$

The randomized algorithm runs in $O(n^{3})$ time. Again, it can be
derandomized efficiently by the method of conditional expectations [33]. ∎

Note that Lemma 27 holds for any perfect matching. For TTP-3, we consider the
Hamiltonian cycle using a minimum weight perfect matching. By making a trade-
off between the two Hamiltonian cycles, we can get the following theorem.

######  Theorem 28.

For TTP-3 with any constant $\varepsilon>0$, there is a polynomial-time
algorithm with an approximation ratio of
$\min\\{\frac{4}{3}+\frac{1}{3}\alpha\gamma,\
1-\frac{1}{6}\gamma+\alpha\gamma\\}+\varepsilon$.

###### Proof.

Here we use $C_{H}$ to denote a minimum weight Hamiltonian cycle in graph $H$.
If we use the Hamiltonian cycle $C^{\prime}_{H}$ obtained by the Christofides-
Serdyukov algorithm, we can construct a feasible schedule with a total weight
of at most
$\frac{2}{3}n_{S}w(C^{\prime}_{H})+\frac{2}{3}\Delta_{H}+O(1/n)\psi$ by Lemma
21, since
$n_{S}w(C^{\prime}_{H})\leq\frac{3}{2}n_{S}w(C_{H})\leq\frac{3}{2}\psi=O(1)\psi$
(recall that the Christofides-Serdyukov algorithm is a $3/2$-approximation
algorithm for TSP). Then, we have that

$\displaystyle\frac{2}{3}n_{S}w(C^{\prime}_{H})+\frac{2}{3}\Delta_{H}+O(1/n)\psi$
$\displaystyle\leq\frac{2}{3}n_{S}\left(\mbox{MST}(H)+\frac{1}{2}w(C_{H})\right)+\frac{2}{3}\Delta_{H}+O(1/n)\psi$
$\displaystyle=\frac{2}{3}\left(n_{S}\mbox{MST}(H)+\frac{1}{2}\Delta_{H}\right)+\frac{1}{3}\Delta_{H}+\frac{1}{3}n_{S}w(C_{H})+O(1/n)\psi$
$\displaystyle\leq\frac{2}{3}\left(1+\frac{1}{4}\gamma\right)\psi+\frac{1}{3}\left(1-\frac{1}{2}\gamma+\alpha\gamma\right)\psi+\frac{1}{3}\psi+O(1/n)\psi$
$\displaystyle=\left(\frac{4}{3}+\frac{1}{3}\alpha\gamma\right)\psi+O(1/n)\psi,$

where the first inequality follows from Lemma 3, and the second follows from
Lemmas 11, 12, and (6).

Similarly, if we use a minimum weight perfect matching $M_{H}$ in graph $H$ to
obtain the Hamiltonian cycle $C^{\prime\prime}_{H}$ in Lemma 27, we can
construct a feasible schedule with a total weight of at most
$\frac{2}{3}n_{S}w(C^{\prime\prime}_{H})+\frac{2}{3}\Delta_{H}+O(1/n)\psi$,
since $n_{S}w(C^{\prime\prime}_{H})\leq
n_{S}(w(M_{H})+\frac{1}{2n_{S}}\Delta_{H}+O(1/n^{2}_{S})\Delta_{H})=n_{S}w(M_{H})+O(1)\Delta_{H}=O(1)\psi$
by Lemmas 12, 15 and 27. Then, we have that

$\displaystyle\frac{2}{3}nw(C^{\prime\prime}_{H})+\frac{2}{3}\Delta_{H}+O(1/n)\psi$
$\displaystyle\leq\frac{2}{3}n_{S}\left(w(M_{H})+\frac{1}{2n_{S}}\Delta_{H}+O(1/n^{2}_{S})\Delta_{H}\right)+\frac{2}{3}\Delta_{H}+O(1/n)\psi$
$\displaystyle\leq\frac{2}{3}(n_{S}w(M)+\Delta_{H})+\frac{1}{3}\Delta_{H}+O(1/n)\psi$
$\displaystyle\leq\frac{2}{3}(1+\alpha\gamma)\psi+\frac{1}{3}\left(1-\frac{1}{2}\gamma+\alpha\gamma\right)\psi+O(1/n)\psi$
$\displaystyle=\left(1-\frac{1}{6}\gamma+\alpha\gamma\right)\psi+O(1/n)\psi,$

where the first inequality follows from Lemma 27, the second follows from
Lemma 13, and the last follows from Lemma 12 and (7).

Since we select the better one between these two Hamiltonian cycles, the
approximation ratio is $\min\\{\frac{4}{3}+\frac{1}{3}\alpha\gamma,\
1-\frac{1}{6}\gamma+\alpha\gamma\\}+O(1/n)$. Hence, there exists a constant
$c$ such that the ratio is bounded by
$\min\\{\frac{4}{3}+\frac{1}{3}\alpha\gamma,\
1-\frac{1}{6}\gamma+\alpha\gamma\\}+c/n$. For any constant $\varepsilon>0$, if
$n\leq c/\varepsilon=O(1)$, we can find an optimal solution by brute force,
otherwise we use the approximation algorithm. This establishes the
approximation ratio of $\min\\{\frac{4}{3}+\frac{1}{3}\alpha\gamma,\
1-\frac{1}{6}\gamma+\alpha\gamma\\}+\varepsilon$. ∎

Note that $\max_{0\leq\alpha,\gamma\leq
1}\min\\{\frac{4}{3}+\frac{1}{3}\alpha\gamma,\
1-\frac{1}{6}\gamma+\alpha\gamma\\}+\varepsilon$ is maximized when
$\alpha=\gamma=1$ with value $(5/3+\varepsilon)$. However, this would require
$0=(\frac{2}{3}+\frac{1}{3}\gamma-\alpha\gamma)\psi\geq
nw(\mathcal{P}^{*}_{3})\geq\frac{1}{2}nw(\mathcal{C}^{*}_{3})$ by Lemma 16. If
we use any constant ratio approximation algorithm for minimum weight 3-path
packing or 3-cycle packing, we may get a much better schedule based on them.
Therefore, we will show that we can do better than $(5/3+\varepsilon)$ by
combining the Hamiltonian cycle construction with the 3-cycle packing
construction shown next.

####  5.1.2 The Approximation Quality of the 3-Cycle Packing Construction

######  Theorem 29.

For TTP-3 with any constant $\varepsilon>0$, if there exist $\rho_{c}$ and
$\rho_{p}$ approximation algorithms for minimum $3$-cycle and 3-path packing
problems respectively, there is a polynomial-time algorithm with an
approximation ratio of
$(\frac{8\rho+6}{9}+\frac{4\rho-3}{9}\gamma-\frac{4\rho-2}{3}\alpha\gamma+\varepsilon)$,
where $\rho=\min\\{\rho_{c},\rho_{p}\\}$.

###### Proof.

First, we consider that the schedule uses a $\rho_{c}$-approximation 3-cycle
packing $\mathcal{C}_{3}$ in graph $H$. By Theorem 25, we can get a schedule
with a weight of at most

$\displaystyle\frac{2}{3}\rho_{c}n_{S}w(\mathcal{C}^{*}_{3})+\frac{2}{3}\Delta_{H}+O(1/n)\psi$
$\displaystyle\leq\frac{4}{3}\rho_{c}n_{S}w(\mathcal{P}^{*}_{3})+\frac{2}{3}\Delta_{H}+O(1/n)\psi$
$\displaystyle\leq\frac{4}{3}\rho_{c}\left(\frac{2}{3}+\frac{1}{3}\gamma-\alpha\gamma\right)\psi+\frac{2}{3}\left(1-\frac{1}{2}\gamma+\alpha\gamma\right)\psi+O(1/n)\psi$
$\displaystyle=\left(\frac{8\rho_{c}+6}{9}+\frac{4\rho_{c}-3}{9}\gamma-\frac{4\rho_{c}-2}{3}\alpha\gamma\right)\psi+O(1/n)\psi,$

where the first inequality follows from $w(\mathcal{C}^{*}_{3})\leq
2w(\mathcal{P}^{*}_{3})$ by the triangle inequality, and the second follows
from Lemmas 12 and 16.

Then, we consider that the schedule uses a $\rho_{p}$-approximation 3-path
packing $\mathcal{P}_{3}$ in graph $H$. By Theorem 26, we can get a schedule
with a weight of at most

$\displaystyle\frac{4}{3}\rho_{p}n_{S}w(\mathcal{P}^{*}_{3})+\frac{2}{3}\Delta_{H}+O(1/n)\psi$
$\displaystyle\leq\frac{4}{3}\rho_{p}\left(\frac{2}{3}+\frac{1}{3}\gamma-\alpha\gamma\right)\psi+\frac{2}{3}\left(1-\frac{1}{2}\gamma+\alpha\gamma\right)\psi+O(1/n)\psi$
$\displaystyle=\left(\frac{8\rho_{p}+6}{9}+\frac{4\rho_{p}-3}{9}\gamma-\frac{4\rho_{p}-2}{3}\alpha\gamma\right)\psi+O(1/n)\psi,$

where the inequality follows from Lemmas 12 and 16.

By selecting the better one, we can get an approximation ratio of
$(\frac{8\rho+6}{9}+\frac{4\rho-3}{9}\gamma-\frac{4\rho-2}{3}\alpha\gamma+\varepsilon)$.
∎

####  5.1.3 Trade-off between Two Constructions

######  Theorem 30.

Given a polynomial-time $\rho_{c}$-approximation algorithm for the minimum
$3$-cycle packing problem, and a polynomial-time $\rho_{p}$-approximation
algorithm for the minimum $3$-path packing problem, let
$\rho=\min\\{\rho_{c},\rho_{p}\\}$. For TTP-3 with any constant
$\varepsilon>0$, there is a polynomial-time algorithm with an approximation
ratio of

$\left\\{\begin{aligned}
\frac{11}{6}-\frac{5}{2(4\rho+1)}+\varepsilon,\quad\mbox{if}\quad\rho\leq\frac{9}{4};\\\
\frac{5}{3}-\frac{2}{3(4\rho-1)}+\varepsilon,\quad\mbox{if}\quad\rho>\frac{9}{4}.\end{aligned}\right.$

###### Proof.

Our algorithm will select the better schedule from the previous two
constructions. By Theorem 28, the ratio of the Hamiltonian cycle construction
is $\min\\{\frac{4}{3}+\frac{1}{3}\alpha\gamma,\
1-\frac{1}{6}\gamma+\alpha\gamma\\}+\varepsilon$. By Theorem 29, the ratio of
the $k$-cycle packing construction is
$(\frac{8\rho+6}{9}+\frac{4\rho-3}{9}\gamma-\frac{4\rho-2}{3}\alpha\gamma+\varepsilon)$.
Therefore, the ratio of our algorithm in the worst case is

$\max_{0\leq\alpha,\gamma\leq
1}\min\left\\{\frac{4}{3}+\frac{1}{3}\alpha\gamma,\
1-\frac{1}{6}\gamma+\alpha\gamma,\
\frac{8\rho+6}{9}+\frac{4\rho-3}{9}\gamma-\frac{4\rho-2}{3}\alpha\gamma\right\\}+\varepsilon.$

We can transform it into the following LP, where we let
$\widetilde{\gamma}=\alpha\gamma$.

$\displaystyle\max\quad$ $\displaystyle y$ s.t. $\displaystyle
y\leq\frac{4}{3}+\frac{1}{3}\widetilde{\gamma},$ $\displaystyle y\leq
1-\frac{1}{6}\gamma+\widetilde{\gamma},$ $\displaystyle
y\leq\frac{8\rho+6}{9}+\frac{4\rho-3}{9}\gamma-\frac{4\rho-2}{3}\widetilde{\gamma},$
$\displaystyle 0\leq\widetilde{\gamma}\leq\gamma\leq 1.$

The LP shows that the ratio is $\frac{11}{6}-\frac{5}{2(4\rho+1)}+\varepsilon$
when $\rho\leq 9/4$, and $\frac{5}{3}-\frac{2}{3(4\rho-1)}+\varepsilon$
otherwise. ∎

There are polynomial-time $8/3$-approximation algorithms for both the minimum
3-cycle and 3-path packing problems [34]. Therefore, we have the following
result.

######  Corollary 31.

For any constant $\varepsilon>0$, there is a polynomial-time
$(139/87+\varepsilon)$-approximation algorithm for TTP-3.

######  Corollary 32.

For any constant $\varepsilon>0$, TTP-3 allows a polynomial-time
$(4/3+\varepsilon)$-approximation algorithm if a minimum 3-cycle or a minimum
3-path packing of $H$ is given.

###  5.2 TTP-4

It is natural to use the same idea to solve TTP-4. For the problem of minimum
4-path packing, to our best knowledge, the current best-known ratio is $3/2$
[35]. For the problem of minimum 4-cycle packing, there is a $3$-approximation
algorithm [34].

If we use the construction based on the Hamiltonian cycle and the construction
based on the 4-path packing, we can get a $(17/10+\varepsilon)$-approximation
algorithm for TTP-4, which improves the previous ratio $(7/4+\varepsilon)$
[11].

######  Theorem 33.

For TTP-4 with any constant $\varepsilon>0$, there is a polynomial-time
algorithm using the Hamiltonian cycle construction that can achieve an
approximation ratio of
$(\frac{3}{2}+\frac{1}{8}\gamma+\frac{1}{8}\alpha\gamma+\varepsilon)$.

###### Proof.

Here we use $C_{H}$ to denote a minimum weight Hamiltonian cycle in graph $H$.
If we use the Hamiltonian cycle $C^{\prime}_{H}$ obtained by the Christofides-
Serdyukov algorithm, we can construct a feasible schedule with a total weight
of at most
$\frac{3}{4}n_{S}w(C^{\prime}_{H})+\frac{1}{2}\Delta_{H}+O(1/n)\psi$ by Lemma
21, since
$n_{S}w(C^{\prime}_{H})\leq\frac{3}{2}n_{S}w(C_{H})\leq\frac{3}{2}\psi=O(1)\psi$
(recall that the Christofides-Serdyukov algorithm is a $3/2$-approximation
algorithm for TSP). Then, we have that

$\displaystyle\frac{3}{4}n_{S}w(C^{\prime}_{H})+\frac{1}{2}\Delta_{H}+O(1/n)\psi$
$\displaystyle\leq\frac{3}{4}n_{S}\left(\mbox{MST}(H)+\frac{1}{2}w(C_{H})\right)+\frac{1}{2}\Delta_{H}+O(1/n)\psi$
$\displaystyle=\frac{3}{4}\left(n_{S}\mbox{MST}(H)+\frac{1}{2}\Delta_{H}\right)+\frac{1}{8}\Delta_{H}+\frac{3}{8}n_{S}w(C_{H})+O(1/n)\psi$
$\displaystyle\leq\frac{3}{4}\left(\frac{5}{4}+\frac{1}{4}\gamma\right)\psi+\frac{1}{8}\left(\frac{3}{2}-\frac{1}{2}\gamma+\alpha\gamma\right)\psi+\frac{3}{8}\psi+O(1/n)\psi$
$\displaystyle=\left(\frac{3}{2}+\frac{1}{8}\gamma+\frac{1}{8}\alpha\gamma\right)\psi+O(1/n)\psi,$

where the first inequality follows from Lemma 3, and the second follows from
Lemmas 11, 12, and (6). Note that there is no need to use the Hamiltonian
cycle based on the minimum weight perfect matching. ∎

######  Theorem 34.

For TTP-4 with any constant $\varepsilon>0$, there is a polynomial-time
algorithm using the 4-path packing construction that can achieve an
approximation ratio of
$(\frac{39}{16}+\frac{5}{16}\gamma-\frac{7}{4}\alpha\gamma+\varepsilon)$.

###### Proof.

Using the $3/2$-approximation 4-path packing $\mathcal{P}_{4}$ in graph $H$,
by Corollary 26, we can get a schedule with a weight of at most
$\frac{9}{4}n_{S}w(\mathcal{P}^{*}_{4})+\frac{1}{2}\Delta_{H}+O(1/n)\psi$.
Then, we have that

$\displaystyle\frac{9}{4}n_{S}w(\mathcal{P}^{*}_{4})+\frac{1}{2}\Delta_{H}+O(1/n)\psi$
$\displaystyle\leq\frac{9}{4}\left(\frac{3}{4}+\frac{1}{4}\gamma-\alpha\gamma\right)\psi+\frac{1}{2}\left(\frac{3}{2}-\frac{1}{2}\gamma+\alpha\gamma\right)\psi+O(1/n)\psi$
$\displaystyle=\left(\frac{39}{16}+\frac{5}{16}\gamma-\frac{7}{4}\alpha\gamma\right)\psi+O(1/n)\psi,$

where the inequality follows from Lemmas 12 and 16. ∎

Making a trade-off between Theorems 33 and 34, we can get an approximation
ratio of

$\max_{0\leq\alpha,\gamma\leq
1}\min\left\\{\frac{3}{2}+\frac{1}{8}\gamma+\frac{1}{8}\alpha\gamma,\
\frac{39}{16}+\frac{5}{16}\gamma-\frac{7}{4}\alpha\gamma\right\\}+\varepsilon=\frac{17}{10}+\varepsilon.$

Hence, we have the following theorem.

######  Theorem 35.

For any contant $\varepsilon>0$, there is a polynomial-time
$(17/10+\varepsilon)$-approximation algorithm for TTP-4.

###  5.3 TTP-$k$ with $k\geq 5$

For TTP-$k$ with $k\geq 5$, we note that both of the best-known approximation
ratios for minimum $k$-cycle and $k$-path packing problems are $4(1-1/k)>3$
[34]. The approximation ratios are too big and we cannot improve TTP-$k$ by
using the same idea. However, by a refined analysis in [11], we can slightly
improve the approximation ratio $(\frac{5k-7}{2k}+\varepsilon)$ by a term of
$\Theta(1/k)$.

Define $\zeta=\alpha\gamma+\beta(1-\gamma)$. It measures the proportion of
weights of all home-edges compared to the itineraries of all teams. Then, we
have $0\leq\zeta\leq 1$. We can get two following lower bounds.

######  Lemma 36.

$(\frac{k-2}{2}+\zeta)\psi\geq\Delta_{H}$.

###### Proof.

By Lemma 12, we have that
$\Delta_{H}\leq(\frac{k-2}{2}+\alpha)\gamma\psi+(\frac{k-3}{2}+\beta)(1-\gamma)\psi$.
Note that
$(\frac{k-2}{2}+\alpha)\gamma\psi+(\frac{k-3}{2}+\beta)(1-\gamma)\psi\leq(\frac{k-2}{2}+\alpha)\gamma\psi+(\frac{k-2}{2}+\beta)(1-\gamma)\psi=(\frac{k-2}{2}+\zeta)\psi$.
∎

######  Lemma 37.

$\min\\{(1-\frac{1}{2}\zeta)\psi,\frac{k}{k+1}\psi\\}\geq n_{S}\mbox{MST}(H)$.

###### Proof.

We first show that $(1-\frac{1}{2}\zeta)\psi\geq n_{S}\mbox{MST}(H)$. By Lemma
14, we have that
$n_{S}\mbox{MST}(H)\leq(1-\frac{1}{2}\alpha)\gamma\psi+(1-\frac{1}{2}\beta)(1-\gamma)\psi=(1-\frac{1}{2}\zeta)\psi$.

To prove $\frac{k}{k+1}\psi\geq n_{S}\mbox{MST}(H)$, it is sufficient to prove
that $\frac{k}{k+1}w(I_{v})\geq\mbox{MST}(H)$ holds for any $v\in S$. Recall
that $I_{v}$ contains a set of $k^{\prime}$-cycles with $3\leq k^{\prime}\leq
k+1$. For each $k^{\prime}$-cycle $C$, we delete the longest edge and the
weight of the cycle loses at least
$\frac{1}{k^{\prime}}w(C)\geq\frac{1}{k+1}w(C)$. Hence, we can get a spanning
tree with the a total weight of at most $\frac{k}{k+1}w(I_{v})$. We have
$\frac{k}{k+1}w(I_{v})\geq\mbox{MST}(H)$. ∎

By Lemmas 36 and 37, we have that

$\frac{k+2}{4}\psi\geq\frac{1}{2}\Delta_{H}+n_{S}\mbox{MST}(H).$ (18)

######  Theorem 38.

For TTP-$k$ with any constant $k\geq 5$, there is a polynomial-time algorithm
achieving approximation ratio of $(\frac{5k^{2}-4k+3}{2k(k+1)}+\varepsilon)$.

###### Proof.

Here we use $C_{H}$ to denote a minimum weight Hamiltonian cycle in graph $H$.
If we use the Hamiltonian cycle $C^{\prime}_{H}$ obtained by the Christofides-
Serdyukov algorithm, we can construct a feasible schedule with a total weight
of at most
$\frac{k-1}{k}n_{S}w(C^{\prime}_{H})+\frac{2}{k}\Delta_{H}+O(k^{2}/n)\psi$ by
Lemma 21, since
$n_{S}w(C^{\prime}_{H})\leq\frac{3}{2}n_{S}w(C_{H})\leq\frac{3}{2}\psi=O(1)\psi$
(recall that the Christofides-Serdyukov algorithm is a $3/2$-approximation
algorithm for TSP). Then, we have that

$\displaystyle\frac{k-1}{k}n_{S}w(C^{\prime}_{H})+\frac{2}{k}\Delta_{H}$
$\displaystyle\leq\frac{k-1}{k}n_{S}\left(\mbox{MST}(H)+\frac{1}{2}w(C_{H})\right)+\frac{2}{k}\Delta_{H}$
$\displaystyle=\frac{4}{k}\left(n_{S}\mbox{MST}(H)+\frac{1}{2}\Delta_{H}\right)+\frac{k-5}{k}n_{S}\mbox{MST}(H)+\frac{k-1}{2k}n_{S}w(C_{H})$
$\displaystyle\leq\frac{4}{k}\left(\frac{k+2}{4}\psi\right)+\frac{k-5}{k}\left(\frac{k}{k+1}\psi\right)+\frac{k-1}{2k}\psi$
$\displaystyle=\frac{5k^{2}-4k+3}{2k(k+1)}\psi,$

where the first inequality follows from Lemma 3, and the second follows from
Lemmas 11, 37, and (18). Since we consider $k$ as a constant, we can get an
approximation of $(\frac{5k^{2}-4k+3}{2k(k+1)}+\varepsilon)$. Note that it
satisfies that $\frac{5k^{2}-4k+3}{2k(k+1)}\leq\frac{5k-7}{2k}$ for any
constant $k\geq 5$. ∎

##  6 LDTTP-$k$ with $k\geq 3$

If all teams are on a line shape graph, TTP-$k$ is known as Linear Distance
TTP-$k$ (LDTTP-$k$) [27]. For this graph, it is easy to see that the minimum
$k$-cycle/path packing can be found in polynomial time. For LDTTP-3, by
Corollary 32, our algorithm has an approximation ratio of $(4/3+\varepsilon)$,
which also matches the current best-known ratio $4/3$ [27]. Their result is
based on a stronger lower bound of LDTTP-3. If we use this lower bound, the
ratio of our 3-cycle packing construction can achieve $(6/5+\varepsilon)$. In
this section, we will consider LDTTP-$k$ directly.

###  6.1 The Lower Bound

We first propose a lower bound for LDTTP-$k$, which is a generalization of the
lower bound for LDTTP-3 used in [27]. We consider the graph $H$, which is also
a line shape. Assume that the teams from left to right on the line are
$(t_{1},t_{2},\dots,t_{n_{S}})$, respectively. We let $d_{i}=w(t_{i},t_{i+1})$
for all $1\leq i\leq n_{S}-1$. Then, we have the following lemma.

######  Lemma 39.

For LDTTP-$k$, it holds that $\psi\geq\sum_{i=1}^{n_{S}-1}c_{i}d_{i},$ where
$c_{i}=2i\lceil\frac{n_{S}-i}{k}\rceil+2(n_{S}-i)\lceil\frac{i}{k}\rceil$.

###### Proof.

For an edge $t_{i}t_{i+1}$, there are $i$ teams on the left and $n_{S}-i$
teams on the right of it. For each left team, it takes at least
$\lceil\frac{n_{S}-i}{k}\rceil$ trips for it to visit all right teams. For
each right team, it takes at least $\lceil\frac{i}{k}\rceil$ trips for it to
visit all left teams. There are at least
$i\lceil\frac{n_{S}-i}{k}\rceil+(n_{S}-i)\lceil\frac{i}{k}\rceil=\frac{l_{i}}{2}$
trips in total. Each trip must cross the edge twice and hence all teams must
cross the edge at least $l_{i}$ times. Together, we get the lower bound
$\sum_{i=1}^{n_{S}-1}l_{i}d_{i}$. ∎

Next, we analyze the approximation ratio of our $k$-cycle packing schedule.

###  6.2 The Analysis

We can get an optimal $k$-cycle packing $\mathcal{C}_{k}$ in graph $H$ such
that

$\mathcal{C}_{k}=\\{(t_{ki-(k-1)},t_{ki-(k-2)},\dots,t_{ki},t_{ki-(k-1)})\\}_{i=1}^{n_{S}/k}.$

Using $\mathcal{C}_{k}$, by Theorem 25, the weight of our cycle packing
schedule is
$\frac{k-1}{k}n_{S}w(\mathcal{C}_{k})+\frac{2}{k}\Delta_{H}+O(k^{3}/n)\psi$.
Let
$\frac{k-1}{k}n_{S}w(\mathcal{C}_{k})+\frac{2}{k}\Delta_{H}=\sum_{i=1}^{n_{S}-1}f_{i}d_{i}$.
Define $\rho=\max_{1\leq i\leq n_{S}-1}\frac{f_{i}}{c_{i}}$. Then, by Lemma
39, we have

$\displaystyle\frac{k-1}{k}n_{S}w(\mathcal{C}_{k})+\frac{2}{k}\Delta_{H}=\sum_{i=1}^{n_{S}-1}f_{i}d_{i}\leq\rho\sum_{i=1}^{n_{S}-1}c_{i}d_{i}\leq\rho\psi.$
(19)

######  Theorem 40.

For LDTTP-$k$ with any constant $k\geq 3$, the approximation ratio of our
cycle packing schedule is $(\frac{3k-3}{2k-1}+\varepsilon)$.

###### Proof.

By (19), we know that it is sufficient to prove
$\rho=\frac{3k-3}{2k-1}+O(1/n)$. Recall that
$\frac{k-1}{k}n_{S}w(\mathcal{C}_{k})+\frac{2}{k}\Delta_{H}=\sum_{i=1}^{n_{S}-1}f_{i}d_{i}$.
On one hand, it is easy to see that
$\frac{k-1}{k}n_{S}w(\mathcal{C}_{k})=\sum_{i=1}^{n_{S}/k}\sum_{j=1}^{k-1}\frac{2k-2}{k}n_{S}d_{ki-j}$.
On the other hand, we have
$\frac{2}{k}\Delta_{H}=\sum_{i=1}^{n_{S}-1}\frac{4}{k}i(n-i)d_{i}$. Therefore,
we have $f_{i}=\frac{4}{k}i(n_{S}-i)$ for $i\bmod k=0$, and
$f_{i}=\frac{4}{k}i(n_{S}-i)+\frac{2k-2}{k}n_{S}$ for $i\bmod k\neq 0$. Recall
that
$c_{i}=2i\lceil\frac{n_{S}-i}{k}\rceil+2(n_{S}-i)\lceil\frac{i}{k}\rceil$. We
have $f_{i^{\prime}}=f_{n_{S}-i^{\prime}}$ and
$c_{i^{\prime}}=c_{n_{S}-i^{\prime}}$ for any $1\leq i^{\prime}\leq n_{S}/2$.
The structure has a symmetry property, and hence we only consider the case of
$1\leq i\leq n_{S}/2$.

Case 1: $i\bmod k=0$. We have $f_{i}=\frac{4}{k}i(n_{S}-i)$ and
$c_{i}=\frac{4}{k}i(n_{S}-i)$. Then, we can get $\frac{f_{i}}{c_{i}}=1$.

Case 2: $i\bmod k=j$, where $1\leq j<k$. We have
$f_{i}=\frac{4}{k}i(n_{S}-i)+\frac{2k-2}{k}n_{S}$. Note that
$\lceil\frac{n_{S}-i}{k}\rceil=\frac{n_{S}-i+j}{k}$ and
$\lceil\frac{i}{k}\rceil=\frac{i+k-j}{k}$. We have
$c_{i}=2i\lceil\frac{n_{S}-i}{k}\rceil+2(n_{S}-i)\lceil\frac{i}{k}\rceil=\frac{4}{k}i(n_{S}-i)+\frac{2}{k}((k-j)n_{S}+(2j-k)i)$.
Then, we can get

$\displaystyle\frac{f_{i}}{c_{i}}=\ $
$\displaystyle\frac{\frac{4}{k}i(n_{S}-i)+\frac{2k-2}{k}n_{S}}{\frac{4}{k}i(n_{S}-i)+\frac{2}{k}((k-j)n_{S}+(2j-k)i)}$
$\displaystyle=\ $ $\displaystyle
1+\frac{\frac{2}{k}((j-1)n_{S}-(2j-k)i)}{\frac{4}{k}i(n_{S}-i)+\frac{2}{k}((k-j)n_{S}+(2j-k)i)}$
$\displaystyle=\ $ $\displaystyle
1+\frac{(j-1)n_{S}-(2j-k)i}{2i(n_{S}-i)+(k-j)n_{S}+(2j-k)i}.$

In the worst case, it is easy to see that we have $j>1$. Recall that $1\leq
i\leq n_{S}/2$ and $k=\Theta(1)$. If $i=\Theta(n)$, we have
$(j-1)n_{S}-(2j-k)i=\Theta(n)$,
$2i(n_{S}-i)+(k-j)n_{S}+(2j-k)i=\Theta(n^{2})$, and hence
$f_{i}/c_{i}=1+\Theta(1/n)$. Otherwise, if $i=o(n)$ and $i=\omega(1)$, we have
$(j-1)n_{S}-(2j-k)i=\Theta(n)$, $2i(n_{S}-i)+(k-j)n_{S}+(2j-k)i=\omega(n)$,
and hence $f_{i}/c_{i}=1+o(1)$. Hence, for the rest case, we have
$i=\Theta(1)$. Moreover, we have that
$(j-1)n_{S}-(2j-k)i=(j-1)n_{S}+\Theta(1)$ and
$2i(n_{S}-i)+(k-j)n_{S}+(2j-k)i=(k+2i-j)n_{S}+\Theta(1)$. Therefore, in the
worst case, we have that

$\displaystyle\frac{f_{i}}{c_{i}}=\ $ $\displaystyle
1+\frac{(j-1)n_{S}+\Theta(1)}{(k+2i-j)n_{S}+\Theta(1)}$ $\displaystyle=\ $
$\displaystyle 1+\frac{j-1}{k+2i-j}+\Theta(1/n)$ $\displaystyle\leq\ $
$\displaystyle 1+\frac{j-1}{k+j}+\Theta(1/n)$ $\displaystyle\leq\ $
$\displaystyle 1+\frac{k-2}{2k-1}+\Theta(1/n),$

where the first inequality follows from $i\geq j$ since $i\bmod k=j$ and the
second is from $1\leq j<k$.

By the above analysis, we have $\rho=\max_{1\leq i\leq
n_{S}-1}\frac{f_{i}}{c_{i}}=1+\frac{k-2}{2k-1}+O(1/n)=\frac{3k-3}{2k-1}+O(1/n)$.
∎

We can see that the approximation ratio is $(6/5+\varepsilon)$ for LDTTP-3,
which improves the previous result of $(4/3+\varepsilon)$ [27].

For LDTTP-$k$, we can also analyze the Hamiltonian cycle schedule. Let $C_{H}$
be the optimal Hamiltonian cycle in graph $H$, i.e.,
$C_{H}=(t_{1},\dots,t_{n_{S}},t_{1})$. Note that $n_{S}w(C_{H})\leq\psi$ by
Lemma 11. By Lemma 21, the total weight of the Hamiltonian cycle schedule is
$\frac{2k-2}{k}n_{S}w(C_{H})+\frac{2}{k}\Delta_{H}+O(k^{2}/n)\psi$. Let
$\frac{2k-2}{k}n_{S}w(C_{H})+\frac{2}{k}\Delta_{H}=\sum_{i=1}^{n-1}f^{\prime}_{i}d_{i}$.
We have that
$\frac{2k-2}{k}n_{S}w(C)=\sum_{i=1}^{n_{S}-1}\frac{2k-2}{k}n_{S}d_{i}$,
$\frac{2}{k}\Delta_{H}=\sum_{i=1}^{n_{S}-1}\frac{4}{k}i(n_{S}-i)d_{i}$, and
$c_{i}=2i\lceil\frac{n_{S}-i}{k}\rceil+2(n_{S}-i)\lceil\frac{i}{k}\rceil$. It
is easy to see that the bottleneck case is

$\frac{f^{\prime}_{k}}{c_{k}}=\frac{\frac{2k-2}{k}n_{S}+4(n_{S}-k)}{4(n_{S}-k)}=\frac{3k-1}{2k}+O(1/n).$

######  Theorem 41.

For LDTTP-$k$ with any constant $k\geq 3$, the approximation ratio of the
Hamiltonian cycle schedule is $(\frac{3k-1}{2k}+\varepsilon)$.

We can see that the approximation ratio $(\frac{3k-1}{2k}+\varepsilon)$ is
worse than the ratio $(\frac{3k-3}{2k-1}+\varepsilon)$. A natural question is
whether there is an algorithm with an approximation ratio better than
$(\frac{3k-3}{2k-1}+\varepsilon)$.

##  7 Conclusion

In this paper, we consider approximation algorithms for TTP-$k$. We propose
several new lower bounds and a new construction based on the $k$-cycle/path
packing. Our construction can be combined well with the previous construction
on the Hamiltonian cycle. For TTP-3, which is the most investigated case of
TTP-$k$, we prove that these constructions can guarantee an
$(139/87+\varepsilon)$-approximation ratio which is better than the best-known
ratio $(5/3+\varepsilon)$. Moreover, we show that we can improve the ratio
from $(7/4+\varepsilon)$ to $(17/10+\varepsilon)$ for TTP-4 and from
$(\frac{5k-7}{2k}+\varepsilon)$ to $(\frac{5k^{2}-4k+3}{2k(k+1)}+\varepsilon)$
for TTP-$k$ with $k\geq 5$. Furthermore, for LDTTP-$k$, we show that the cycle
packing construction has an approximation of
$(\frac{3k-3}{2k-1}+\varepsilon)$, which improves the ratio from $4/3$ to
$(6/5+\varepsilon)$ for LDTTP-3. We also remark that according to our results,
an improved approximation ratio for minimum weight $k$-cycle/path packing may
directly lead to further improvements for TTP-$k$.

Acknowledgements The work is supported by the National Natural Science
Foundation of China, under grant 62372095.

## Declarations

### Funding

Not applicable.

### Competing interests

The authors declare no competing interests.

### Ethics approval and consent to participate

Not applicable.

### Consent for publication

Not applicable.

### Data availability

Not applicable.

### Materials availability

Not applicable.

### Code availability

Not applicable.

### Author contribution

All authors wrote the main manuscript text. All authors reviewed the
manuscript.

## References

  *   * Easton et al. [2001] Easton, K., Nemhauser, G., Trick, M.: The traveling tournament problem: description and benchmarks. In: 7th International Conference on Principles and Practice of Constraint Programming, pp. 580–584 (2001)
  * Bhattacharyya [2016] Bhattacharyya, R.: Complexity of the unconstrained traveling tournament problem. Operations Research Letters 44(5), 649–654 (2016)
  * Thielen and Westphal [2011] Thielen, C., Westphal, S.: Complexity of the traveling tournament problem. Theoretical Computer Science 412(4), 345–351 (2011)
  * Chatterjee [2021] Chatterjee, D.: Complexity of traveling tournament problem with trip length more than three. CoRR abs/2110.02300 (2021) 2110.02300
  * Thielen and Westphal [2012] Thielen, C., Westphal, S.: Approximation algorithms for TTP(2). Mathematical Methods of Operations Research 76(1), 1–20 (2012)
  * Xiao and Kou [2016] Xiao, M., Kou, S.: An improved approximation algorithm for the traveling tournament problem with maximum trip length two. In: MFCS 2016, vol. 58, pp. 89–18914 (2016)
  * Zhao and Xiao [2021a] Zhao, J., Xiao, M.: The traveling tournament problem with maximum tour length two: A practical algorithm with an improved approximation bound. In: IJCAI 2021, pp. 4206–4212 (2021)
  * Zhao and Xiao [2021b] Zhao, J., Xiao, M.: A further improvement on approximating TTP-2. In: COCOON 2021. Lecture Notes in Computer Science, vol. 13025, pp. 137–149 (2021)
  * Chatterjee and Roy [2021] Chatterjee, D., Roy, B.K.: An improved scheduling algorithm for traveling tournament problem with maximum trip length two. In: ATMOS 2021, vol. 96, pp. 16–11615 (2021)
  * Miyashiro et al. [2012] Miyashiro, R., Matsui, T., Imahori, S.: An approximation algorithm for the traveling tournament problem. Annals of Operations Research 194(1), 317–324 (2012)
  * Yamaguchi et al. [2011] Yamaguchi, D., Imahori, S., Miyashiro, R., Matsui, T.: An improved approximation algorithm for the traveling tournament problem. Algorithmica 61(4), 1077–1091 (2011)
  * Imahori et al. [2014] Imahori, S., Matsui, T., Miyashiro, R.: A 2.75-approximation algorithm for the unconstrained traveling tournament problem. Annals of Operations Research 218(1), 237–247 (2014)
  * Westphal and Noparlik [2014] Westphal, S., Noparlik, K.: A 5.875-approximation for the traveling tournament problem. Annals of Operations Research 218(1), 347–360 (2014)
  * Hoshino and Kawarabayashi [2013] Hoshino, R., Kawarabayashi, K.-i.: An approximation algorithm for the bipartite traveling tournament problem. Mathematics of Operations Research 38(4), 720–728 (2013)
  * Imahori [2021] Imahori, S.: A 1+O(1/N) approximation algorithm for TTP(2). CoRR abs/2108.08444 (2021) 2108.08444
  * Easton et al. [2003] Easton, K., Nemhauser, G., Trick, M.: Solving the travelling tournament problem: a combined integer programming and constraint programming approach. In: 4th International Conference of Practice and Theory of Automated Timetabling IV, pp. 100–109 (2003)
  * Lim et al. [2006] Lim, A., Rodrigues, B., Zhang, X.: A simulated annealing and hill-climbing algorithm for the traveling tournament problem. European Journal of Operational Research 174(3), 1459–1478 (2006)
  * Anagnostopoulos et al. [2006] Anagnostopoulos, A., Michel, L., Van Hentenryck, P., Vergados, Y.: A simulated annealing approach to the traveling tournament problem. Journal of Scheduling 9(2), 177–193 (2006)
  * Di Gaspero and Schaerf [2007] Di Gaspero, L., Schaerf, A.: A composite-neighborhood tabu search approach to the traveling tournament problem. Journal of Heuristics 13(2), 189–207 (2007)
  * Goerigk et al. [2014] Goerigk, M., Hoshino, R., Kawarabayashi, K., Westphal, S.: Solving the traveling tournament problem by packing three-vertex paths. In: Twenty-Eighth AAAI Conference on Artificial Intelligence, pp. 2271–2277 (2014)
  * Goerigk and Westphal [2016] Goerigk, M., Westphal, S.: A combined local search and integer programming approach to the traveling tournament problem. Ann. Oper. Res. 239(1), 343–354 (2016)
  * Trick [2022] Trick, M.: Challenge traveling tournament instances. Accessed: 2022-4-01 (2022)
  * Bulck et al. [2020] Bulck, D.V., Goossens, D.R., Schönberger, J., Guajardo, M.: Robinx: A three-field classification and unified data format for round-robin sports timetabling. Eur. J. Oper. Res. 280(2), 568–580 (2020)
  * Karlin et al. [2021] Karlin, A.R., Klein, N., Gharan, S.O.: A (slightly) improved approximation algorithm for metric TSP. In: STOC 2021, pp. 32–45 (2021)
  * Christofides [1976] Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group (1976)
  * Serdyukov [1978] Serdyukov, A.I.: Some extremal bypasses in graphs. Upravlyaemye Sistemy 17, 76–79 (1978)
  * Hoshino and Kawarabayashi [2012] Hoshino, R., Kawarabayashi, K.: Generating approximate solutions to the TTP using a linear distance relaxation. J. Artif. Intell. Res. 45, 257–286 (2012)
  * Zhao et al. [2022] Zhao, J., Xiao, M., Xu, C.: Improved approximation algorithms for the traveling tournament problem. In: MFCS 2022,. LIPIcs, vol. 241, pp. 83–18315 (2022)
  * Campbell and Chen [1976] Campbell, R.T., Chen, D.-S.: A minimum distance basketball scheduling problem. Management science in sports 4, 15–26 (1976)
  * Asano et al. [1996] Asano, T., Katoh, N., Tamaki, H., Tokuyama, T.: Covering points in the plane by k-tours: a polynomial approximation scheme for fixed k. IBM Tokyo Research Laboratory Research Report RT0162 (1996)
  * Kirkman [1847] Kirkman, T.P.: On a problem in combinations. Cambridge and Dublin Mathematical Journal 2, 191–204 (1847)
  * De Werra [1981] De Werra, D.: Scheduling in sports. Studies on graphs and discrete programming 11, 381–395 (1981)
  * Motwani and Raghavan [1995] Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
  * Goemans and Williamson [1995] Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2), 296–317 (1995)
  * Monnot and Toulouse [2008] Monnot, J., Toulouse, S.: Approximation results for the weighted p${}_{\mbox{4}}$ partition problem. J. Discrete Algorithms 6(2), 299–312 (2008)