# The APX-hardness of the Traveling Tournament Problem

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

The Traveling Tournament Problem (TTP-$k$) is a well-known benchmark problem
in sports scheduling, 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, each
team plays at most $k$-consecutive home games or away games, and the total
traveling distance of all the $n$ teams is minimized. TTP-$k$ allows a PTAS
when $k=2$ and becomes APX-hard when $k\geq n-1$. In this paper, we reduce the
gap by showing that TTP-$k$ is APX-hard for any fixed $k\geq 3$.

Keywords: Traveling Tournament Problem, APX-hardness, Approximation
Algorithms, Sports Scheduling, Combinatorial Optimization

##  1 Introduction

In the field of sports scheduling [17], the traveling tournament problem
(TTP-$k$) is a well-known benchmark problem that was first systematically
introduced in [11]. 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 two games against each of the other $n-1$ teams, one home game at
its home venue and one away game 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-$k$, we
have the following three basic constraints or assumptions on the double round-
robin tournament.

Traveling Tournament Problem (TTP-$k$)

  * •

_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 the $i$-th day to its game venue on the $(i+1)$-th day.

  * •

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

The input of TTP-$k$ is a complete graph where each vertex represents a team
and the weight between two vertices $a$ and $b$, denoted by $w(a,b)$, is the
distance from the home of team $a$ to the home of team $b$. We only consider
the case when the weight function $w$ satisfies the symmetry and triangle
inequality properties, i.e., $w(a,b)+w(b,c)\geq w(a,c)=w(c,a)$ for all
vertices $a,b,c$.

TTP-$k$ is a difficult combinatorial optimization problem. Readers can refer
to [5, 10] for an overview. For the case of $k=1$, the problem is infeasible
[9]. When $k\geq 2$ and $n$ is an even number greater than 2, feasible
solutions exist. Next, we survey the complexity of TTP-$k$.

For $k=2$, the NP-hardness is still unknown but a PTAS has already been found
[20, 14, 26]. For $k=3$, Thielen and Westphal [19] proved the NP-hardness by a
reduction from 3-SAT. Using a generalized reduction from $k$-SAT, Chatterjee
[6] proved the NP-hardness for any fixed $k>3$. When $k\geq n-1$, the bounded-
by-$k$ constraint loses its meaning and the traveling distance of a team can
be as short as that of a TSP. We may simply use $k=n-1$ to denote this case.
For $k=n-1$, Bhattacharyya [4] proved the NP-hardness using a reduction from
$(1,2)$-TSP, i.e., a special case of TSP where the edge weights are either 1
or 2. Recently, using an L-reduction from $(1,2)$-TSP, Bendayan _et al._ [3]
further proved the APX-hardness of TTP-$(n-1)$. So, there is no PTAS for
TTP-$(n-1)$ unless P=NP.

Since TTP-2 admits a PTAS while TTP-$(n-1)$ does not, a natural question is
whether TTP-$k$ admits a PTAS or not for any fixed $k\geq 3$. In this paper,
we answer this question by proving that TTP-$k$ is APX-hard for any fixed
$k\geq 3$. A summary of the current-known complexities of TTP-$k$ is shown in
Table 1.

TTP-$k$ | $k=2$ | $k=3$ | $3<k=O(1)$ | $k\geq n-1$
---|---|---|---|---
P v.s. NP-hard | Unknown | NP-hard [19] | NP-hard [6] | NP-hard [4]
PTAS v.s. APX-hard | PTAS [20, 14, 26] | APX-hard [This Paper] | APX-hard [3]
Table 1: A summary of the current-known complexities of TTP-$k$

It is worth mentioning that there is a large number of studies on
approximation algorithms [20, 23, 26, 25, 7, 14, 18, 12, 13]. For $k=2$, the
approximation ratios for even $n/2$ and odd $n/2$ have been improved to
$(1+3/n)$ and $(1+5/n)$ [27], which implies that TTP-2 admits a PTAS. For
$k=3$ and $k=4$, the approximation ratios are $(139/87+\varepsilon)$ and
$(17/10+\varepsilon)$ [29], respectively. For $5\leq k=o(n)$, the ratio is
$(5k-7)/(2k)+O(k/n)$ [24]. For $k=n-1$, Imahori  _et al._ [15] proposed a
$2.75$-approximation algorithm. At the same time, Westphal and Noparlik [21]
proposed a $5.875$-approximation algorithm for all $k\geq 4$ and $n\geq 6$.
Note that when $k$ is sufficiently large the latter three approximation ratios
can be slightly improved due to the randomized
$(3/2-\varepsilon_{0})$-approximation algorithm for TSP, where
$\varepsilon_{0}$ is a value of about $10^{-36}$ [16].

##  2 Preliminary

In the following, we always consider $k$ as a constant. A simple path on $k$
different vertices is called a _$k$ -path_. A _$k$ -path packing_ in a graph
of $n$ vertices is a set of vertex-disjoint $n/k$ $k$-paths such that all
vertices in the graph are covered. Note that a $k$-path packing exists only if
$n\bmod k=0$. A weight function is called an _integer_ function if it only
outputs non-negative and constant integers. If the input is a graph for an
instance $I$, we use $I=(V_{I},E_{I})$ to denote the graph where $V_{I}$
denotes the vertex set and $E_{I}$ denotes the edge set of the graph.

###  2.1 APX-hardness and L-reduction

An optimization problem belongs to the APX class if it admits an
$O(1)$-approximation algorithm. Moreover, it has a polynomial-time
approximation scheme (PTAS) if it has an $(1+\varepsilon)$-approximation
algorithm for any constant $\varepsilon>0$. A problem is APX-hard if for every
problem in APX there is a PTAS-reduction to it. To prove the APX-hardness of a
problem, we may also use an L-reduction (linear reduction) from an APX-hard
problem, where an L-reduction directly implies a PTAS reduction [8]. The
definition of L-reduction is given as follows.

######  Definition 1 ([22]).

Given two optimization problems $\Pi$ and $\Xi$, we have an L-reduction from
$\Pi$ to $\Xi$ if for some constants $\alpha,\beta>0$:

  1. 1.

For each instance $I$ of $\Pi$ we can compute in polynomial time an instance
$J$ of $\Xi$;

  2. 2.

$\mbox{OPT}(J)\leq\alpha\cdot\mbox{OPT}(I)$;

  3. 3.

Given a solution of weight $S(J)$ to $J$, we can compute in polynomial time a
solution of weight $S(I)$ to $I$ such that

$|S(I)-\mbox{OPT}(I)|\leq\beta\cdot|S(J)-\mbox{OPT}(J)|.$

###  2.2 The Framework of the Reduction

To establish the APX-hardness of TTP-$k$, we employ a well-known APX-hard
problem called the $k$-tour cover problem ($k$-TC). However, instead of
directly using $k$-TC, we consider a variant called Boosted Restricted $k$-TC.
We first show that Boosted Restricted $k$-TC remains APX-hard (see Section 3).

In our L-reduction from Boosted Restricted $k$-TC to TTP-$k$, given an
instance $I$ of Boosted Restricted $k$-TC, we first construct an instance
$I^{\prime}$ of $k$-TC satisfying some desired properties and then construct
an instance $J$ of TTP-$k$ in polynomial time. The details of these
constructions are explained in Section 4. By further proving the last two
properties of the L-reduction in Sections 5 and 6 respectively, we establish
the APX-hardness of TTP-$k$.

######  Theorem 2.

TTP-$k$ is APX-hard for any fixed $k\geq 3$.

##  3 The Boosted Restricted $k$-Tour Cover Problem

In TTP-$k$, the frequency at which a single team needs to return home depends
on the value of $k$. When the value of $k$ is small, the team is required to
return home more frequently. Conversely, if $k$ is very large, such as
$k=n-1$, the constraint of being bounded by $k$ loses its significance, and
the team can schedule their travel distances to be as short as in the
Traveling Salesman Problem (TSP). In order to compute the minimum traveling
distance for a team in this scenario, we need to solve the $k$-tour cover
problem ($k$-TC) [2].

######  Definition 3 ($k$-TC).

An instance of $k$-TC can be presented by a complete graph $I=(V_{I},E_{I})$,
where there is one depot vertex $o$ in $V_{I}$, $n-1$ non-depot vertices in
$V_{I}\setminus\\{o\\}$, and a weight function $w$ on the edges in $E_{I}$.
The goal of $k$-TC is to find a set of tours of minimum total weight covering
all non-depot vertices such that each tour is a simple cycle that always
contains the depot vertex and at most $k$ non-depot vertices.

$k$-TC is known to be APX-hard for any fixed $k\geq 3$ [1]333Note that the
paper [1] may not be easily accessible or searchable through specific
platforms. Here, we refer to a version of the paper titled in Japanese but
written in English [30], which can be accessed through Google Scholar.. Given
the relationship between TTP-$k$ and $k$-TC, one potential approach to prove
the APX-hardness of TTP-$k$ is through an L-reduction from $k$-TC to TTP-$k$.
However, directly performing such a reduction is not a straightforward task.
We introduce a restricted version of $k$-TC, denoted as Restricted $k$-TC. It
was implicitly used and proved to be APX-hard for any fixed $k\geq 3$ in [1].

######  Definition 4 (Restricted $k$-TC).

Compared to the definition of $k$-TC, Restricted $k$-TC introduces an
additional constraint on the weight function $w$. Specifically, the weight
function $w$ is required to be an integer function, and it must satisfy the
condition $w(o,v)=\Theta(1)$ for all $v\in V_{I}\setminus\\{o\\}$.

Definition 4 is motivated by the following fact. The outputs of the weight
function used in [1] are all constant fractions (related to $k$), e.g.,
$\frac{3k-7}{2k-4}$. Moreover, the weights of edges incident to the depot
vertex are all positive. Therefore, by scaling up a positive constant integer
(related to $k$), we can assume w.l.o.g. that the weight function is an
integer function and it holds $w(o,v)=\Theta(1)$ for every $v\in
V_{I}\setminus\\{o\\}$. For any solution of Restricted $k$-TC with weight
$S(I)$, we can get $S(I)-\mbox{OPT}(I)=\Omega(1)$ if $S(I)\neq\mbox{OPT}(I)$.
Moreover, the solution of Restricted $k$-TC has the following property.

######  Lemma 5.

For any instance $I$ of Restricted $k$-TC, any feasible solution has a weight
of $\Theta(n)$.

###### Proof.

Since each tour cover at most $k$ non-depot vertices, to cover all $n-1$ non-
depot vertices, any feasible solution must contain at least
$\lfloor\frac{n-1}{k}\rfloor$ tours and then use at least
$2\cdot\lfloor\frac{n-1}{k}\rfloor$ edges incident to the depot vertex. By
Definition 4, $w(o,v)=\Theta(1)$ for any $v\in V_{I}\setminus\\{o\\}$. Hence,
a lower bound of any feasible solution is $\Theta(n)$. Moreover, by the
triangle inequality, any feasible solution has a weight of at most
$2\sum_{v\in V_{I}}w(o,v)=\Theta(n)$, i.e., in the worst solution, each tour
only covers a single non-depot vertex. Therefore, any feasible solution has a
weight of $\Theta(n)$. ∎

Then, we introduce a boosted version of Restricted $k$-TC, denoted as Boosted
Restricted $k$-TC.

######  Definition 6 (Boosted Restricted $k$-TC).

Given an instance $I$ of Restricted $k$-TC, the objective of Boosted
Restricted $k$-TC is to find a solution $I$ of Restricted $k$-TC with weight
$S(I)$ that minimizes the expression $m(m^{2}-1)\cdot S(I)$, where
$m=\Theta(n)$ (to be defined later).

The concept of the “boosted method” has previously been used in proving the
APX-hardness of TTP-$(n-1)$ in [3]. It is worth noting that Boosted Restricted
$k$-TC remains APX-hard for any fixed $k\geq 3$ and the input for Boosted
Restricted $k$-TC is the same as that for Restricted $k$-TC. To prove our main
theorem, we will establish an L-reduction from Boosted Restricted $k$-TC to
TTP-$k$.

Next, we show the details of the L-reduction. By Definition 1, there are three
conditions in the L-reduction. We will consider them respectively.

##  4 The Construction of the Instance

Given an instance $I$ of Restricted $k$-TC, we first make some modifications
to obtain an instance $I^{\prime}$ of $k$-TC and then show how to construct an
instance $J$ of TTP-$k$, both in polynomial time.

An _$l$ -tour_ is a simple cycle that contains the depot vertex and exactly
$l$ non-depot vertices. A solution of an instance of $k$-TC that contains only
$k$-tours is called a _saturated_ solution. An instance of $k$-TC is called a
_saturated_ instance if it admits an optimal saturated solution. Not every
instance $I$ of Restricted $k$-TC is saturated. However, by adding some new
non-depot vertices on the depot position, we can get an equivalent saturated
instance $I^{\prime}$ of $k$-TC, i.e., there is an optimal saturated solution
with the same weight of the optimal solution in $I$. In the following, we use
$m$ to denote the number of non-depot vertices in $I^{\prime}$.

######  Lemma 7.

Given an instance $I$ of Restricted $k$-TC, there is a polynomial-time
algorithm to get an equivalent saturated instance $I^{\prime}$ of $k$-TC, and
the number of non-depot vertices in $I^{\prime}$ is even.

###### Proof.

Suppose that there is an optimal solution in $I$ that contains $c_{l}$ of
$l$-tours. Firstly, we can see that after adding some new non-depot vertices
on the depot position we can get an equivalent new instance. If we add
$\sum_{l<k}c_{l}(k-l)$ new non-depot vertices on the depot position, the
optimal solution in $I$ corresponds to an optimal saturated solution in the
new instance since we can fill each $l$-tour in the optimal solution in $I$
with $k-l$ of the new non-depot vertices. Then, if we further add $n^{\prime}$
with $n^{\prime}\bmod k=0$ new non-depot vertices on the depot position, there
still exists an optimal saturated solution in the new instance since the new
non-depot vertices can be covered by $n^{\prime}/k$ new $k$-tours with zero
weight. We have $\sum_{l<k}c_{l}(k-l)<\sum_{l<k}nk<nk^{2}$ since $c_{l}<n$.
So, let $n^{\prime}=nk^{2}+k-(n-1)\bmod k-\sum_{l<k}c_{l}(k-l)$. We have
$n^{\prime}>0$ and $n^{\prime}\bmod k=0$ since
$(n-1+\sum_{l<k}c_{l}(k-l))\bmod k=0$. Therefore, given the instance $I$, by
adding $\sum_{l<k}c_{l}(k-l)+n^{\prime}=nk^{2}+k-(n-1)\bmod k$ new non-depot
vertices on the depot position, we can get an equivalent saturated instance
$I^{\prime}$ of $k$-TC. Note that there is 1 depot vertex and $m\coloneqq
n-1+nk^{2}+k-(n-1)\bmod k$ non-depot vertices in $I^{\prime}$. We may assume
w.l.o.g. that $m\bmod 2=0$. Otherwise, we have $k\bmod 2=1$ since $m\bmod
k=0$, and in this case, we can further add $k$ new non-depot vertices on the
depot position. Then, $m\leftarrow m+k$ would be even. Since $k=O(1)$,
$I^{\prime}$ can be obtained in polynomial time. ∎

Note that the original instance $I$ of Restricted $k$-TC has $n$ vertices,
while the modified instance $I^{\prime}$ of $k$-TC has $m+1$ vertices,
including one depot vertex and $m=\Theta(n)$ non-depot vertices.

To construct an instance $J$ of TTP-$k$, we further add $m(m^{2}-1)-1$ new
vertices on the depot position of $I^{\prime}$. Therefore, $J$ has $m^{3}$
vertices, each representing a team. Among these vertices, $m(m^{2}-1)$
vertices are considered as _dummy_ vertices, including one depot vertex and
$m(m^{2}-1)-1$ new vertices. This construction can be achieved in polynomial
time, leading to the following lemma.

######  Lemma 8.

Given an instance $I$ of Restricted $k$-TC, we can construct the above
instance $J$ of TTP-$k$ in polynomial time.

An illustration of the relations for instances $I$, $I^{\prime}$ and $J$ can
be seen in Figure 1. Both $I^{\prime}$ and $J$ are obtained by adding some
vertices on the depot position of $I$.

CAB$I$ Figure 1: An illustration of the relations for instances $I$,
$I^{\prime}$, and $J$, where cycle $C$ denotes the depot position, cycle $A$
denotes $m-(n-1)$ vertices on the depot, and cycle $B$ denotes $m(m^{2}-1)-1$
vertices on the depot: the ellipse can be seen as instance $I$ (containing 1
depot vertex, denoted by the black node, and $n-1$ non-depot vertices, denoted
by the white nodes), the ellipse with vertices in $A$ can be seen as instance
$I^{\prime}$, and the ellipse with vertices in $A$ and $B$ can be seen as
instance $J$

##  5 The Second Property

In this section, we prove the second property of the L-reduction in Definition
1. Note that $I$ is an instance of Restricted $k$-TC and our L-reduction is
from Boosted Restricted $k$-TC. Hence, we need to prove that
$\mbox{OPT}(J)\leq\alpha\cdot m(m^{2}-1)\cdot\mbox{OPT}(I)$, where $\alpha$ is
a constant.

Recall that in $I^{\prime}$ of $k$-TC there always exists an optimal saturated
solution that contains only $k$-tours. So, such a solution corresponds to a
$k$-path packing in the graph induced by the $m$ non-depot vertices, denoted
by $\mathcal{P}^{*}_{k}$. Based on this $k$-path packing, we will construct a
solution for instance $J$ of TTP-$k$, which is an upper bound of $OPT(J)$.

###  5.1 The construction of the schedule

There are $d\coloneqq m/k$ $k$-paths in $\mathcal{P}^{*}_{k}$. We will pack
them as a _super-team_ , denoted by $U_{1}$. There are still $m(m^{2}-1)$
dummy vertices on the depot position, which will be divided into
$m(m^{2}-1)/k$ $k$-paths with zero weight and then further divided into
$m^{2}-1$ dummy super-teams by arbitrarily packing $d$ $k$-paths as a super-
team, denoted by $\\{U_{2},\dots,U_{m^{2}}\\}$. Hence, there are $m^{2}$
super-teams in total, and in each super-team there are $d$ $k$-paths and hence
$m$ vertices.

If a dummy team in $U_{i}$ ($i>1$) (i.e., a dummy vertex with its position on
the depot position) always plays $k$-consecutive away games along each
$k$-path in $U_{1}$ then its total traveling distance is exactly
$\mbox{OPT}(I^{\prime})=\mbox{OPT}(I)$. We will construct a feasible solution
for TTP-$k$ such that all dummy teams play $k$-consecutive away games along
each $k$-path in $U_{1}$. Our construction is based on the $k$-path packing
construction in [28]. The main idea is to first arrange _super-games_ between
super-teams and then extend the super-games into normal games.

The super-game schedule contains $m^{2}$ time slots. The designs in the first
and last time slots are slightly different from other time slots. We first
consider the first $m^{2}-1$ time slots. In each of the first $m^{2}-1$ time
slots there are $m^{2}/2$ super-games. In the first time slot, the $m^{2}/2$
super-games can be seen in Figure 2, where each super-game is represented by a
directed edge and all super-games are _normal_ super-games. The last super-
team is denoted by a double-cycle node, while the other super-teams are
denoted by single-cycle nodes.

$U_{16}$$U_{1}$$U_{2}$$U_{15}$$U_{3}$$U_{14}$$U_{4}$$U_{13}$$U_{5}$$U_{12}$$U_{6}$$U_{11}$$U_{7}$$U_{10}$$U_{8}$$U_{9}$
Figure 2: The super-game schedule in the first time slot, where $m=4$

In the second time slot, we change the positions of single-cycle nodes in the
cycle $U_{1}U_{2}\dots U_{m^{2}-1}$ by moving one position in the clockwise
direction, and we also change the direction of each edge except for the most
left edge. The main difference with the first time slot is that the super-game
for the most left edge is called the _left_ super-game, where we put a letter
‘L’ to denote it. The other super-games are still normal super-games. So,
there is $1$ left super-game and $m^{2}/2-1$ normal super-games in the second
time slot.

$U_{16}$$U_{15}$L$U_{1}$$U_{14}$$U_{2}$$U_{13}$$U_{3}$$U_{12}$$U_{4}$$U_{11}$$U_{5}$$U_{10}$$U_{6}$$U_{9}$$U_{7}$$U_{8}$
Figure 3: The super-game schedule in the second time slot, where $m=4$

In the third time slot, we change the positions of single-cycle nodes in the
cycle $U_{1}U_{2}\dots U_{m^{2}-1}$ by moving one position in the clockwise
direction, and change the direction of every edge. So, there is still $1$ left
super-game and $m^{2}/2-1$ normal super-games in the third time slot.

$U_{16}$$U_{14}$L$U_{15}$$U_{13}$$U_{1}$$U_{12}$$U_{2}$$U_{11}$$U_{3}$$U_{10}$$U_{4}$$U_{9}$$U_{5}$$U_{8}$$U_{6}$$U_{7}$
Figure 4: The super-game schedule in the second time slot, where $m=4$

The schedules for the other time slots (except for the last) are derived
analogously. Before we introduce the super-games in the last time slot, we
first explain how to extend the normal/left super-games in the first $m-1$
time slots to normal games.

Normal super-games: We consider a normal super-game from super-teams $U_{i}$
to $U_{j}$. Recall that each super-team contains $d$ $k$-paths. Recall that
there are $d$ $k$-paths in each super-team. Assume that
$U_{i}=\\{\\{x_{0},\dots,x_{k-1}\\},\\{x_{kd-k},\dots,x_{kd-1}\\}\\}$ and
$U_{j}=\\{\\{y_{0},\dots,y_{k-1}\\},\\{y_{kd-k},\dots,y_{kd-1}\\}\\}$, where
$\\{x_{ki^{\prime}-k},\dots,x_{ki^{\prime}-1}\\}$ (resp.,
$\\{y_{ki^{\prime}-k},\dots,y_{ki^{\prime}-1}\\}$) denotes the $i^{\prime}$-th
$k$-path in $U_{i}$ (resp., $U_{j}$). The normal super-game will be extended
into normal games on $2kd$ days in the following way:

  * •

Team $x_{ki+i^{\prime}}$ plays an away game with $y_{kj+j^{\prime}}$ on
$(2k(i+j)+i^{\prime}+j^{\prime})\bmod 2kd$ day,

  * •

Team $x_{ki+i^{\prime}}$ plays a home game with $y_{kj+j^{\prime}}$ on
$(2k(i+j)+i^{\prime}+j^{\prime}+k)\bmod 2kd$ day,

where $0\leq i,j\leq d-1$ and $0\leq i^{\prime},j^{\prime}\leq k-1$. An
illustration of the normal games after extending one normal super-game for
$k=3$ and $d=2$ is shown in Table 2.

|  $0$ |  $1$ |  $2$ |  $3$ |  $4$ |  $5$ |  $6$ |  $7$ |  $8$ |  $9$ |  $10$ |  $11$
---|---|---|---|---|---|---|---|---|---|---|---|---
$x_{0}$ |  $y_{0}$ |  $y_{1}$ |  $y_{2}$ |  $\boldsymbol{y_{0}}$ |  $\boldsymbol{y_{1}}$ |  $\boldsymbol{y_{2}}$ |  $y_{3}$ |  $y_{4}$ |  $y_{5}$ |  $\boldsymbol{y_{3}}$ |  $\boldsymbol{y_{4}}$ |  $\boldsymbol{y_{5}}$
$x_{1}$ |  $\boldsymbol{y_{5}}$ |  $y_{0}$ |  $y_{1}$ |  $y_{2}$ |  $\boldsymbol{y_{0}}$ |  $\boldsymbol{y_{1}}$ |  $\boldsymbol{y_{2}}$ |  $y_{3}$ |  $y_{4}$ |  $y_{5}$ |  $\boldsymbol{y_{3}}$ |  $\boldsymbol{y_{4}}$
$x_{2}$ |  $\boldsymbol{y_{4}}$ |  $\boldsymbol{y_{5}}$ |  $y_{0}$ |  $y_{1}$ |  $y_{2}$ |  $\boldsymbol{y_{0}}$ |  $\boldsymbol{y_{1}}$ |  $\boldsymbol{y_{2}}$ |  $y_{3}$ |  $y_{4}$ |  $y_{5}$ |  $\boldsymbol{y_{3}}$
$x_{3}$ |  $y_{3}$ |  $y_{4}$ |  $y_{5}$ |  $\boldsymbol{y_{3}}$ |  $\boldsymbol{y_{4}}$ |  $\boldsymbol{y_{5}}$ |  $y_{0}$ |  $y_{1}$ |  $y_{2}$ |  $\boldsymbol{y_{0}}$ |  $\boldsymbol{y_{1}}$ |  $\boldsymbol{y_{2}}$
$x_{4}$ |  $\boldsymbol{y_{2}}$ |  $y_{3}$ |  $y_{4}$ |  $y_{5}$ |  $\boldsymbol{y_{3}}$ |  $\boldsymbol{y_{4}}$ |  $\boldsymbol{y_{5}}$ |  $y_{0}$ |  $y_{1}$ |  $y_{2}$ |  $\boldsymbol{y_{0}}$ |  $\boldsymbol{y_{1}}$
$x_{5}$ |  $\boldsymbol{y_{1}}$ |  $\boldsymbol{y_{2}}$ |  $y_{3}$ |  $y_{4}$ |  $y_{5}$ |  $\boldsymbol{y_{3}}$ |  $\boldsymbol{y_{4}}$ |  $\boldsymbol{y_{5}}$ |  $y_{0}$ |  $y_{1}$ |  $y_{2}$ |  $\boldsymbol{y_{0}}$
$y_{0}$ |  $\boldsymbol{x_{0}}$ |  $\boldsymbol{x_{1}}$ |  $\boldsymbol{x_{2}}$ |  $x_{0}$ |  $x_{1}$ |  $x_{2}$ |  $\boldsymbol{x_{3}}$ |  $\boldsymbol{x_{4}}$ |  $\boldsymbol{x_{5}}$ |  $x_{3}$ |  $x_{4}$ |  $x_{5}$
$y_{1}$ |  $x_{5}$ |  $\boldsymbol{x_{0}}$ |  $\boldsymbol{x_{1}}$ |  $\boldsymbol{x_{2}}$ |  $x_{0}$ |  $x_{1}$ |  $x_{2}$ |  $\boldsymbol{x_{3}}$ |  $\boldsymbol{x_{4}}$ |  $\boldsymbol{x_{5}}$ |  $x_{3}$ |  $x_{4}$
$y_{2}$ |  $x_{4}$ |  $x_{5}$ |  $\boldsymbol{x_{0}}$ |  $\boldsymbol{x_{1}}$ |  $\boldsymbol{x_{2}}$ |  $x_{0}$ |  $x_{1}$ |  $x_{2}$ |  $\boldsymbol{x_{3}}$ |  $\boldsymbol{x_{4}}$ |  $\boldsymbol{x_{5}}$ |  $x_{3}$
$y_{3}$ |  $\boldsymbol{x_{3}}$ |  $\boldsymbol{x_{4}}$ |  $\boldsymbol{x_{5}}$ |  $x_{3}$ |  $x_{4}$ |  $x_{5}$ |  $\boldsymbol{x_{0}}$ |  $\boldsymbol{x_{1}}$ |  $\boldsymbol{x_{2}}$ |  $x_{0}$ |  $x_{1}$ |  $x_{2}$
$y_{4}$ |  $x_{2}$ |  $\boldsymbol{x_{3}}$ |  $\boldsymbol{x_{4}}$ |  $\boldsymbol{x_{5}}$ |  $x_{3}$ |  $x_{4}$ |  $x_{5}$ |  $\boldsymbol{x_{0}}$ |  $\boldsymbol{x_{1}}$ |  $\boldsymbol{x_{2}}$ |  $x_{0}$ |  $x_{1}$
$y_{5}$ |  $x_{1}$ |  $x_{2}$ |  $\boldsymbol{x_{3}}$ |  $\boldsymbol{x_{4}}$ |  $\boldsymbol{x_{5}}$ |  $x_{3}$ |  $x_{4}$ |  $x_{5}$ |  $\boldsymbol{x_{0}}$ |  $\boldsymbol{x_{1}}$ |  $\boldsymbol{x_{2}}$ |  $x_{0}$
Table 2:  Extending the normal super-game from $U_{i}=$
$\\{\\{x_{0},x_{1},x_{2}\\},\\{x_{3},x_{4},x_{5}\\}\\}$ to
$U_{j}=\\{\\{y_{0},y_{1},y_{2}\\}$, $\\{y_{3},y_{4},y_{5}\\}\\}$ into normal
games on $2kd=12$ days, where home normal games are marked in bold

We can see that every normal team in $U_{i}$ will play $d$ away trips along
the $d$ $k$-paths in $U_{j}$, and every normal team in $U_{j}$ will play $d$
or $d+1$ away trips along at least $d-1$ $k$-paths in $U_{i}$. Moreover, all
games are arranged between one team in $U_{i}$ and one in $U_{j}$. Note that
this construction was also used in [13].

Left super-games: Then, we consider a left super-game from super-teams $U_{i}$
to $U_{j}$. Assume that
$U_{i}=\\{\\{x_{0},\dots,x_{k-1}\\},\\{x_{kd-k},\dots,x_{kd-1}\\}\\}$ and
$U_{j}=\\{\\{y_{0},\dots,y_{k-1}\\},\\{y_{kd-k},\dots,y_{kd-1}\\}\\}$. The
extension is easy to present. For all normal teams in $U_{i}$ and $U_{j}$, we
define matches $s_{i}=\\{x_{i^{\prime}}\rightarrow y_{(kd+i-i^{\prime})\bmod
kd}\\}_{i^{\prime}=0}^{kd-1}$, and also let $\overline{s_{i}}$ denote the case
that the game venues in $s_{i}$ are reversed. We directly extend the left
super-game into normal games on $2kd$ days in the following way:

$s_{0}\overline{s_{1}}s_{2}\overline{s_{3}}\cdots
s_{kd-2}\overline{s_{kd-1}}\cdot\overline{s_{0}\overline{s_{1}}s_{2}\overline{s_{3}}\cdots
s_{kd-2}\overline{s_{kd-1}}}.$

An illustration of the normal games after extending one normal super-game for
$k=3$ and $d=2$ is shown in Table 3. All games between one team in $U_{i}$ and
one in $U_{j}$ are arranged.

|  $0$ |  $1$ |  $2$ |  $3$ |  $4$ |  $5$ |  $6$ |  $7$ |  $8$ |  $9$ |  $10$ |  $11$
---|---|---|---|---|---|---|---|---|---|---|---|---
$x_{0}$ |  $y_{0}$ |  $\boldsymbol{y_{1}}$ |  $y_{2}$ |  $\boldsymbol{y_{3}}$ |  $y_{4}$ |  $\boldsymbol{y_{5}}$ |  $\boldsymbol{y_{0}}$ |  $y_{1}$ |  $\boldsymbol{y_{2}}$ |  $y_{3}$ |  $\boldsymbol{y_{4}}$ |  $y_{5}$
$x_{1}$ |  $y_{5}$ |  $\boldsymbol{y_{0}}$ |  $y_{1}$ |  $\boldsymbol{y_{2}}$ |  $y_{3}$ |  $\boldsymbol{y_{4}}$ |  $\boldsymbol{y_{5}}$ |  $y_{0}$ |  $\boldsymbol{y_{1}}$ |  $y_{2}$ |  $\boldsymbol{y_{3}}$ |  $y_{4}$
$x_{2}$ |  $y_{4}$ |  $\boldsymbol{y_{5}}$ |  $y_{0}$ |  $\boldsymbol{y_{1}}$ |  $y_{2}$ |  $\boldsymbol{y_{3}}$ |  $\boldsymbol{y_{4}}$ |  $y_{5}$ |  $\boldsymbol{y_{0}}$ |  $y_{1}$ |  $\boldsymbol{y_{2}}$ |  $y_{3}$
$x_{3}$ |  $y_{3}$ |  $\boldsymbol{y_{4}}$ |  $y_{5}$ |  $\boldsymbol{y_{0}}$ |  $y_{1}$ |  $\boldsymbol{y_{2}}$ |  $\boldsymbol{y_{3}}$ |  $y_{4}$ |  $\boldsymbol{y_{5}}$ |  $y_{0}$ |  $\boldsymbol{y_{1}}$ |  $y_{2}$
$x_{4}$ |  $y_{2}$ |  $\boldsymbol{y_{3}}$ |  $y_{4}$ |  $\boldsymbol{y_{5}}$ |  $y_{0}$ |  $\boldsymbol{y_{1}}$ |  $\boldsymbol{y_{2}}$ |  $y_{3}$ |  $\boldsymbol{y_{4}}$ |  $y_{5}$ |  $\boldsymbol{y_{0}}$ |  $y_{1}$
$x_{5}$ |  $y_{1}$ |  $\boldsymbol{y_{2}}$ |  $y_{3}$ |  $\boldsymbol{y_{4}}$ |  $y_{5}$ |  $\boldsymbol{y_{0}}$ |  $\boldsymbol{y_{1}}$ |  $y_{2}$ |  $\boldsymbol{y_{3}}$ |  $y_{4}$ |  $\boldsymbol{y_{5}}$ |  $y_{0}$
$y_{0}$ |  $\boldsymbol{x_{0}}$ |  $x_{1}$ |  $\boldsymbol{x_{2}}$ |  $x_{3}$ |  $\boldsymbol{x_{4}}$ |  $x_{5}$ |  $x_{0}$ |  $\boldsymbol{x_{1}}$ |  $x_{2}$ |  $\boldsymbol{x_{3}}$ |  $x_{4}$ |  $\boldsymbol{x_{5}}$
$y_{1}$ |  $\boldsymbol{x_{5}}$ |  $x_{0}$ |  $\boldsymbol{x_{1}}$ |  $x_{2}$ |  $\boldsymbol{x_{3}}$ |  $x_{4}$ |  $x_{5}$ |  $\boldsymbol{x_{0}}$ |  $x_{1}$ |  $\boldsymbol{x_{2}}$ |  $x_{3}$ |  $\boldsymbol{x_{4}}$
$y_{2}$ |  $\boldsymbol{x_{4}}$ |  $x_{5}$ |  $\boldsymbol{x_{0}}$ |  $x_{1}$ |  $\boldsymbol{x_{2}}$ |  $x_{3}$ |  $x_{4}$ |  $\boldsymbol{x_{5}}$ |  $x_{0}$ |  $\boldsymbol{x_{1}}$ |  $x_{2}$ |  $\boldsymbol{x_{3}}$
$y_{3}$ |  $\boldsymbol{x_{3}}$ |  $x_{4}$ |  $\boldsymbol{x_{5}}$ |  $x_{0}$ |  $\boldsymbol{x_{1}}$ |  $x_{2}$ |  $x_{3}$ |  $\boldsymbol{x_{4}}$ |  $x_{5}$ |  $\boldsymbol{x_{0}}$ |  $x_{1}$ |  $\boldsymbol{x_{2}}$
$y_{4}$ |  $\boldsymbol{x_{2}}$ |  $x_{3}$ |  $\boldsymbol{x_{4}}$ |  $x_{5}$ |  $\boldsymbol{x_{0}}$ |  $x_{1}$ |  $x_{2}$ |  $\boldsymbol{x_{3}}$ |  $x_{4}$ |  $\boldsymbol{x_{5}}$ |  $x_{0}$ |  $\boldsymbol{x_{1}}$
$y_{5}$ |  $\boldsymbol{x_{1}}$ |  $x_{2}$ |  $\boldsymbol{x_{3}}$ |  $x_{4}$ |  $\boldsymbol{x_{5}}$ |  $x_{0}$ |  $x_{1}$ |  $\boldsymbol{x_{2}}$ |  $x_{3}$ |  $\boldsymbol{x_{4}}$ |  $x_{5}$ |  $\boldsymbol{x_{0}}$
Table 3:  Extending the left super-game from $U_{i}=$
$\\{\\{x_{0},x_{1},x_{2}\\},\\{x_{3},x_{4},x_{5}\\}\\}$ to
$U_{j}=\\{\\{y_{0},y_{1},y_{2}\\}$, $\\{y_{3},y_{4},y_{5}\\}\\}$ into normal
games on $2kd=12$ days, where home normal games are marked in bold

######  Lemma 9.

There are no more than $k$-consecutive home/away games in the first $m^{2}-1$
time slots.

###### Proof.

We use ‘A’ and ‘H’ to denote an away game and a home game, respectively.

By the design of left and normal super-games, it is clear that games in each
time slot satisfy the constraint. Assume that there are more than
$k$-consecutive home/away games for team $t_{i}$ at the joint of time slots
$Q$ and $Q+1$. Recall that the states of each team on days $2i-1$ and $2i$ in
each left super-game are AH or HA. So, team $t_{i}$ cannot be from super-team
$U_{m^{2}}$ since $U_{m^{2}}$ always plays left super-games. Assume that team
$t_{i}$ is from super-team $U_{i^{\prime}}$ ($i^{\prime}\neq m$). Moreover,
there should be a normal super-game for $U_{i^{\prime}}$ in time slot $Q$ or
$Q+1$. For the sake of presentation, we use $L$ and $N$ (resp., $\overline{L}$
and $\overline{N}$) to indicate an away (resp, a home) left and normal super-
game of super-team $U_{i^{\prime}}$. According to the rotation scheme of the
construction, there are six cases for the super-games of super-team
$U_{i^{\prime}}$ in time slots $Q$ and $Q+1$: $NL$, $NN$, $\overline{L}N$, and
$\overline{NL}$, $\overline{NN}$, $\overline{\overline{L}N}$. Note that the
first three cases are symmetrical with the last three. It is sufficient to
consider the first three cases. In an away normal super-game, team $t_{i}$
plays $k^{\prime}$-consecutive homes games on the first $k^{\prime}$ days and
$(k-k^{\prime})$-consecutive homes games on the last $k-k^{\prime}$ days where
$0\leq k^{\prime}\leq k-1$ depending on the position of $t_{i}$ in the
$k$-path. For the joint of $NL$, since the states of $t_{i}$ are AH on the
first two days of $L$, there are no consecutive home/away games. For the joint
of $NN$, there are exactly $k$-consecutive home games. For the joint of
$\overline{L}N$, since the states of $t_{i}$ are AH on the last two days of
$\overline{L}$, there are at most $k^{\prime}+1\leq k$ consecutive home games.
Therefore, two consecutive time slots cannot create more than $k$-consecutive
home/away games. ∎

At last, we are ready to design games in the last time slot. Recall that in a
normal/left super-game between super-teams $U_{i}$ and $U_{j}$, all games
between one team in $U_{i}$ and one in $U_{j}$ are arranged. Moreover, it is
well-known that the rotation scheme of the construction can make sure any pair
of $m^{2}$ super-teams meets exactly once in the first $m^{2}-1$ time slot.
Hence, the unarranged games are games within each super-team. The unarranged
games within each super-team can be seen as a double round-robin on $m$ teams
(recall that $m$ is even). To arrange them, we will simply call a TTP-2
algorithm. Clearly, there would be no more than $2$-consecutive home/away
games in the last time slot. We also need to make sure that there are no more
than $k$-consecutive home/away games between the last two time slots. So, we
will use a special TTP-2 algorithm where every team plays AH or HA on the
first two days.

######  Lemma 10.

There is a special TTP-2 algorithm where every team plays AH or HA on the
first two days.

###### Proof.

Assume that there are $m=6$ teams in a super-team, denoted by
$\\{1,2,3,4,5,6\\}$. We show a construction satisfying the above property.
Moreover, we will show that it is easy to generalize for a larger number of
teams.

$6$$1$$2$$5$$3$$4$

(a) The first day

$6$$5$$1$$4$$2$$3$

(b) The second day

$6$$4$$5$$3$$1$$2$

(c) The third day

Figure 5: An illustration of the special TTP-2 algorithm, where we only show
the first three days for $m=6$ teams

The framework of the special TTP-2 algorithm is similar to the construction of
super-teams. The last team is denoted by a double-cycle node, and the other
teams are single-cycle nodes. On the first day (see (a) in Figure 5), except
for the most left edge, the directions of edges alternatively change from left
to right. On the next day, we change the positions of white nodes in the cycle
$12345$ by moving one position in the clockwise direction, but we only change
the direction of the most left edge. The third day is obtained by the same
rule. Based on this, we can obtain the games on the first $m-1$ days. Let
$\Gamma_{i}$ denote the games on $i$-th day, and $\overline{\Gamma_{i}}$
denote the games on $i$-th day but with venues reversed, then the complete
double round-robin can be presented by

$\Gamma_{1}\cdot\Gamma_{2}\cdots\Gamma_{m-2}\cdot\Gamma_{m-1}\cdot\overline{\Gamma_{m-2}\cdot\Gamma_{m-1}\cdot\Gamma_{1}\cdot\Gamma_{2}\cdots\Gamma_{m-3}}.$

See Table 4 for an illustration of the complete double round-robin.

|  $0$ |  $1$ |  $2$ |  $3$ |  $4$ |  $5$ |  $6$ |  $7$ |  $8$ |  $9$
---|---|---|---|---|---|---|---|---|---|---
$1$ |  $\boldsymbol{6}$ |  $4$ |  $\boldsymbol{2}$ |  $5$ |  $\boldsymbol{3}$ |  $\boldsymbol{5}$ |  $3$ |  $6$ |  $\boldsymbol{4}$ |  $2$
$2$ |  $5$ |  $\boldsymbol{3}$ |  $1$ |  $\boldsymbol{4}$ |  $\boldsymbol{6}$ |  $4$ |  $6$ |  $\boldsymbol{5}$ |  $3$ |  $\boldsymbol{1}$
$3$ |  $\boldsymbol{4}$ |  $2$ |  $\boldsymbol{5}$ |  $6$ |  $1$ |  $\boldsymbol{6}$ |  $\boldsymbol{1}$ |  $4$ |  $\boldsymbol{2}$ |  $5$
$4$ |  $3$ |  $\boldsymbol{1}$ |  $\boldsymbol{6}$ |  $2$ |  $\boldsymbol{5}$ |  $\boldsymbol{2}$ |  $5$ |  $\boldsymbol{3}$ |  $1$ |  $6$
$5$ |  $\boldsymbol{2}$ |  $6$ |  $3$ |  $\boldsymbol{1}$ |  $4$ |  $1$ |  $\boldsymbol{4}$ |  $2$ |  $\boldsymbol{6}$ |  $\boldsymbol{3}$
$6$ |  $1$ |  $\boldsymbol{5}$ |  $4$ |  $\boldsymbol{3}$ |  $2$ |  $3$ |  $\boldsymbol{2}$ |  $\boldsymbol{1}$ |  $5$ |  $\boldsymbol{4}$
Table 4: An illustration of the special TTP-2 algorithm for $m=6$ teams on
$2m-2=10$ days, where home games are marked in bold

The construction can be seen as a simple variant of TTP-2 construction in
[20]. It is easy to verify that the double round-robin is feasible for TTP-2.
Moreover, every team plays AH or HA on the first two days (see Figure 5 or
Table 4). Specifically, half teams play AH and half play HA on the first two
days.

To generalize the construction for two larger number of teams, we can simply
put the teams on the most right position using an edge with a different
direction. By induction, we can generalize the construction for any even
larger number of teams. ∎

Then, we use the special TTP-2 algorithm to design the unarranged games for
each super-team. Consider a super-team $U_{i}$. If $U_{i}$ plays a left super-
game, we know that all teams play AH or HA on the last two days in the
$m^{2}-1$ time slot. By arbitrarily calling the special TTP-2 algorithm, every
team plays AH or HA on the first two days in the last time slot. So, these two
time slots cannot create more than $k$-consecutive home/away games. If $U_{i}$
plays an away (resp., home) normal super-game, there are $m/k$ teams playing
$k$-consecutive home (resp., away) games and $m-m/k$ teams play
$k^{\prime}$-consecutive home (resp., away) games on the last $k^{\prime}$
days in the $m^{2}-1$ time slot. To avoid creating more than $k$-consecutive
home/away games, we can carefully call the special TTP-2 algorithm such that
the $m/k<m/2$ teams play AH (resp., HA) (and each of the other $m-m/k$ teams
will play AH or HA) on the first two days in the last time slot. This is
feasible since there are exactly a half number ($m/2$) of teams playing AH and
a half number of teams playing HA on the first two days of the special TTP-2
double round-robin. So, there are no more than $k$-consecutive home/away games
between the last two time slots. Moreover, by Lemma 9, we have the following
lemma.

######  Lemma 11.

There are no more than $k$-consecutive home/away games in the construction.

######  Theorem 12.

Given instance $J$, the above construction generates a feasible solution for
TTP-$k$.

###### Proof.

First, the solution is a complete double round-robin since two games between a
pair of teams are arranged entirely in either a super-game or the TTP-2 double
round-robin. Moreover, by the design of super-games and the definition of
TTP-2 double round-robin, the games are not arranged on two consecutive days.
So, the solution satisfies the no-repeat constraint. Last, by Lemma 11, the
solution also satisfies the bounded-by-$k$ constraint. ∎

###  5.2 The quality of the schedule

To analyze the quality, we calculate the weight of the itinerary for each
team, i.e., the traveling distance for each team.

Case 1. First, we consider teams in $U_{i}\in\\{U_{2},\dots,U_{m^{2}}\\}$. In
each of the first $m^{2}-1$ time slots, $U_{i}$ plays an away normal super-
game with $U_{1}$. By the design of normal super-games, all teams in $U_{i}$
play $d$ $k$-consecutive away games along the $d$ $k$-paths in $U_{1}$.
Moreover, all teams are at home before the first game starts and after the
last game ends in the away normal super-game. Hence, for each team, the trips
of games in the super-game form a sub-itinerary. Recall that teams in $U_{i}$
are all dummy teams with positions on the depot. So, each team has a sub-
itinerary same as the optimal saturated solution in $I^{\prime}$ and hence has
a traveling distance of $\mbox{OPT}(I^{\prime})=\mbox{OPT}(I)$. Note that the
other sub-itineraries for visiting teams in $U_{i^{\prime}}$ ($i^{\prime}\neq
1$) have a zero weight since all teams in super-teams of
$\\{U_{2},\dots,U_{m^{2}}\\}$ are dummy teams on the same position. Therefore,
these $m(m^{2}-1)$ dummy teams have a total traveling distance of
$m(m^{2}-1)\cdot\mbox{OPT}(I)$.

Case 2. Then, we consider teams in $U_{1}$. For the sake of analysis, we
assume that all teams in $U_{1}$ return home after the last game ends in the
$m^{2}-1$ time slot. So, it will split the itinerary of each team into two
parts without decreasing the weight by the triangle inequality. Next, we
consider a team $x$ in $U_{1}$.

Case 2.1. We first consider the first part of its itinerary, i.e., the trips
due to the games in the first $m^{2}-1$ time slots. Note that $U_{1}$ plays
$m^{2}-1$ home normal super-games in the construction. By the design of normal
super-games, it will first play $k^{\prime}$-consecutive away games ($0\leq
k^{\prime}<k$), then repeat $k$-consecutive home games with $k$-consecutive
home games, and last play $(k-k^{\prime})$-consecutive away games. Hence,
combining all these $m^{2}-1$ home normal games, we know that $x$ plays
exactly $d(m^{2}-1)$ trips if $k^{\prime}=0$ and $d(m^{2}-1)+1$ trips
otherwise. Again, the trips are all for dummy teams, and hence each trip has a
weight of $2w(o,x)$. Since each team in $U_{1}$ corresponds to a vertex in
$V_{I^{\prime}}\setminus\\{o\\}$, teams in $U_{1}$ have a total traveling
distance of at most $2(d(m^{2}-1)+1)\sum_{x\in V_{I^{\prime}}}w(o,x)$. Recall
that $I^{\prime}$ is obtained by adding some vertices on the depot of $I$. So,
we have $\sum_{x\in V_{I^{\prime}}}w(o,x)=\sum_{x\in V_{I}}w(o,x)$. Then, we
have

$2(d(m^{2}-1)+1)\sum_{x\in V_{I^{\prime}}}w(o,x)=2(d(m^{2}-1)+1)\sum_{x\in
V_{I}}w(o,x)=2d(m^{2}-1)\sum_{x\in V_{I}}w(o,x)+2\sum_{x\in V_{I}}w(o,x).$

Case 2.2. We then consider the second part of its itinerary, i.e., the trips
due to the games in the last time slots. Recall that in the last time slot we
simply call a TTP-2 algorithm for teams in $U_{1}$. In the worst case, team
$x$ visits other $m-1$ teams using $m-1$ trips by the triangle inequality,
i.e., each trip visits only a single team. Hence, teams in $U_{1}$ have a
total traveling distance of at most $2\sum_{x\in V_{I^{\prime}}}\sum_{y\in
V_{I^{\prime}}}w(x,y)$. By the triangle inequality, we can get

$2\sum_{x\in V_{I^{\prime}}}\sum_{y\in V_{I^{\prime}}}w(x,y)\leq 2\sum_{x\in
V_{I^{\prime}}}\sum_{y\in V_{I^{\prime}}}(w(o,x)+w(o,y))=4(m+1)\sum_{x\in
V_{I^{\prime}}}w(o,x)=4(m+1)\sum_{x\in V_{I}}w(o,x),$

where the first equation follows from that there is 1 depot vertex and $m$
non-depot vertices in $I^{\prime}$, and the second follows from that
$I^{\prime}$ is obtained by adding some vertices on the depot of $I$.

Therefore, the schedule has a weight of at most
$m(m^{2}-1)\cdot\mbox{OPT}(I)+2d(m^{2}-1)\sum_{x\in
V_{I}}w(o,x)+(4m+6)\sum_{x\in V_{I}}w(o,x)$.

######  Lemma 13.

There exists a constant $\alpha>0$ such that $\mbox{OPT}(J)\leq\alpha\cdot
m(m^{2}-1)\cdot\mbox{OPT}(I)$.

###### Proof.

Given an instance $I$ of Restricted $k$-TC, our construction shows that

$\mbox{OPT}(J)\leq m(m^{2}-1)\cdot\mbox{OPT}(I)+2d(m^{2}-1)\sum_{x\in
V_{I}}w(o,x)+(4m+6)\sum_{x\in V_{I}}w(o,x).$

By Definition 4 and Lemma 5, we have $\sum_{x\in V_{I}}w(o,x)=\Theta(n)$ and
$\mbox{OPT}(I)=\Theta(n)$. Moreover, since $d=m/k$ and $m=\Theta(n)$, we can
get

$m(m^{2}-1)\cdot\mbox{OPT}(I)+2d(m^{2}-1)\sum_{x\in
V_{I}}w(o,x)+(4m+6)\sum_{x\in
V_{I}}w(o,x)=\Theta(m(m^{2}-1)\cdot\mbox{OPT}(I)).$

So, there exists a constant $\alpha>0$ such that $\mbox{OPT}(J)\leq\alpha\cdot
m(m^{2}-1)\cdot\mbox{OPT}(I)$. ∎

##  6 The Third Property

In this section, we prove the last property of the L-reduction in Definition
1. Given a solution $S(J)$ of instance $J$, we first show how to construe a
solution $S(I)$ of instance $I$ in polynomial time.

Denote the itinerary of each team $x\in V_{J}$ in $S(J)$ by $T_{x}$ and the
traveling distance by $w(T_{x})$. Recall that there are $m(m^{2}-1)$ dummy
teams with their positions on the depot, denoted by $D_{J}$. Consider a dummy
team $x\in D_{J}$. By shortcutting all vertices on the depot except for
itself, we obtain a solution of $I$, denoted by $S_{x}(I)$, since instance $J$
is obtained by adding some vertices on the depot of instance $I$ (see Figure
1). Note that $S_{x}(I)=w(T_{x})$ since $x$ is also on the depot. We can
obtain a solution $S(I)$ of instance $I$ by choosing the best one from
$\\{S_{x}(I)\mid x\in D_{J}\\}$, which clearly takes polynomial time. So, we
have the following lemma.

######  Lemma 14.

Given a solution $S(J)$ of instance $J$, we can construe a solution $S(I)$ of
instance $I$ in polynomial time.

Note that we also have

$\sum_{x\in D_{J}}w(T_{x})=\sum_{x\in D_{J}}S_{x}(I)\geq m(m^{2}-1)\cdot
S(I).$

Next, we consider a non-dummy team $x\in V_{J}\setminus D_{J}$. In its
itinerary $T_{x}$, it uses at least $m(m^{2}-1)/k=d(m^{2}-1)$ trips to visit
all dummy teams. So, we can get $w(T_{x})\geq 2d(m^{2}-1)w(o,x)$ by the
triangle inequality. Then, we have

$\sum_{x\in V_{J}\setminus D_{J}}w(T_{x})\geq 2d(m^{2}-1)\sum_{x\in
V_{I}}w(o,x).$

Therefore, we have

$S(J)=\sum_{x\in D_{J}}w(T_{x})+\sum_{x\in V_{J}\setminus D_{J}}w(T_{x})\geq
m(m^{2}-1)\cdot S(I)+2d(m^{2}-1)\sum_{x\in V_{I}}w(o,x).$

######  Lemma 15.

There exists a constant $\beta>0$ such that

$m(m^{2}-1)\cdot(S(I)-\mbox{OPT}(I))\leq\beta\cdot(S(J)-\mbox{OPT}(J)).$

###### Proof.

Previously, we have shown that $S(J)\geq m(m^{2}-1)\cdot
S(I)+2d(m^{2}-1)\sum_{x\in V_{I}}w(o,x)$. Recall that $\mbox{OPT}(J)\leq
m(m^{2}-1)\cdot\mbox{OPT}(I)+2d(m^{2}-1)\sum_{x\in
V_{I}}w(o,x)+(4m+6)\sum_{x\in V_{I}}w(o,x)$. Then, we can get

$S(J)-\mbox{OPT}(J)\geq m(m^{2}-1)\cdot(S(I)-\mbox{OPT}(I))-(4m+6)\sum_{x\in
V_{I}}w(o,x).$

We assume w.l.o.g. that $S(I)>\mbox{OPT}(I)$; otherwise, the lemma holds
trivially. By Definition 4, we have $S(I)-\mbox{OPT}(I)=\Omega(1)$. So,
$m(m^{2}-1)\cdot(S(I)-\mbox{OPT}(I))=\Omega(n^{3})$. Recall that
$(4m+6)\sum_{x\in V_{I}}w(o,x)=\Theta(n^{2})$. Then, we have

$m(m^{2}-1)\cdot(S(I)-\mbox{OPT}(I))-(4m+6)\sum_{x\in
V_{I}}w(o,x)=\Theta(m(m^{2}-1)\cdot(S(I)-\mbox{OPT}(I))).$

So, there exists a constant $\beta>0$ such that
$m(m^{2}-1)\cdot(S(I)-\mbox{OPT}(I))\leq\beta\cdot(S(J)-\mbox{OPT}(J))$. ∎

Theorem 2 directly follows from Lemmas 8, 13, 14 and 15.

##  7 Conclusion

Previously, it is known that TTP-$k$ allows a PTAS when $k=2$ and is APX-hard
when $k\geq n-1$. To make the complexity status clear, we further show that
TTP-$k$ is APX-hard for any fixed $k\geq 3$. Our hardness result, instead of
using $k$-SAT, is reduced from the $k$-Tour Cover problem, which also provides
an alternative proof for the NP-hardness of TTP-$k$ with any fixed $k\geq 3$.

## Acknowledgments

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

## Declaration of competing interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## References

  * [1] Tetsuo Asano, Naoki Katoh, Hisao Tamaki, and Takeshi Tokuyama.  Covering points in the plane by k-tours: a polynomial approximation scheme for fixed k.  IBM Tokyo Research Laboratory Research Report RT0162, 1996.
  * [2] Tetsuo Asano, Naoki Katoh, Hisao Tamaki, and Takeshi Tokuyama.  Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k.  In STOC 1997, pages 275–283, 1997.
  * [3] Salomon Bendayan, Joseph Cheriyan, and Kevin K. H. Cheung.  Unconstrained traveling tournament problem is apx-complete.  CoRR, abs/2212.09165, 2022.
  * [4] Rishiraj Bhattacharyya.  Complexity of the unconstrained traveling tournament problem.  Operations Research Letters, 44(5):649–654, 2016.
  * [5] David Van Bulck, Dries R. Goossens, Jörn Schönberger, and Mario Guajardo.  Robinx: A three-field classification and unified data format for round-robin sports timetabling.  Eur. J. Oper. Res., 280(2):568–580, 2020.
  * [6] Diptendu Chatterjee.  Complexity of traveling tournament problem with trip length more than three.  CoRR, abs/2110.02300, 2021.
  * [7] Diptendu Chatterjee and Bimal Kumar Roy.  An improved scheduling algorithm for traveling tournament problem with maximum trip length two.  In ATMOS 2021, volume 96, pages 16:1–16:15, 2021.
  * [8] Pierluigi Crescenzi.  A short guide to approximation preserving reductions.  In Proceedings of Computational Complexity. Twelfth Annual IEEE Conference, pages 262–273. IEEE, 1997.
  * [9] Dominique de Werra.  Some models of graphs for scheduling sports competitions.  Discrete Applied Mathematics, 21(1):47–65, 1988.
  * [10] Guillermo Durán.  Sports scheduling and other topics in sports analytics: a survey with special reference to latin america.  Top, 29(1):125–155, 2021.
  * [11] Kelly Easton, George Nemhauser, and Michael Trick.  The traveling tournament problem: description and benchmarks.  In 7th International Conference on Principles and Practice of Constraint Programming, pages 580–584, 2001.
  * [12] Richard Hoshino and Ken-ichi Kawarabayashi.  Generating approximate solutions to the TTP using a linear distance relaxation.  J. Artif. Intell. Res., 45:257–286, 2012.
  * [13] Richard Hoshino and Ken-ichi Kawarabayashi.  An approximation algorithm for the bipartite traveling tournament problem.  Mathematics of Operations Research, 38(4):720–728, 2013.
  * [14] Shinji Imahori.  A 1+O(1/N) approximation algorithm for TTP(2).  CoRR, abs/2108.08444, 2021.
  * [15] Shinji Imahori, Tomomi Matsui, and Ryuhei Miyashiro.  A 2.75-approximation algorithm for the unconstrained traveling tournament problem.  Annals of Operations Research, 218(1):237–247, 2014.
  * [16] Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan.  A (slightly) improved approximation algorithm for metric TSP.  In STOC 2021, pages 32–45, 2021.
  * [17] Graham Kendall, Sigrid Knust, Celso C Ribeiro, and Sebastián Urrutia.  Scheduling in sports: An annotated bibliography.  Computers & Operations Research, 37(1):1–19, 2010.
  * [18] Ryuhei Miyashiro, Tomomi Matsui, and Shinji Imahori.  An approximation algorithm for the traveling tournament problem.  Annals of Operations Research, 194(1):317–324, 2012.
  * [19] Clemens Thielen and Stephan Westphal.  Complexity of the traveling tournament problem.  Theoretical Computer Science, 412(4):345–351, 2011.
  * [20] Clemens Thielen and Stephan Westphal.  Approximation algorithms for TTP(2).  Mathematical Methods of Operations Research, 76(1):1–20, 2012.
  * [21] Stephan Westphal and Karl Noparlik.  A 5.875-approximation for the traveling tournament problem.  Annals of Operations Research, 218(1):347–360, 2014.
  * [22] David P Williamson and David B Shmoys.  The design of approximation algorithms.  Cambridge university press, 2011.
  * [23] Mingyu Xiao and Shaowei Kou.  An improved approximation algorithm for the traveling tournament problem with maximum trip length two.  In MFCS 2016, volume 58, pages 89:1–89:14, 2016.
  * [24] Daisuke Yamaguchi, Shinji Imahori, Ryuhei Miyashiro, and Tomomi Matsui.  An improved approximation algorithm for the traveling tournament problem.  Algorithmica, 61(4):1077–1091, 2011.
  * [25] Jingyang Zhao and Mingyu Xiao.  A further improvement on approximating TTP-2.  In COCOON 2021, volume 13025 of Lecture Notes in Computer Science, pages 137–149, 2021.
  * [26] Jingyang Zhao and Mingyu Xiao.  The traveling tournament problem with maximum tour length two: A practical algorithm with an improved approximation bound.  In IJCAI 2021, pages 4206–4212, 2021.
  * [27] Jingyang Zhao and Mingyu Xiao.  Practical algorithms with guaranteed approximation ratio for TTP with maximum tour length two.  CoRR, abs/2212.12240, 2022.
  * [28] Jingyang Zhao and Mingyu Xiao.  The linear distance traveling tournament problem allows an eptas.  In AAAI 2023, pages 12155–12162. AAAI Press, 2023.
  * [29] Jingyang Zhao, Mingyu Xiao, and Chao Xu.  Improved approximation algorithms for the traveling tournament problem.  In MFCS 2022,, volume 241 of LIPIcs, pages 83:1–83:15, 2022\.
  * [30] 浅野哲夫, 加藤直樹, 玉木久夫, 徳山豪, et al.  平面点集合の k 巡回路被覆問題: k が定数の場合の多項式時間近似スキーム.  情報処理学会研究報告アルゴリズム (AL), 1996(89 (1996-AL-053)):79–86, 1996.


# RAFIC: Retrieval-Augmented Few-shot Image Classification

Hangfei Lin Li Miao Amir Ziai
Stanford University
{hangfei, limiao<EMAIL_ADDRESS>

##  1 Extended Abstract

Few-shot image classification is the task of classifying unseen images to one
of $N$ mutually exclusive classes, using only a small number of training
examples for each class. The limited availability of these examples (denoted
as $K$) presents a significant challenge to classification accuracy in some
cases.

To address this, we have developed a method for augmenting the set of $K$ with
an addition set of $A$ retrieved images. We call this system Retrieval-
Augmented Few-shot Image Classification (RAFIC).

Through a series of experiments, we demonstrate that RAFIC markedly improves
performance of few-shot image classification across two challenging datasets.
RAFIC consists of two main components: (a) a retrieval component which uses
CLIP Schuhmann et al. (2022), LAION-5B Schuhmann et al. (2022), and faiss
Johnson et al. (2019), in order to efficiently retrieve images similar to the
supplied images, and (b) retrieval meta-learning, which learns to judiciously
utilize the retrieved images. Code and data is available at
github.com/amirziai/rafic.

###  1.1 Key Findings

  1. 1.

Using CLIP embeddings leads to vastly superior performance vs. raw pixels. We
show that using CLIP Radford et al. (2021) embeddings as input features
significantly surpasses the performance of raw pixels. For instance, we see
accuracy increase from 0.26 to 0.88 in the 10-way rare bird classification
task.

  2. 2.

Zero-shot retrieval using class names is highly effective. We also found that
zero-shot retrieval using class names text embedding is highly effective,
achieving over 96% accuracy in 10-way bird classification, surpassing other
methods and showcasing CLIP’s familiarity with certain concepts over others.

  3. 3.

Efficient retrieval-augmentations leads to a boost in accuracy. The addition
of retrieved images significantly improved model accuracy in two challenging
few-shot tasks compared to a baseline of logistic regression without meta-
training or augmentation. Using Approximate Nearest Neighbors (ANN) search via
faiss Johnson et al. (2019), we have enabled real-time retrieval and
representation extraction across LAION-5B, a repository of 5B+ images.

  4. 4.

Meta-learning the retrieval strategy further boosts accuracy. We demonstrate
that accuracy can be further improved by using coarse (up or downweighting
retrieval as a whole) and fine-grained (up or downweighting individual
retrieved images) strategies for meta-learning the retrieval strategy.

  5. 5.

MAML is more adept at adaptation than ProtoNet. Training on one task and
evaluating on another (cross-evaluation) showed that MAML Chen et al. (2021)
adapts well relative to ProtoNet Snell et al. (2017). Moreover, inclusion of
more retrieval images helped with further closing of the performance gap.

Overall, our research validates that retrieval and meta-learning approaches
boost performance in few-shot image classification, particularly in cross-task
evaluation settings.

##  2 Introduction

Figure 1: Overview of our proposed system Retrieval-Augmented Few-shot Image
Classification (RAFIC). The top diagram shows the high-level view and the
bottom one shows the details of the retriever. The top diagram depicts 2-way
($N=2$) classification of aircraft variants. For each class, we provide 1
support image ($K=1$) and ask the model to classify 1 query image ($Q=1$). The
retriever uses support images and class labels to retrieve 3 ($A=3$)
additional images images. We then concatenate image CLIP embeddings from both
support and retrieved images and use that for model training. The model is
evaluated on correctly predicting the labels of the query images. Retrieval is
done for each class label. We use the CLIP text encoder to embed the class
name ($E_{T}$). We then extract image embeddings for each support image using
CLIP, and take the mean ($E_{S}$). We retrieve the top-$A$ images from
LAION-5B using a faiss index and use
$E_{Q}=\alpha_{T}E_{T}+(1-\alpha_{T})E_{S}$ as the query, where
$0\leq\alpha_{T}\leq 1$.

Few-shot image classificationDhillon et al. (2019) is a rapidly evolving
domain in machine learning, characterized by the challenge of training models
to accurately classify new images into a predefined set of categories, despite
the availability of only a limited number of samples per class. This approach
is especially valuable in fields where acquiring large datasets is impractical
or impossible, such as medical imaging Kotia et al. (2021), drug discovery
Vella and Ebejer (2022), and precision manufacturing Deshpande et al. (2020).
The ability to make accurate predictions from minimal data not only economizes
on the resources typically required for training conventional machine learning
models but also opens up new possibilities in areas where data is scarce or
expensive to acquire.

Our study centers on meta-learningVilalta and Drissi (2002), a leading
paradigm in solving few-shot image classification. This paradigm focuses on
training models that can effectively generalize to new tasks with sparse data.
Within this context, we explore various methodologies, including metric-based
approaches like ProtoNetSnell et al. (2017), known for producing feature
embeddings through metric learning, and non-metric-based methods such as
MAMLFinn et al. (2017), which utilizes gradient-based strategies for model
parameter optimization. However, these techniques are often limited by the
data scarcity challenge inherent in few-shot scenarios.

To mitigate this limitation, data augmentationNi et al. (2021) has emerged as
a popular strategy. This encompasses a range of techniques like image flips,
crops, patch erasures, and the introduction of image noiseShorten and
Khoshgoftaar (2019). Furthermore, advanced methods such as generating new
images via feature space interpolationKhodadadeh et al. (2020) or using
generative models are being exploredBowles et al. (2018). Variations in data
augmentation, including augmenting either the support or the query set, have
been extensively investigated in the literature Antoniou et al. (2017).

Our research explores the potential of employing an intelligent retrieval-
based data augmentation system. The system searches and fetch additional
relevant $A$ examples from external sources, thereby artificially expanding
the few-shot dataset from $K$ samples to a more robust size $K+A$.
Specifically, our system relies on the large-scale image-text dataset, LAION
Schuhmann et al. (2022). We use CLIP Radford et al. (2021) embedding and faiss
Johnson et al. (2019) for image featurization and relevant image retrieval, as
illustrated in Figure 1. By retrieving images that are contextually similar to
the few-shot examples, we can enrich the training dataset, thereby providing
the model with a more comprehensive learning base. We demonstrate that this
system can significantly enhance the classification performance of few-shot
image classifiers.

Another unique aspect of our approach involves meta-learning the retrieval
strategy. This includes adding attention on image similarity, adjusting
learning rates on retrieved data, and weighted loss computation. The goal is
for the model to discern the most beneficial images for use, a process we
believe leads to noticeable improvements. We further explored the
generalization capabilities of the models by cross-evaluation the models
against a complete different image dataset. We see some gains even in the
cross-evaluation scenarios.

The primary contribution of our work lies in introducing retrieval
augmentation to few-shot image classification, where we develop an end-to-end
system capable of utilizing LAION, faiss and CLIP for data augmentation.
Additionally, the meta-learning aspect of the retrieval strategy represents a
significant innovation. This methodology’s effectiveness across various
domains promises potential advancements in applying few-shot image
classification in real-world scenarios.

##  3 Related Work

Meta-learning aims to develop models that can quickly adapt to new tasks with
limited data and generalize effectively to unseen examples. Within this field,
two primary families of approaches have gained prominence: non-metric and
metric-based methods. Non-metric methods, exemplified by Model-Agnostic Meta-
Learning (MAML)Finn et al. (2017), optimize a model’s initial parameters for
rapid fine-tuning across diverse tasks. Metric-based approaches, such as
Prototypical NetworksSnell et al. (2017), learn a distance function for
classifying instances by comparing them to labeled examples in a support set.
Each approach addresses the challenge of adaptation and generalization in
unique ways: non-metric methods like MAML optimize for parameter flexibility,
while metric-based methods focus on learning effective similarity measures for
classification.

While both non-metric and metric-based meta-learning methods have shown
promise, they both grapple with the issue of data scarcity. Addressing this
challenge has become a focal point in both computer vision and natural
language processing (NLP) domains within the realm of meta-learning. A pivotal
strategy in this context is data augmentationNi et al. (2021), which has been
widely recognized for its effectiveness in enhancing meta-learning
performance. Our research contributes to this area, focusing on innovative
data augmentation techniques to mitigate the limitations posed by limited
datasets.

####  3.0.1 Meta-learning for image classification

Various innovative methods have been developed to overcome the challenge of
data scarcity in image classification.

Chen et al. (2021) attempt to mitigate the data scarcity problem by retrieving
additional images from a base dataset of unlabeled images. Retrieval of
similar images is done via training a linear classifier on the support images
and then using that classifier to retrieve images with the largest score. This
paper presents thorough ablation studies to tease out the impact of several
design decisions such as the number of augmented images and model
architecture. However, the authors do not experiment with different retrieval
strategies.

Zhang et al. (2022) leverage both visual and text CLIP Radford et al. (2021)
embeddings to fine-tune a module for improving classification. Similar to this
work, we plan to use CLIP as our base visual and textual encoder. However,
this work does not use retrieval-augmentation.

Zhang et al. (2019) present a novel approach to few-shot learning by
leveraging saliency-guided hallucination of samples. Their method segments
existing images into background and foreground components, which are then
reassembled to generate new, synthesized images. This technique is innovative
in its utilization of saliency information to enrich the learning dataset.
While the method shows promise, it inherently has limitations concerning the
diversity of synthesized samples. The performance tends to plateau as the
number of unique combinations derived from the background and foreground
segments is exhausted.

One notable approach is identified in Ni et al. (2021) where four distinct
modes of augmentation—query, support, task, and shot—are explored. This
research also introduces Meta-MaxUp, a method that combines various meta-
specific data augmentations, significantly enhancing the performance of
prevalent meta-learning algorithms without the need for additional images.

In supervised image classification, RAC Long et al. (2022) also explore the
idea of external augmentation to improve classification accuracy.

Our research builds upon these foundations, introducing retrieval augmentation
from large-scale image dataset to image classification in meta-learning. By
augmenting the training data and meta-learning the retrieval strategy, we
leverage insights from the aforementioned studies. Specifically, RAFIC
utilizes the LAION-5B dataset and CLIP embedding, incorporating image and
class text embedding for enhanced image retrieval, thus addressing the
critical challenges identified in the related work.

##  4 Methods

This section introduces our proposed method and details the components we have
leveraged.

###  4.1 Few-shot image classification

Few-shot image classification is the task of classifying $Q$ query images (per
class) belonging to $N$ mutually exclusive classes, given a few examples (i.e.
$K$) from each class. It differs from normal image classification in that $K$
is usually very small.

###  4.2 Proposed method: Retrieval-Augmented Few-shot Image Classification
(RAFIC)

Fig 1 depicts an overview of our proposed system RAFIC. We leverage a
retriever to augment the support set with $A$ additional images retrieved from
a large scale repository of images. We hypothesize that the inclusion of these
additional images, combined with strategies for meta-learning the retrieval
strategy, can improve classification accuracy.

###  4.3 CLIP for image and text encoding

OpenAI’s CLIP Radford et al. (2021) was trained on 400M+ image-text pairs. By
combining text and image encoders, CLIP learns a shared embedding space where
images and text can be directly compared. This makes clip highly efficient and
effective at zero-shot retrieval and image/text encoding. RAFIC uses CLIP
(ViT-L/14) for encoding images and text.

###  4.4 Retriever

RAFIC’s retrieval component uses (1) CLIP, (2) a large corpus of 5B images
(LAION-5B), and (3) an efficient retrieval index (faiss), for retrieving and
augmenting support images.

####  4.4.1 LAION-5B

LAION-5B Schuhmann et al. (2022) is a corpus of 5B+ image-text pairs. At the
time of this writing, this dataset is the largest open-source repository of
images. RAFIC retrieves images from LAION-5B that are most similar to the
supplied support images.

####  4.4.2 Retrieval index (faiss)

RAFIC retrieves similar images for each class. Brute-force retrieval search
across 5B+ images is prohibitively expensive. Therefore, we resort to
Approximate Nearest Neighbor (ANN) search via faiss Johnson et al. (2019). We
use cosine similarity as our retrieval score.

####  4.4.3 Retrieval mechanics

Given a set of $K$ support images for class name $T$ (a string), we first use
the CLIP text encoder to encode the string formatted as "photo of {T}
{dataset}", we call this $E_{T}$. An example of this string is "photo of a
Boeing 747-400 aircraft", where $T$ is "Boeing 747-400" and dataset is
"aircraft".

Next, we encode each image using the CLIP image encoder and take the mean of
the image embeddings to get $E_{S}$. Then, we compute
$E_{Q}=\alpha_{T}E_{T}+(1-\alpha_{T})E_{S}$ (where $0\leq\alpha_{T}\leq 1$)
and use $E_{Q}$ to search against the faiss index.

###  4.5 Model

Image embeddings for the support and retrieved images are concatenated into a
combined matrix $X$. Then, $X$ is passed into a learning model. This model is
ultimately responsible for predicting query image labels. As we will see
shortly, the model may or may not use $X$. We considered a few models that we
will now describe.

####  4.5.1 Logistic Regression (LR)

We learn a Logistic Regression classifier using $X$ for each task. In other
words, a new classifier is trained for each $N$-way few-shot classification
task, and there’s no opportunity for meta-learning across tasks. We use the
scikit-learn Pedregosa et al. (2011) implementation of LR.

####  4.5.2 Model-Agnostic Meta-Learning (MAML)

MAML Finn et al. (2017) is a widely used meta-learning technique. MAML
involves an inner-loop, which can adapt to the task, and an outer loop, which
updates the model parameters while training. We use an an MLP on top of CLIP
embeddings with ReLU activation.

####  4.5.3 Prototypical Networks (ProtoNet)

ProtoNet Snell et al. (2017) learns by creating "prototypes", which is an
average of the support images per task. To classify unseen images, ProtoNet
simply compares their features to these prototypes, and assigns them to the
closest matching class. Similar to MAML, we use an MLP with ReLU on top of
CLIP embeddings.

####  4.5.4 Zero-shot (ZS) classification using class names

This model is special in that it does not use the support images and therefore
does not use retrieval (i.e. ignores $X$). We follow this approach:

  1. 1.

Extract CLIP embeddings for query images and the class names.

  2. 2.

For each query image, calculate the cosine similarity between image embeddings
and each of the class text embeddings.

  3. 3.

Output the class name with the highest score.

###  4.6 Retrieval meta-learning

In our retrieval augmentation, we employ two following two categories of meta-
learning approaches:

  * •

Coarse-grained. We use two techniques: (1) meta-learn separate learning rates
for support and retrieval component, allowing the learning process to over or
under-emphasize retrieval as a whole, and (2) weighted loss computation, we
use similarity score to overemphasize retrieved images with higher visual
alignment in the learning process. We have only implemented this method for
MAML.

  * •

Fine-grained. For each retrieved image, we append the retrieval cosine
similarity score to the image CLIP embeddings. For support and query images,
we append the value of 1.

##  5 Experiments

In this section, we conduct a series of experiments to study our proposed
system.

###  5.1 Datasets

We use two datasets for our experiments.

####  5.1.1 Birds

The Caltech-UCSD Birds dataset Wah et al. (2011) has a total of 11,788 images
from across 200 classes of rare birds. The dataset is split into 70%, 15%, and
15% for train, validation, and test respectively.

####  5.1.2 Aircraft

The FGVC-Aircraft dataset Maji et al. (2013) contains 10,200 images of
aircraft across 102 different aircraft model variants. Each variant belongs to
one of 29 manufacturers. For instance, Boeing has 22 different variants such
as 747-100 and 777-200. To avoid leakage across splits, we partitioned the
data by manufacturer, which yielded approximately 65%, 20%, and 15% for train,
validation, and test.

###  5.2 Experimental setup

For all experiments, we picked the following values:

  * •

$N=10$, which implies random guessing accuracy of 0.1.

  * •

$K=1$, accuracy tends to improve with more support images. Picking the
smallest possible value left more room for observing the impact of our
proposed method.

  * •

$Q=5$, our early experiments indicated that the results are not very sensitive
to this value.

  * •

$\alpha_{T}=0.8$, in our early experiments, we observed that putting more
weight on the class name text embedding $E_{T}$ lead to better results
relative to the mean image embeddings $E_{S}$.

We ran experiments using 5 different seeds and observed the variance in the
validation set. In most cases the standard deviation is less than 1 percentage
point. We report accuracy on the test set.

For MAML and ProtoNet, we train with batch size 8 and up to a maximum of 200
training steps (both methods converge earlier). For ProtoNet we used a single-
layer linear layer with 64 hidden dimensions, but also tried 2-layer MLPs and
using 32, 128, 256 neurons, and observed very little impact. For MAML, we use
inner and outer learning rate of 0.04 and 0.001 respectively, used 100 inner
steps, and a 2-layer MLP with 128 and 32 hidden neurons.

####  5.2.1 Compact index construction for efficient experimentation

To enable efficient experimentation, we opted to precompute a compact index.
This approach eliminated the need for real-time embedding extraction. We
constructed this index by (1) retrieving the top-20 images from LAION-5B for
each image in the dataset using the image embedding, (2) retrieving the
top-100 images for each class label, (3) taking the union of all images in the
previous step, and (4) extracting these embeddings and constructing a new
compact faiss index for retrieval.

Using this approach, we are guaranteed to only retrieve precomputed images. We
ran a few experiments and validated that recall was very close to 1 in the
majority of cases relative to using the full index.

###  5.3 Experiment 0: CLIP vs. raw pixels

We evaluated the effectiveness of using CLIP embeddings vs. raw pixels as
input features for few-shot image classification using a basic MAML setup.
CLIP embeddings achieved a remarkable accuracy of 0.88 on the birds dataset,
far surpassing the performance of raw image bytes, which only reached 0.26.
This clearly demonstrates the significant advantage of using CLIP embeddings,
which capture richer semantic information and lead to significantly improved
classification performance. To ensure consistent and optimal performance
across all experiments, we use CLIP embedding as the default representation
for images.

###  5.4 Experiment 1: augmenting support images via retrieval

This experiment focuses on the effect of adding retrieved images. Fig 2 shows
accuracy as a function of increasing the number of retrieved images (starting
at 0).

Figure 2: Accuracy as a function of number of retrieved images $A$. We use
$A=\\{0,1,2,5,20,50\\}$. Baseline is the dashed black line, which is LR with
$A=0$. We see that accuracy improves as we increase $A$. The red line (ZS)
does not use support or retrieved images and only uses class label name
embeddings. We see that no method can beat ZS for birds, but ProtoNet
outperforms it for aircraft.

We observe that retrieval boosts performance. However, performance plateaus as
$A$ increases in most cases. Both MAML and ProtoNet beat the LR baseline (i.e.
LR at $A=0$), but ZS beats all methods for birds without referencing support
images or additional retrieved images.

This experiment suggests that CLIP has seen more examples of rare birds with
rich textual descriptions from across the internet vs. aircraft. Also,
aircraft variants are harder to visually distinguish and retrieval and meta-
learning appear to boost accuracy more as a consequence.

###  5.5 Experiment 2: meta-learning the retrieval strategy

We start with the observation that retrieved images are not all equally
relevant. Ideally, the retrieval strategy should learn to put the correct
emphasis on retrieval, and not blindly treat all images equally.

As described in the Methods section, we consider techniques to address fine
and coarse-grain retrieval meta-learning. We tabulate the effect of enabling
both of these vs. no retrieval meta-learning in Table 1 (results for $A=50$
are flat, which we exclude to save space).

Dataset | Method | A=1 | A=2 | A=5 | A=20
---|---|---|---|---|---
Birds | MAML | 0.88 / 0.88 | 0.88 / 0.89 | 0.90 / 0.91 | 0.92 / 0.92
ProtoNet | 0.91 / 0.94 | 0.93 / 0.93 | 0.92 / 0.93 | 0.92 / 0.93
Aircraft | MAML | 0.50 / 0.53 | 0.49 / 0.53 | 0.48 / 0.52 | 0.48 / 0.51
ProtoNet | 0.53 / 0.60 | 0.57 / 0.63 | 0.59 / 0.61 | 0.56 / 0.56
Table 1: Effect of meta-learning the retrieval strategy. Results are in x / y
format, where y is accuracy with and x is without meta-learning. Cells with an
improvement are bolded, and we can see an improvement in most cases,
especially for the aircraft dataset.

Improvements are larger for smaller values of $A$, ProtoNet enjoys a larger
boost, and aircraft benefits more than birds (consistent with experiment 1).
Note that ProtoNet only uses fine-grained (i.e. appending cosine similarity of
retrieved images to CLIP embeddings). MAML uses both fine and coarse-grained.
Ablating fine-grain from MAML led to losing almost all of the benefits. Using
only fine-grained for aircraft actually led to an improvement for $A\geq 2$,
namely 0.55, 0.53, and 0.53 for $A$ equal to 2, 5, and 20 respectively.

###  5.6 Experiment 3: cross-evaluation

In this experiment, we meta-train methods on one dataset and evaluate it on
the other dataset. Obviously, we expect methods to performance worse when not
trained on the evaluation task. This experiment is intended to answer two
questions:

  1. 1.

How much performance drop do we see? Another way of asking this question is:
can one method recover better from not having been trained on the evaluation
task?

  2. 2.

Do we see a gain with meta-learning the retrieval strategy (i.e. what we
tested in experiment 2)?

Fig 3 depicts the results of our experiments for answering these two
questions.

Figure 3: Cross-evaluation results for experiment 3. The y-axis for all four
graphs is the absolute difference in accuracy times 100. For example, if
accuracy with and without a treatment is 0.82 and 0.80 respectively, the
difference (i.e. gain) is 2 percentage points. The first row focuses on
question 1 and measures the drop (i.e. negative gain) in accuracy when we
cross-evaluate vs. training and evaluating on the same dataset. The second row
focuses on question two, and shows the accuracy gain of using retrieval meta-
learning (described in experiment 2) vs. not using it (both are cross-
evaluated). We omitted results for $A>5$ as they ended up being very similar
to $A=5$, for the sake of brevity.

We notice that MAML can better adapt much vs. ProtoNet. This finding makes
sense in light of understanding how MAML works, and especially given the fact
that we use 100 inner steps for adaptation. ProtoNet, on the other hand, has
no opportunity to adapt since the learned parameters are fixed at evaluation.
Also, we see that there’s less of a drop as we go from 1 to 5. Additional
retrieved images appear to make tasks more transferable across both methods.

Focusing on the second row in Fig 3, we see that meta-learning the retrieval
strategy plays a positive role, with the effect being larger for ProtoNet.

This experiment introduces an additional angle to our study. Although we saw
MAML consistently underperform the simpler ProtoNet in previous experiments,
we can see that it’s more adaptable and might be a better choice for meta-
learning across radically different tasks. We should note that MAML involves
more hyperparameters relative to ProtoNet, and we might’ve been able to see
similar or better performance to ProtoNet with thorough hyperparameter tuning.

##  6 Conclusion and future work

Our study suggests that retrieval-augmentation using a large-scale image
repository (LAION-5B), efficient image-text encoders (CLIP), and efficient
retrieval indices (faiss), can benefit few-shot image classification. We have
also demonstrated that meta-learning is beneficial for faster adaptation and
higher performance when labeled data is hard or expensive to collect.

For future work, we aim to broaden our research by incorporating a more
diverse range of datasets from different domains, in order to better assess
the validity of our method. Additionally, we have only scratched the surface
when it comes to meta-learning the retrieval strategy. For instance, having
observed the benefits from including textual descriptions, we plan to devise
and experiment with methods that further leverage natural language.

##  7 Contributions

  1. 1.

Hangfei conducted data exploration, optimized CLIP embeddings extraction, and
build the data loader for retrieval, training and evaluation.

  2. 2.

Li developed the training and evaluation framework. He also designed and
implemented meta-learning methods for retrieval.

  3. 3.

Amir built and optimized the faiss index for retrieval and designed and
conducted the experiments.

We deviated from our original plan as we realized that efficient retrieval is
key to fast experimentation, and that developing and optimizing the retrieval
index requires additional effort. This led to Li taking over the development
of new meta-learning methods instead of Amir.

##  8 Acknowledgements

We would like to thank Yoonho Lee, whose insightful discussions and guidance
have been instrumental in shaping and refining this work. Additionally, our
thanks go to Chelsea Finn for her valuable advice in the selection of datasets
and providing early feedback in this research direction.

## References

  * Antoniou et al. [2017] Antreas Antoniou, Amos Storkey, and Harrison Edwards.  Data augmentation generative adversarial networks.  _arXiv preprint arXiv:1711.04340_ , 2017.
  * Bowles et al. [2018] Christopher Bowles, Liang Chen, Ricardo Guerrero, Paul Bentley, Roger Gunn, Alexander Hammers, David Alexander Dickie, Maria Valdés Hernández, Joanna Wardlaw, and Daniel Rueckert.  Gan augmentation: Augmenting training data using generative adversarial networks.  _arXiv preprint arXiv:1810.10863_ , 2018.
  * Chen et al. [2021] Wentao Chen, Chenyang Si, Wei Wang, Liang Wang, Zilei Wang, and Tieniu Tan.  Few-shot learning with part discovery and augmentation from unlabeled images.  _arXiv preprint arXiv:2105.11874_ , 2021.
  * Deshpande et al. [2020] Aditya M Deshpande, Ali A Minai, and Manish Kumar.  One-shot recognition of manufacturing defects in steel surfaces.  _Procedia Manufacturing_ , 48:1064–1071, 2020.
  * Dhillon et al. [2019] Guneet S Dhillon, Pratik Chaudhari, Avinash Ravichandran, and Stefano Soatto.  A baseline for few-shot image classification.  _arXiv preprint arXiv:1909.02729_ , 2019.
  * Finn et al. [2017] Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks, 2017.
  * Johnson et al. [2019] Jeff Johnson, Matthijs Douze, and Hervé Jégou.  Billion-scale similarity search with gpus.  _IEEE Transactions on Big Data_ , 7(3):535–547, 2019.
  * Khodadadeh et al. [2020] Siavash Khodadadeh, Sharare Zehtabian, Saeed Vahidian, Weijia Wang, Bill Lin, and Ladislau Bölöni.  Unsupervised meta-learning through latent-space interpolation in generative models.  _arXiv preprint arXiv:2006.10236_ , 2020.
  * Kotia et al. [2021] Jai Kotia, Adit Kotwal, Rishika Bharti, and Ramchandra Mangrulkar.  Few shot learning for medical imaging.  _Machine learning algorithms for industrial applications_ , pages 107–132, 2021.
  * Long et al. [2022] Alexander Long, Wei Yin, Thalaiyasingam Ajanthan, Vu Nguyen, Pulak Purkait, Ravi Garg, Alan Blair, Chunhua Shen, and Anton van den Hengel.  Retrieval augmented classification for long-tail visual recognition.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 6959–6969, 2022.
  * Maji et al. [2013] Subhransu Maji, Esa Rahtu, Juho Kannala, Matthew Blaschko, and Andrea Vedaldi.  Fine-grained visual classification of aircraft.  _arXiv preprint arXiv:1306.5151_ , 2013.
  * Ni et al. [2021] Renkun Ni, Micah Goldblum, Amr Sharaf, Kezhi Kong, and Tom Goldstein.  Data augmentation for meta-learning.  In _International Conference on Machine Learning_ , pages 8152–8161. PMLR, 2021.
  * Pedregosa et al. [2011] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al.  Scikit-learn: Machine learning in python.  _the Journal of machine Learning research_ , 12:2825–2830, 2011.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In _International conference on machine learning_ , pages 8748–8763. PMLR, 2021.
  * Schuhmann et al. [2022] Christoph Schuhmann, Romain Beaumont, Richard Vencu, Cade Gordon, Ross Wightman, Mehdi Cherti, Theo Coombes, Aarush Katta, Clayton Mullis, Mitchell Wortsman, et al.  Laion-5b: An open large-scale dataset for training next generation image-text models.  _Advances in Neural Information Processing Systems_ , 35:25278–25294, 2022.
  * Shorten and Khoshgoftaar [2019] Connor Shorten and Taghi M Khoshgoftaar.  A survey on image data augmentation for deep learning.  _Journal of big data_ , 6(1):1–48, 2019.
  * Snell et al. [2017] Jake Snell, Kevin Swersky, and Richard Zemel.  Prototypical networks for few-shot learning.  _Advances in neural information processing systems_ , 30, 2017.
  * Vella and Ebejer [2022] Daniel Vella and Jean-Paul Ebejer.  Few-shot learning for low-data drug discovery.  _Journal of Chemical Information and Modeling_ , 63(1):27–42, 2022.
  * Vilalta and Drissi [2002] Ricardo Vilalta and Youssef Drissi.  A perspective view and survey of meta-learning.  _Artificial intelligence review_ , 18:77–95, 2002.
  * Wah et al. [2011] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie.  The caltech-ucsd birds-200-2011 dataset.  2011\.
  * Zhang et al. [2019] Hongguang Zhang, Jing Zhang, and Piotr Koniusz.  Few-shot learning via saliency-guided hallucination of samples.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2019.
  * Zhang et al. [2022] Renrui Zhang, Wei Zhang, Rongyao Fang, Peng Gao, Kunchang Li, Jifeng Dai, Yu Qiao, and Hongsheng Li.  Tip-adapter: Training-free adaption of clip for few-shot classification.  In _European Conference on Computer Vision_ , pages 493–510. Springer, 2022.