# A test of invariance of dark matter halo surface density using
multiwavelength mock galaxy catalogues

Gopika K.,1 Shantanu Desai,1 Aseem Paranjape2
1Department of Physics, Indian Institute of Technology, Hyderabad, Kandi,
Telangana-502284, India
2Inter-University Centre for Astronomy and Astrophysics, Ganeshkhind, Post Bag
4, Pune 411007, India
E-mail<EMAIL_ADDRESS>
(Accepted XXX. Received YYY; in original form ZZZ)

###### Abstract

A large number of observations have shown that the dark matter halo surface
density, given by the product of halo core radius and core density is nearly
constant for a diverse suite of galaxies. Although this invariance of the halo
surface density is violated at galaxy cluster and group scales, it is still an
open question on whether the aforementioned constancy on galactic scales can
be explained within $\Lambda$CDM. For this purpose, we probe the variation of
halo surface density as a function of mass using multi-wavelength mock galaxy
catalogs from $\Lambda$CDM simulations, where the adiabatic contraction of
dark matter halos in the presence of baryons has been taken into account. We
find that these baryonified $\Lambda$CDM halos were best fitted with a
generalized-NFW profile, and the halo surface density from these halos has a
degeneracy with respect to both the halo mass and the virial concentration. We
find that the correlation with mass when averaged over concentration is
consistent with a constant halo surface density. However, a power-law
dependence as a function of halo mass also cannot be ruled out.

###### keywords:

galaxies: formation - cosmology: theory - cosmology: dark matter - methods:
numerical

††pubyear: 2023††pagerange: A test of invariance of dark matter halo surface
density using multiwavelength mock galaxy catalogues–A

##  1 Introduction

Although, the current concordance $\Lambda$CDM model of cosmology consisting
of 70% dark energy and 25% cold dark matter is very successful in explaining
cosmological observations at large scales (Aghanim et al., 2020), there are
still some vexing issues with this standard cosmological model. Some of these
problems with the standard model include the core-cusp and the missing
satellites problem (Bullock & Boylan-Kolchin, 2017), Hubble constant tension
(Di Valentino et al., 2021), $\sigma_{8}$ tensions between cluster and CMB
(Benisty, 2021), failure to detect cold dark matter candidates in laboratory
based experiments (Merritt, 2017), Lithium-7 problem in Big-Bang
nucleosynthesis (Fields et al., 2020), radial acceleration relation in spiral
galaxies with very low scatter (McGaugh et al., 2016), CMB anomalies at large
angular scales (Copi et al., 2010), etc. An up-to-date summary of the
challenges for $\Lambda$CDM model can be found in Perivolaropoulos & Skara
(2022); Abdalla et al. (2022); Peebles (2022). Therefore a large number of
alternatives to the standard cosmological model have been proposed to account
for some of these anomalies (Bull et al., 2016; Banik & Zhao, 2022; Abdalla et
al., 2022).

An intriguing observational result discovered more than a decade ago is that
the dark matter halo surface density was found to be constant, for a wide
variety of systems spanning over 18 orders in blue visual magnitude for a
diverse suite of galaxies, such as spiral galaxies, low surface brightness
galaxies, dwarf spheroidal satellites of Milky way (Donato et al., 2004, 2009;
Walker et al., 2010; Salucci et al., 2012; Kormendy & Freeman, 2016; Hayashi &
Chiba, 2015; Burkert, 2015; Salucci, 2019). These results for a constant dark
matter surface density were obtained by fitting the dark matter distribution
in these systems to a cored profile, either Burkert (Burkert, 1995), pseudo-
isothermal profile (Kormendy & Freeman, 2016), or a simple isothermal sphere
(Spano et al., 2008). All these cored profiles can be parameterized by a
central density ($\rho_{c}$) and core radius ($r_{c}$); and the halo surface
density ($S$) is then defined according to:

$S\equiv\rho_{c}\times r_{c}$ (1)

The halo surface density can also be interpreted as a measure of the Newtonian
acceleration at a given radius (Cardone & Tortora, 2010). The existence of a
constant dark matter surface density was found to be independent of which
cored profile was used (Donato et al., 2009). The latest best-fit value
obtained by fitting all the available data for the above systems is given by
$\log(\rho_{c}r_{c})=2.15\pm 0.2$ with units of $\log(M_{\odot}/pc^{2})$
(Salucci, 2019).

However, cored profiles cannot adequately fit all systems, some of which need
cuspy profiles (Simon et al., 2005; Strigari et al., 2010; Genina et al.,
2018; Breddels & Helmi, 2013; Newman et al., 2013a; Newman et al., 2013b;
Hayashi et al., 2020). Also, sometimes the same data can be easily fitted with
both cored and cuspy profiles (Gentile et al., 2007; Meadows et al., 2020;
Boldrini, 2021). Therefore, a variant of the aforementioned halo surface
density has been constructed (which has been refered to in the literature as
“column density”), whose value was found to be nearly invariant for both cored
and cuspy profiles (Boyarsky et al., 2009, 2010; Del Popolo et al., 2013), and
therefore can be applied to observational data, since it is mostly agnostic to
the underlying dark matter profile:

$S(R)=\frac{2}{R^{2}}\int_{0}^{R}r^{\prime}dr^{\prime}\int_{-\infty}^{+\infty}dz\rho_{DM}(\sqrt{r^{\prime
2}+z^{2}})$ (2)

The above definition implies that $S(R)$ is proportional to the dark matter
surface density at a radius $R$. The column densities for some of the commonly
used dark matter profiles such as Navarro-Frenk-White (NFW) ($S_{NFW}$),
pseudo-isothermal ($S_{ISO}$) and Burkert profiles ($S_{BUR}$) are connected
to each other as follows: $S_{NFW}(r_{s})\approx 0.91S_{ISO}(6r_{c})$ and
$S_{NFW}(r_{s})\approx 0.98S_{BUR}(1.66r_{0})$ (Boyarsky et al., 2009). The
analytical expressions for $S_{NFW}$ and $S_{ISO}$ have been provided in
Boyarsky et al. (2009); Del Popolo et al. (2013) .111We note that there are
also other variants of the halo surface density used in the literature, for
example mean surface density, given by $\frac{M(r)}{4/3\pi r^{2}}$ (Bondarenko
et al., 2018) or $\frac{M(r)}{\pi r^{2}}$ (Hayashi & Chiba, 2015). However, we
do not evaluate these quantities in this work.

The aforementioned results for the constancy of dark matter halo surface
density have however been disputed in the literature by many other works,
which have shown that the dark matter column density (Eq. 2) as well as the
halo surface density (Eq. 1) is not constant and is correlated with the galaxy
luminosity, halo mass, and stellar age (Boyarsky et al., 2009; Napolitano et
al., 2010; Cardone & Tortora, 2010; Del Popolo et al., 2013; Cardone & Del
Popolo, 2012; Saburova & Del Popolo, 2014; Del Popolo & Lee, 2017; Zhou et
al., 2020). Some of these works have found $S\propto M_{halo}^{0.16-0.2}$ (Del
Popolo et al., 2013) as well as $S\propto L^{0.13}$ (Zhou et al., 2020).  Most
recently, Del Popolo (2023) found a dichotomy in the behaviour of halo surface
density based on the effective surface brightness ($\Sigma_{\rm eff}$). For
high-surface brightness galaxies from the SPARC sample, ($\Sigma_{\rm
eff}>200L_{\odot}/pc^{2}$), this work found the halo surface density is
constant as a function of magnitude, but with a larger value than Donato et
al. (2009). However for low-surface brightness galaxies, the halo surface
density is anti-correlated with magnitude or correlated with luminosity (Del
Popolo, 2023). Therefore, a majority of papers in the literature could not
corroborate the claims in Donato et al. (2009).

These observations of a (near)-constancy of the halo surface density have been
shown to be a very good laboratory for testing alternatives to $\Lambda$CDM or
constraining particle dark matter properties within these alternatives.
Milgrom (2009) has pointed out that, in MOND, the numerical value of the
constant halo surface density obtained in Donato et al. (2009) is equal to
$\frac{a_{0}}{2\pi G}$, where $a_{0}$ is the MOND acceleration scale, and
hence this observation is consistent with MOND predictions. A constant halo
surface density is also predicted by superfluid dark matter (Berezhiani et
al., 2018), self-interacting dark matter (Rocha et al., 2013; Bondarenko et
al., 2018; Lin & Loeb, 2016; Kaplinghat et al., 2016) and ultra-light scalar
dark matter (Ureña-López et al., 2017). Observations of constant surface
density have been used to obtain a lower limit on the warm dark matter
particle mass (Hayashi & Chiba, 2015). Burkert (2020) has argued that a
constant halo surface density is also in tension with fuzzy dark matter.
However, the analysis in Burkert (2020) assumes that the core density of fuzzy
dark matter models follows isothermal or Burkert profile, whereas the density
profiles in these models are quite different (Khelashvili et al., 2022).
Alternatives to $\Lambda$CDM model such as the logtropic model, which involve
coupled dark energy-dark matter have also been able to explain this constancy
of halo surface density (Chavanis, 2022).

Motivated by these considerations, studies on the constancy of halo surface
density were extended to galaxy cluster (Chan, 2014; Gopika & Desai, 2020) as
well as galaxy group scales (Gopika & Desai, 2021). These works found that
although the core radius is inversely proportional to the core density, their
product, viz. the halo surface density is about an order of magnitude larger
than that obtained for single galaxies, whereas for galaxy groups, it is in
between that for single galaxies and groups. Therefore, the invariance of halo
surface density found from galaxies (Donato et al., 2009) does not hold true
for group or cluster scaled halos.

It is still an open question whether the current standard model of Cosmology,
namely the $\Lambda$CDM model, with best-fit parameters determined by Planck
Cosmology (Aghanim et al., 2020), can explain the (near) constancy of the halo
surface density on galactic scales and its elevated value on cluster scales.
Some proposed semi-analytical mechanisms within the $\Lambda$CDM model to
explain the near constancy of halo surface density include transformation of
cusps to cores due to dynamical feedback processes (Ogiya & Mori, 2011), non-
violent relaxation of galactic halos (Baushev, 2014), secondary self-similar
infall model (Del Popolo, 2009; Del Popolo et al., 2013), analytical
description of the virialized spherical dark matter halo with the NFW density
profile (Demiański & Doroshkevich, 2014). However, except for the secondary
infall model, which predicts ($S\propto M_{200}^{0.20\pm 0.05}$) and the
Demiański & Doroshkevich (2014) model which predicts $S\propto M_{vir}^{0.3}$,
none of the other proposed models can self-consistently predict the observed
trends for halo surface densities as a function of mass for the full dynamical
range of halo mass from dwarf galaxies to cluster scale halos. More than a
decade ago, a preliminary study using isolated halos and subhalos from the
Aquarius cosmological simulations (Macciò et al., 2008; Springel et al., 2008)
also found a scaling of the column density with halo mass, although no error
analysis was carried out (Boyarsky et al., 2009). In the last few years the
availability of high resolution mock catalogs, which agree with observational
data enables a detailed systematic study of the dark matter surface density.

Therefore, in this work we set out to carry out such a study using mock galaxy
catalogs (Paranjape et al., 2021) that successfully mimick the properties and
spatial distribution of galaxies in the local Universe (redshift $z\lesssim
0.1$). Among other features, these mock catalogs have been shown by Paranjape
& Sheth (2021) to reproduce the radial acceleration relation (McGaugh et al.,
2016), which has previously been an enigma within the $\Lambda$CDM model
(Famaey & McGaugh, 2012).

This manuscript is structured as follows. The multi-wavelength mock galaxy
catalog is defined in Sect. 2. The data analysis procedure is described in
Sect. 3. The gNFW fits are described in Sect. 4. Our results for the halo
surface density can be found in Sect. 5. We conclude in Sect. 6.

##  2 Mock galaxy catalogs

In this work, we use mock galaxy catalogs constructed using the algorithm
presented by Paranjape et al. (2021). Here, we briefly summarise the main
features of interest of these catalogs and refer the reader to Paranjape et
al. (2021) for further details of the underlying $N$-body simulation and the
mock algorithm which was extensively tested by them.

Each catalog represents a luminosity-complete sample of galaxies with SDSS
$r$-band absolute magnitude $M_{r}\leq-19$ in a $(300h^{-1}{\rm Mpc})^{3}$
comoving volume at $z=0$. The mock contains both central and satellite
galaxies, populated in dark matter halos identified in an $N$-body simulation
having $1024^{3}$ particles with a flat $\Lambda$CDM WMAP7 cosmology (Komatsu
et al., 2011; $\Omega_{\rm m}=0.276$, $h=0.7$).

The galaxies in each mock were populated using a halo occupation distribution
(HOD) model calibrated by Paul et al. (2019) using luminosity- and colour-
dependent clustering measurements from the Sloan Digital Sky Survey (SDSS,
York et al., 2000; Zehavi et al., 2011). Each galaxy in the mock is assigned
absolute magnitudes in SDSS $u$, $g$ and $r$ bands and a stellar mass
$m_{\ast}$ using a colour-dependent mass-to-light ratio.

In this work, we use the population of mock central galaxies having
$m_{\ast}\geq 10^{9.8}h^{-2}M_{\odot}$, which results in $\sim 221,000$
objects that form a volume-complete sample of stellar mass-selected galaxies.

The host halos of these centrals are ‘baryonified’ as described by Paranjape
et al. (2021), and the dark matter profiles of the respective host halos are
assumed to respond to the presence of these baryons. This response is modelled
as a quasi-adiabatic relaxation process (Teyssier et al., 2011; Schneider &
Teyssier, 2015, see section 3 of Paranjape & Sheth, 2021) parametrised by a
‘relaxation parameter’ $q$ to control the amount of relaxation, such that
$q=1$ ($q=0$) corresponds to perfect angular momentum conservation (no
response to baryons). We have performed our analysis using two mock catalogs,
respectively produced using the values $q=0.68$ and $q=0.33$. While the former
provides a good description of the effect seen in cluster-sized halos in
hydrodynamical CDM zoom simulations (Teyssier et al., 2011; Schneider &
Teyssier, 2015), it is subject to some theoretical uncertainty as discussed by
Paranjape & Sheth (2021). The second value $q=0.33$ was shown by Paranjape &
Sheth (2021) to improve the agreement at high accelerations between the median
RAR of the mock and measurements using disk galaxies in the SPARC sample.
Settling the theoretical uncertainty in the modelling of quasi-adiabatic
relaxation requires a detailed study of hydrodynamical simulations of galaxy
formation over a large mass range, which has only recently begun to be
performed (Velmani & Paranjape, 2023). We have found, however, that all our
results in this work are independent of the value of $q$. For brevity,
therefore, we only report the results using $q=0.33$.

##  3 Data Analysis

In this section, we will outline our data analysis procedure. Each simulated
halo is characterized by a baryonified dark matter density profile up to the
virial radius, along with other physical parameters such as the virial
concentration ($C_{vir}$), virial-mass ($M_{halo}$), and stellar mass
($m_{\ast}$). Firstly, we shall describe the different parametric forms of the
dark matter halo density profiles used to fit the simulation data. Then, we
discuss the regression method used to determine the best-fit density profile,
which can robustly fit the full range of simulated profiles. Lastly, we shall
present our results for the halo surface density using the best-fit profile
and study its variation as a function of halo mass and other parameters.

###  3.1 Dark Matter Density Profiles

All the results on the halo surface density in literature were obtained by
fitting for cored profiles such as isothermal or Burkert profiles (Donato et
al., 2009; Salucci et al., 2012; Chan, 2014; Gopika & Desai, 2020, 2021; Zhou
et al., 2020) or NFW profiles (Boyarsky et al., 2009, 2010). As a first step
towards this, we produce density profiles of relaxed dark matter $\rho(r)$ in
units of $\rho_{vir}$ at 30 logarithmically spaced values of $r/R_{vir}$ in
the range $(10^{-5},1)$. These densities and radii are then converted into the
real physical units of $M_{\odot}/pc^{3}$ and $kpc$ respectively by assuming
the fiducial cosmology of the underlying simulation.

Figure 1 shows the distribution of the halo mass and concentration for the
stellar-mass complete sample of 2,21,670 halos with a stellar mass selection,
$\log m_{\ast}\geq 9.85h^{-2}M_{\odot}$ included in this analysis. We have
used the total mass at the virial radius $r_{200}$ as a proxy for the halo
mass($M_{halo}$) of the dark matter halos for the entirety of this study.

Figure 1: Distribution of the virial mass, $M_{halo}$ and virial
concentration, $C_{vir}$ for the stellar-mass complete sample of simulated
halos.

We now fit the simulated halos with a cored isothermal and Burkert profile as
well as some non-cored profiles such as NFW and generalized-NFW (gNFW), which
are described below:

  * •

Burkert Profile (Burkert, 1995)

$\rho_{Bur}(r)=\frac{\rho_{c}r_{c}^{3}}{(r^{2}+r_{c}^{2})(r+r_{c})}$ (3)

  * •

Isothermal Profile (Kormendy & Freeman, 2016):

$\rho_{iso}(r)=\frac{\rho_{c}}{[1+(r/r_{c})^{2}]}$ (4)

where $r$ is the radial distance; $r_{c}$ and $\rho_{c}$ are the scale
parameters, which are usually referred to in the literature as the core radius
and core density, respectively.

  * •

NFW Profile (Navarro et al., 1997):

$\rho_{NFW}(r)=\frac{\rho_{s}}{(r/r_{s})(1+r/r_{s})^{2}}$ (5)

where $r_{s}$ and $\rho_{s}$ are the NFW scale parameters.

  * •

gNFW Profile (Zhao, 1996; Moore et al., 1999):

$\rho_{gNFW}(r)=\frac{\rho_{s}}{(r/r_{s})^{\alpha}(1+r/r_{s})^{3-\alpha}}$ (6)

This 3-parameter gNFW model is a generalization of the NFW profile where
$\rho_{s}$ and $r_{s}$ are the normalization and scale radius, respectively
and $\alpha$ is the inner slope of the profile, where $\alpha=1$ would attain
a standard NFW profile.

However, we shall subsequently show that only a generalized NFW profile can
holistically fit these baryonified dark-matter halos for all galaxies as
discussed in the next section.

###  3.2 Fits to halo profiles

The fits for the simulated density profiles to the analytic density models
described in Section 3.1 are paramount to this study. Here, we have performed
fits on the stacked halo profiles. Stacked profiles are essential, since the
individual halo profiles do not have any errors associated with them, and
hence analysing the stacks permits us to average over a bin of data to obtain
a single density profile with error proxies derived from looking at the
scatter within the stack. The use of stacks in this work is adequate, as our
main goal is to study the halo scaling relations.

For the $\chi^{2}$ analysis associated with the fitting of the simulated halo
densities with cored isothermal, NFW, and generalized-NFW models, we have
considered the distributed densities for fixed bins of halo-mass ($M_{halo}$),
virial concentration ($C_{vir}$), and stellar mass ($m_{\ast}$). For this
work, we have used three different binning procedures to achieve three
distinct data sets labelled as Set 1, Set 2, Set 3, which correspond to
binning the entire simulation data with respect to $M_{halo}$; $M_{halo}$ and
$C_{vir}$; and $M_{halo}$, $C_{vir}$, and $m_{\ast}$, respectively with a very
stringent technique being followed in order to attain evenly populated bins
for each of these cases.

For the Set 1 data, the whole population is divided into five equal quantiles
of halo mass with each mass-bin having approximately 44,300 halos.
Additionally, in order to carry out a more detailed analysis, we can perform a
similar percentile binning with respect to the virial concentration in the Set
1 data to get Set 2 data. Each bin of mass is further sub-divided using
$C_{vir}$ giving 25 bins, having an approximate population of 8800 halos in
each bin. The Set 3 data is similarly obtained by doing a percentile binning
in the Set 2 data using the stellar mass to get an evenly populated 125 three-
dimensional bins in $M_{halo}$, $C_{vir}$, and $m_{\ast}$.

A stack can be constructed by calculating the mean density of the simulated
profiles in each of the percentile-bins discussed above for the 30
logarithmically spaced values of $r$ in the range $(10^{-5},1)\times R_{vir}$.
The error associated with the density in each bin is represented by the
standard deviation of the density of the given radial bin distributed across
all halos of the stack. The physical parameters such as $M_{halo}$, $C_{vir}$,
and $m_{\ast}$ associated with these stacked objects (for each bin) are
obtained from the median of the binned data.

Finally, the stacks are each fitted to the functional forms of all the halo
profiles, to determine the best-fit parameters in each model followed by a
model selection procedure to determine the best-fit parametric model which can
fit the full range of halo density profiles. In Figure 2, a radial profile of
the relaxed dark matter density for one of the Set 3 stacked objects is shown.
The data points represent the average density profile of a bin where the data
are binned with respect to the halo mass, $C_{vir}$, and stellar mass. The
median values of the physical parameters $M_{halo}$, $C_{vir}$, and $m_{\ast}$
associated with this stacked halo are $2.03\times 10^{12}h^{-1}M_{\odot}$,
9.83, and $2.47\times 10^{10}h^{-2}M_{\odot}$, respectively. Based on this
visual appearance, we can see that only the gNFW profile provides a good fit.
However, we quantify this using model comparison techniques as described in
the next subsection.

Figure 2: This figure shows the relaxed dark-matter density profile for a
stacked object with $M_{halo}=2.03\times 10^{12}h^{-1}M_{\odot}$,
$C_{vir}=9.83$ and $\log m_{\ast}=2.47\times 10^{10}h^{-2}M_{\odot}$ which is
fitted with a generalized-NFW (red), NFW (blue), isothermal (cyan) and
Burkert(green) profiles. The yellow region shows the distribution of halo
profiles in the mass range within this bin.

###  3.3 $\chi^{2}$\- Analysis and Model Comparison

The efficacy of the dark matter analytic model fits to the simulation data
discussed in Section 3.2 has been gauged using the $\chi^{2}$ analysis
supplemented with information theory techniques such as Akaike and Bayesian
information criteria (Liddle, 2007). The $\chi^{2}$ statistics is first used
to determine the goodness of fit for the aforementioned models. We have
estimated the reduced $\chi^{2}$ for the fits which is given by,

$\displaystyle\rm{\chi^{2}}=\sum\bigg{(}\frac{\rho_{model}-\rho_{data}}{\sigma}\bigg{)}^{2}\quad
and\quad\rm{\chi^{2}_{red}}=\frac{\chi^{2}}{N-k}$ (7)

Here, $\rho_{model}$ is the density profile derived from the best fit values
for the analytical models used to fit the simulated stacks, whereas
$\rho_{data}$ and $\sigma$ denote the data-points and associated errors of the
stacks from simulated halo density profiles respectively, as described in
Section 3.2, $N$ is the total number of data points, $k$ is the number of free
parameters in each model, where the summation is done over all the data
points. Figure 3 represents the distribution of reduced-$\chi^{2}$ values for
the binned data. We infer that cored profiles such as isothermal or Burkert
provide egregious fits, whereas the NFW profile with reduced $\chi^{2}$
greater than one for many halos also does not provide a good description for
the full range of simulation data. However, we find that only the generalized
NFW profile can self-consistently fit these baryonified dark-matter halos with
reduced-$\chi^{2}$ close to one. Regardless, drawing a conclusion solely from
the reduced-$\chi^{2}$ values is not advisable as the models described here do
not have the same number of free parameters. Hence to assess the robustness of
gNFW fit relative to NFW, we have used the Akaike Information Criterion (AIC)
and the Bayesian Information Criterion (BIC) metrics to quantify the goodness
of fit. The AIC and BIC are defined as follows (Liddle, 2007):

$\displaystyle\rm{AIC}$ $\displaystyle=$
$\displaystyle\chi^{2}+2k+\frac{2k(k+1)}{N-k-1}$ (8) $\displaystyle\rm{BIC}$
$\displaystyle=$ $\displaystyle\chi^{2}+k\ln N,$ (9)

Mass-bin | gNFW | NFW
---|---|---
| AIC | BIC | AIC | BIC
Bin 1 | -127.5 | -124.2 | -122.1 | -119.7
Bin 2 | -135.3 | -131.9 | -127.8 | -125.5
Bin 3 | -140.6 | -137.3 | -131.9 | -129.6
Bin 4 | -146.1 | -142.8 | -136.4 | -134.0
Bin 5 | -156.1 | -152.8 | -145.2 | -142.9
Table 1:  This table shows the AIC-BIC values for both the gNFW and NFW fits
to the mass-binned stacks(Set 1) of the simulated halos. Since the fits for
the cored profiles were bad, we did not apply these AIC/BIC techniques to
them. Both AIC and BIC point to gNFW being the preferred profiles for all the
bins

When comparing two models, the model with the smaller value of AIC and BIC is
considered the favored one, and a difference of more than ten in AIC/BIC is
considered as decisive evidence in favor of the model with the lower value. We
have here conducted these model comparison tests for the three-parameter gNFW
profile which provides very good fits to all the dark matter halos than the
2-parameter NFW profile. We do not apply the AIC and BIC based tests to the
isothermal and Burkert profiles, as these models can be excluded based on
their large reduced $\chi^{2}$ values. The AIC and BIC values for the mass-
binned data are tabulated in Table 1 and we see the values for gNFW model are
consistently smaller than the NFW model for all the bins with the difference
equal to 5-10 depending on the mass bin.

Figure 3: Distribution of the reduced-$\chi^{2}$ values of the fits for
isothermal (orange), NFW (teal), gNFW (violet) and Burkert (blue) profiles to
the stacked data across the halo mass.

Therefore, since the gNFW profile is the most robust in terms of describing
the simulated halo density profiles based on the aforementioned statistical
tests, we shall derive all the other results based on the fits from this
profile for the remainder of this paper.

##  4 GNFW fits to Simulated halos

In this section, we shall discuss the best-fit gNFW parameters to the stacks
obtained from the mock catalogs. The density data for one such stacked profile
as shown in Figure 2 is fitted with a gNFW model (Eq. 6) by maximizing the
log-likelihood function using the emcee MCMC sampler (Foreman-Mackey et al.,
2013). The corner plots of the fit parameters associated with the gNFW model
for the mass binned data showing 68%, 90%, and 99% credible intervals can be
found in the Appendix. Figure 4 shows the distribution of the fit parameters
of a gNFW model for the Set 2 data, where the halos are binned with respect to
both the halo mass and the concentration. In this figure, the trend of the
gNFW parameters or a combination of them with the halo mass is depicted with
the five quantiles of the virial concentration represented using five distinct
symbols. The scale density ($\rho_{s}$) decreases with halo mass but increases
with $C_{vir}$, whereas $r_{s}$ shows an antipodal trend with the halo mass
and $C_{vir}$ to that of the density. The near-unity values of the inner-slope
($\alpha$) suggest an inner profile similar to that of the standard NFW halo,
which is further compounded by having the logarithmic slope nearly equal to -2
for this model as is shown in Figure 4.

Figure 4: The distribution of best-fit parameters of the gNFW profile as a
function of halo mass. The trend of the gNFW parameters with mass for
different $C_{vir}$ bins are designated using different colours. Bins 1, 2, 3,
4, and 5 are represented by green, red, blue, yellow, and violet colours,
respectively.

###  4.1 Scaling relation of $r_{s}$ with halo parameters

The mock catalogs discussed in Section 2 assume a $\Lambda$CDM cosmology, and
each simulated halo starts with its total matter density described with an NFW
profile that is consistent with the gravity-only simulation, where this mock
catalog is being generated with mass $M_{halo}=(4\pi/3)r_{vir}^{3}\times
200\rho_{crit}$ and $C_{vir}=r_{s}(NFW)/r_{vir}$ and later undergoing a
baryonification. These modified halos are better described by a generalized
NFW profile rather than with the NFW model, as shown in Section 3. The right
panel of Figure 5 shows the distribution of the scale-radius ($r_{s}(gNFW)$)
derived from the gNFW fits to the Set 2 data with their NFW scale radii
($r_{s}(NFW)$) calculated from the simulation parameters, $C_{vir}$ and
$M_{halo}$, which shows a tight positive correlation with an approximate slope
of unity, which implies that there is no considerable change between the gNFW
fit parameter, $r_{s}(gNFW)$ and that derived from the initial simulation
parameters. This is further compounded by the trend of the logarithmic slope
of $\rho_{s}$ with $M_{halo}$ that has values very close to -2 and depicts a
slightly negative trend with $M_{halo}$ and $C_{vir}$ (cf. Figure 4). The
tight positive scaling relation of $r_{s}(gNFW)$ with $M_{halo}$ in log-space
for the Set 1 data presented in Figure 5 (left panel) is given by,

$\log r_{s}=(0.54\pm 0.07)\log M_{halo}-(4.96\pm 0.84)$ (10)

From Eq. 10, we infer that the baryon-affected halos have their $r_{s}$
increasing with mass slightly faster than $M^{1/3}$, and $C_{vir}$ is
marginally decreasing with mass similar to the standard NFW halos.

Figure 5: Plot of gNFW scale-radius ($r_{s}$) as a function of halo mass in
log-space for the simulated data averaged over equal mass quantiles for Set 1
data (left panel).The gNFW scale radius versus the scale radius derived from
the simulation parameters $C_{vir}$ and $M_{halo}$ in log-space for the Set 2
data (right panel). The $r_{s}$ parameter in both X- and Y-axis is depicted in
the physical units of kpc. The colour bar in the right panel shows the virial
concentration associated with the simulated halos.

##  5 Results for halo density

Although the earliest studies of dark matter surface density were done using
the halo surface density defined in Eq. 1 (Donato et al., 2009), the dark
matter column density (Eq. 2) was found to be invariant with respect to the
posited dark matter density profile and hence, subsequently applied to
observational data for NFW (Boyarsky et al., 2009, 2010; Del Popolo et al.,
2013; Del Popolo & Lee, 2017) as well as Burkert profile (Gopika & Desai,
2021). Since neither the NFW nor any of the cored profiles could adequately
fit the density profiles of the simulated halos, we calculate the dark matter
column density using the three-parameter gNFW profile and use that as a proxy
for the dark matter halo surface density. The dark matter column density for a
gNFW profile is given by (Boyarsky et al., 2009):

$\displaystyle
S_{gNFW}(R)=\frac{2}{R^{2}}\int_{0}^{R}r^{\prime}dr^{\prime}\int_{-\infty}^{+\infty}dz\frac{\rho_{s}}{(r_{d}/r_{s})^{\alpha}(1+r_{d}/r_{s})^{3-\alpha}}$
(11) $\displaystyle\noindent\rm{where}\quad\quad r_{d}=\sqrt{r^{\prime
2}+z^{2}}$

The column densities for all these halos were determined from Eq. 11 by
numerical integration at $R=r_{s}$, where $r_{s}$ is the scale radius from the
gNFW fits. The double integration in the $S_{gNFW}$ function make the standard
error propagation intractable, since no closed form analytical solution is
available for $S_{gNFW}$. Hence, we have followed an alternative approach to
determine the errors. We have calculated the best-fit value and the associated
errors in $S_{gNFW}$ from the parameter space of the emcee MCMC sampler used
for the maximization of the log-likelihood function of the gNFW fits to
stacked density profiles. The median values of the aforementioned column-
density array give the best value for $S_{gNFW}$ and the 0.16 and 0.84
quantiles, from which one can estimate 1$\sigma$ errors for $S_{gNFW}$.

This plot of $S_{gNFW}$ as a function of halo mass can be found in Figure 6.
In the right panel, the variation of $S_{gNFW}$ with halo-mass for the Set 2
data is shown with each $C_{vir}$ bin being represented by a different colour.
We can see that there is a positive trend between $C_{vir}$ and $S_{gNFW}$ for
the same halo mass. Similarly, the plot in the left panel shows the $S_{gNFW}$
values for the Set 1 data, which have been calculated in five equal quantiles
of mass bins as a function of halo mass. We infer that $S_{gNFW}$ has at best
a weak dependence on $M_{halo}$, but definitely shows a strong dependence on
$C_{vir}$.

Figure 6: Plot of the dark matter column-density ($S_{gNFW}$) versus halo mass
($M_{halo}$) in log-space. The overall average trend of $S_{gNFW}$ with halo
mass from the Set 1 data (left panel) showcases a constant value with the
slope equal to $0.053\pm 0.09$ from a linear-fit. The trend of $S_{gNFW}$ with
log $M_{halo}$ and $C_{vir}$ are shown with $C_{vir}$ bins designated with
different colours (right panel).

The dark matter column density (after averaging over all concentrations)
(Figure 6) is given by,

$S_{gNFW}\propto M_{halo}^{0.053\pm 0.09}$ (12)

Therefore, given the current errors, $S_{gNFW}$ agrees with both a constant
value as well as a power law scaling with halo mass. Since all the previous
studies on the halo surface density have used either a cored or NFW profile, a
direct comparison of the absolute value of halo surface density with our
simulation results cannot be easily done.

##  6 Conclusions

A large number of studies have shown that the dark matter halo surface density
is constant for a whole suite of galaxies from dwarf galaxies to giant
elliptical galaxies over 18 decades in blue magnitude. This invariance of the
halo surface density however does not hold for galaxy clusters and galaxy
groups.

In order to ascertain if these predictions are consistent with $\Lambda$CDM,
we have investigated the density profiles of mock catalogs obtained using
baryonified Gravity-only $\Lambda$CDM simulations, which incorporate the
quasi-adiabatic relaxation of dark matter halos in the presence of baryons
(Paranjape et al., 2021). We tried to fit these halos with a variety of cored
and non-cored density profiles. Although, the cored isothermal or Burkert
profiles can adequately model the rotation curves of galaxies, groups, and
clusters (Salucci, 2019; Kormendy & Freeman, 2016; Chan, 2014), these cored
profiles as well as the cuspy NFW profiles fail to describe density profiles
of the mock catalogs, unlike the observed data. Therefore we cannot do a
direct detailed comparison to observational results done previously, since
they either assumed cored profiles (Donato et al., 2009; Zhou et al., 2020) or
NFW profiles (Boyarsky et al., 2009). The simulated halos could only be self-
consistently fitted using gNFW profiles over the full range of mass scales. As
proxy for the halo surface density, we calculated the dark matter column
density for the gNFW profile (cf. Eq. 6).

Our conclusions based on these studies are as follows:

  * •

The gNFW analytic model best describes the density profiles of the mock
simulation catalogs used in this paper. This is very evident from their
reduced $\chi^{2}$ analysis and model comparison tests such as AIC and BIC,
which confirm the fact that the cored or the NFW profiles do not provide a
good fit to these mock catalog objects.

  * •

The gNFW $r_{s}$ shows a tight positive correlation with halo mass and also a
slight decrease in the virial concentration as a function of halo mass which
is similar to that for the standard NFW halos. Furthermore, the gNFW $r_{s}$
values from the fits to the simulated profiles do not show much deviation from
the simulation values of $r_{s}(NFW)$.

  * •

The dark matter column-density is consistent with both a constant halo surface
density as a function of halo mass as well as a power-law dependence with halo
mass.

  * •

We also found that $S_{gNFW}$ is positively correlated with $C_{vir}$ for a
fixed halo mass. It would be interesting to compare this with observations.

In a follow-up work we also plan to extend these studies to cluster and group-
scale halos to ascertain if the simulations predict the elevated values for
the column density at these scales.

## Acknowledgements

The research of AP is supported by the Associateship Scheme of ICTP, Trieste.
GK acknowledges the Ministry of Education (MoE), Government of India for the
Senior Research Fellowship.

## Data Availability

The data used in this work is described in Paranjape et al. (2021) and can be
obtained from a reasonable request to the corresponding author of that paper.

## References

  * Abdalla et al. (2022) Abdalla E., et al., 2022, Journal of High Energy Astrophysics, 34, 49
  * Aghanim et al. (2020) Aghanim N., et al., 2020, A&A, 641, A6
  * Banik & Zhao (2022) Banik I., Zhao H., 2022, Symmetry, 14, 1331
  * Baushev (2014) Baushev A. N., 2014, A&A, 569, A114
  * Benisty (2021) Benisty D., 2021, Physics of the Dark Universe, 31, 100766
  * Berezhiani et al. (2018) Berezhiani L., Famaey B., Khoury J., 2018, J. Cosmology Astropart. Phys, 2018, 021
  * Boldrini (2021) Boldrini P., 2021, Galaxies, 10, 5
  * Bondarenko et al. (2018) Bondarenko K., Boyarsky A., Bringmann T., Sokolenko A., 2018, J. Cosmology Astropart. Phys, 2018, 049
  * Boyarsky et al. (2009) Boyarsky A., Ruchayskiy O., Iakubovskyi D., Maccio’ A. V., Malyshev D., 2009, arXiv e-prints, p. arXiv:0911.1774
  * Boyarsky et al. (2010) Boyarsky A., Neronov A., Ruchayskiy O., Tkachev I., 2010, Phys. Rev. Lett., 104, 191301
  * Breddels & Helmi (2013) Breddels M. A., Helmi A., 2013, A&A, 558, A35
  * Bull et al. (2016) Bull P., et al., 2016, Physics of the Dark Universe, 12, 56
  * Bullock & Boylan-Kolchin (2017) Bullock J. S., Boylan-Kolchin M., 2017, ARA&A, 55, 343
  * Burkert (1995) Burkert A., 1995, ApJ, 447, L25
  * Burkert (2015) Burkert A., 2015, ApJ, 808, 158
  * Burkert (2020) Burkert A., 2020, ApJ, 904, 161
  * Cardone & Del Popolo (2012) Cardone V. F., Del Popolo A., 2012, MNRAS, 427, 3176
  * Cardone & Tortora (2010) Cardone V. F., Tortora C., 2010, MNRAS, 409, 1570
  * Chan (2014) Chan M. H., 2014, MNRAS, 442, L14
  * Chavanis (2022) Chavanis P.-H., 2022, Physics of the Dark Universe, 37, 101098
  * Copi et al. (2010) Copi C. J., Huterer D., Schwarz D. J., Starkman G. D., 2010, Adv. Astron., 2010, 847541
  * Del Popolo (2009) Del Popolo A., 2009, ApJ, 698, 2093
  * Del Popolo (2023) Del Popolo A., 2023, Physics of the Dark Universe, 40, 101203
  * Del Popolo & Lee (2017) Del Popolo A., Lee X.-G., 2017, Astronomy Reports, 61, 1003
  * Del Popolo et al. (2013) Del Popolo A., Cardone V. F., Belvedere G., 2013, MNRAS, 429, 1080
  * Demiański & Doroshkevich (2014) Demiański M., Doroshkevich A. G., 2014, MNRAS, 439, 179
  * Di Valentino et al. (2021) Di Valentino E., et al., 2021, Classical and Quantum Gravity, 38, 153001
  * Donato et al. (2004) Donato F., Gentile G., Salucci P., 2004, MNRAS, 353, L17
  * Donato et al. (2009) Donato F., et al., 2009, MNRAS, 397, 1169
  * Famaey & McGaugh (2012) Famaey B., McGaugh S. S., 2012, Living Reviews in Relativity, 15, 10
  * Fields et al. (2020) Fields B. D., Olive K. A., Yeh T.-H., Young C., 2020, J. Cosmology Astropart. Phys, 2020, 010
  * Foreman-Mackey et al. (2013) Foreman-Mackey D., Hogg D. W., Lang D., Goodman J., 2013, PASP, 125, 306
  * Genina et al. (2018) Genina A., et al., 2018, MNRAS, 474, 1398
  * Gentile et al. (2007) Gentile G., Tonini C., Salucci P., 2007, A&A, 467, 925
  * Gopika & Desai (2020) Gopika K., Desai S., 2020, Physics of the Dark Universe, 30, 100707
  * Gopika & Desai (2021) Gopika K., Desai S., 2021, Physics of the Dark Universe, 33, 100874
  * Hayashi & Chiba (2015) Hayashi K., Chiba M., 2015, ApJ, 803, L11
  * Hayashi et al. (2020) Hayashi K., Chiba M., Ishiyama T., 2020, ApJ, 904, 45
  * Kaplinghat et al. (2016) Kaplinghat M., Tulin S., Yu H.-B., 2016, Phys. Rev. Lett., 116, 041302
  * Khelashvili et al. (2022) Khelashvili M., Rudakovskyi A., Hossenfelder S., 2022, arXiv e-prints, p. arXiv:2207.14165
  * Komatsu et al. (2011) Komatsu E., et al., 2011, ApJS, 192, 18
  * Kormendy & Freeman (2016) Kormendy J., Freeman K. C., 2016, ApJ, 817, 84
  * Liddle (2007) Liddle A. R., 2007, MNRAS, 377, L74
  * Lin & Loeb (2016) Lin H. W., Loeb A., 2016, J. Cosmology Astropart. Phys, 2016, 009
  * Macciò et al. (2008) Macciò A. V., Dutton A. A., van den Bosch F. C., 2008, MNRAS, 391, 1940
  * McGaugh et al. (2016) McGaugh S. S., Lelli F., Schombert J. M., 2016, Phys. Rev. Lett., 117, 201101
  * Meadows et al. (2020) Meadows N., Navarro J. F., Santos-Santos I., Benítez-Llambay A., Frenk C., 2020, MNRAS, 491, 3336
  * Merritt (2017) Merritt D., 2017, Studies in the History and Philosophy of Modern Physics, 57, 41
  * Milgrom (2009) Milgrom M., 2009, MNRAS, 398, 1023
  * Moore et al. (1999) Moore B., Quinn T., Governato F., Stadel J., Lake G., 1999, Monthly Notices of the Royal Astronomical Society, 310, 1147
  * Napolitano et al. (2010) Napolitano N. R., Romanowsky A. J., Tortora C., 2010, MNRAS, 405, 2351
  * Navarro et al. (1997) Navarro J. F., Frenk C. S., White S. D. M., 1997, ApJ, 490, 493
  * Newman et al. (2013a) Newman A. B., Treu T., Ellis R. S., Sand D. J., Nipoti C., Richard J., Jullo E., 2013a, ApJ, 765, 24
  * Newman et al. (2013b) Newman A. B., Treu T., Ellis R. S., Sand D. J., 2013b, ApJ, 765, 25
  * Ogiya & Mori (2011) Ogiya G., Mori M., 2011, ApJ, 736, L2
  * Paranjape & Sheth (2021) Paranjape A., Sheth R. K., 2021, MNRAS, 507, 632
  * Paranjape et al. (2021) Paranjape A., Choudhury T. R., Sheth R. K., 2021, MNRAS, 503, 4147
  * Paul et al. (2019) Paul N., Pahwa I., Paranjape A., 2019, MNRAS, 488, 1220
  * Peebles (2022) Peebles P. J. E., 2022, Annals of Physics, 447, 169159
  * Perivolaropoulos & Skara (2022) Perivolaropoulos L., Skara F., 2022, New A Rev., 95, 101659
  * Rocha et al. (2013) Rocha M., Peter A. H. G., Bullock J. S., Kaplinghat M., Garrison-Kimmel S., Oñorbe J., Moustakas L. A., 2013, MNRAS, 430, 81
  * Saburova & Del Popolo (2014) Saburova A., Del Popolo A., 2014, MNRAS, 445, 3512
  * Salucci (2019) Salucci P., 2019, A&A Rev., 27, 2
  * Salucci et al. (2012) Salucci P., Wilkinson M. I., Walker M. G., Gilmore G. F., Grebel E. K., Koch A., Frigerio Martins C., Wyse R. F. G., 2012, MNRAS, 420, 2034
  * Schneider & Teyssier (2015) Schneider A., Teyssier R., 2015, J. Cosmology Astropart. Phys, 2015, 049
  * Simon et al. (2005) Simon J. D., Bolatto A. D., Leroy A., Blitz L., Gates E. L., 2005, ApJ, 621, 757
  * Spano et al. (2008) Spano M., Marcelin M., Amram P., Carignan C., Epinat B., Hernandez O., 2008, MNRAS, 383, 297
  * Springel et al. (2008) Springel V., et al., 2008, MNRAS, 391, 1685
  * Strigari et al. (2010) Strigari L. E., Frenk C. S., White S. D. M., 2010, MNRAS, 408, 2364
  * Teyssier et al. (2011) Teyssier R., Moore B., Martizzi D., Dubois Y., Mayer L., 2011, MNRAS, 414, 195
  * Ureña-López et al. (2017) Ureña-López L. A., Robles V. H., Matos T., 2017, Phys. Rev. D, 96, 043005
  * Velmani & Paranjape (2023) Velmani P., Paranjape A., 2023, MNRAS, 520, 2867
  * Walker et al. (2010) Walker M. G., McGaugh S. S., Mateo M., Olszewski E. W., Kuzio de Naray R., 2010, ApJ, 717, L87
  * York et al. (2000) York D. G., et al., 2000, AJ, 120, 1579
  * Zehavi et al. (2011) Zehavi I., et al., 2011, ApJ, 736, 59
  * Zhao (1996) Zhao H., 1996, MNRAS, 278, 488
  * Zhou et al. (2020) Zhou Y., Del Popolo A., Chang Z., 2020, Physics of the Dark Universe, 28, 100468

##  Appendix A gNFW fits to Stacked data

In this section we shall discuss about fitting the gNFW profiles to the mass-
binned stacks from Set 1 data. The gNFW model fitting was done by maximising
the log-likelihood function given below:

$\displaystyle\ln\mathcal{L}=-0.5\sum\bigg{[}\bigg{(}\frac{\rho_{gNFW}-\rho_{data}}{\sigma}\bigg{)}^{2}+\ln(\sigma^{2})\bigg{]},$
(13)

where $\rho_{data}$ and $\sigma$ denote the mock density profiles and their
errors, respectively. We apply standard priors to the three free parameters,
$r_{s}$, $\rho_{s}$ and $\alpha$ of the gNFW model. A log-uniform prior was
employed for both $r_{s}$ and $\rho_{s}$ in the range $0<r_{s}<10^{3}$ and
$10^{-4}<\rho_{s}<10^{-1}$ respectively. For $\alpha$, we choose a uniform
prior between 0.8 and 1.6. For the MCMC runs, the number of walkers was set to
200 and the total number of iterations to 5000 which attained a mean
acceptance fraction of approximately 0.6 for these fits.

Figure 7 shows the MCMC corner plots showing the posterior distributions with
68%, 90% and 99 % credible intervals of the three free parameters of the gNFW
model, viz $\log r_{s}$, $\log\rho_{s}$, and $\alpha$, which were used for the
Set-1 data. The posterior distribution medians and their 1-$\sigma$
uncertainties are represented by vertical dashed lines in the histograms shown
diagonally in the corner plots. The corner plots associated with Set 1 data
are displayed in ascending order of mass with Figure 7(a) showing the lowest
mass bin and Figure 8(a), the highest mass bin.

(a) Mass bin 1

(b) Mass bin 2

(c) Mass bin 3

(d) Mass bin 4

Figure 7: Corner plots for the gNFW fits to Set 1 data. The plot shows the
68%, 90%, and 99% credible intervals. (a) Mass bin 5 Figure 8: Corner plots
for the gNFW fits to Set 1 data. The plot shows the 68%, 90%, and 99% credible
intervals. (cont.)


#  A 5-approximation Algorithm for 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 tournament timetabling, which asks us to design a double round-robin
schedule such that the total traveling distance of all $n$ teams is minimized
under the constraints that each pair of teams plays one game in each other’s
home venue, and each team plays at most $k$-consecutive home games or away
games. Westphal and Noparlik (Ann. Oper. Res. 218(1):347-360, 2014) claimed a
$5.875$-approximation algorithm for all $k\geq 4$ and $n\geq 6$. However,
there were both flaws in the construction of the schedule and in the analysis.
In this paper, we show that there is a 5-approximation algorithm for all $k$
and $n$. Furthermore, if $k\geq n/2$, the approximation ratio can be improved
to 4.

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

##  1 Introduction

In the field of sports scheduling [21], 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 2 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 starts, all teams are at home, and
they will return home after the last game ends. 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 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 the bounded-by-$k$
constraint loses meaning and a team can schedule their travel distance as
short as that in the traveling salesman problem (TSP).

The input of TTP-$k$ is a complete graph where each vertex represents a team
and the distance between two vertices $i$ and $j$, denoted by $d(i,j)$, is the
distance from the home of team $i$ to the home of team $j$. In this paper, we
only consider the case that the distance function $d$ satisfies the symmetry
and triangle inequality properties, i.e., $d(i,j)=d(j,i)$ and $d(i,h)\leq
d(i,j)+d(j,h)$ for all $1\leq i,j,h\leq n$.

TTP-$k$ is a difficult optimization problem. Readers can refer to [4, 10] for
an overview. For the case of $k=1$, the problem is infeasible [8]. For $3\leq
k=O(1)$ or $k=n-1$, the NP-hardness has been established [3, 25, 5]. Recently,
Bendayan _et al._ [2] further proved the APX-hardness for $k=n-1$. 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 [26, 29, 32, 31, 6, 18, 23, 16, 17] and heuristic algorithms [12,
22, 1, 9, 13, 14].

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

In terms of approximation algorithms, almost all 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$,
the approximation ratios for even $n/2$ and odd $n/2$ have been improved to
$(1+3/n)$ and $(1+5/n)$ [33]. For $k=3$ and $k=4$, the best approximation
ratios are $(139/87+\varepsilon)$ and $(17/10+\varepsilon)$, respectively
[34]. For $5\leq k=o(n)$, the ratio is $(5k-7)/(2k)+O(k/n)$ [30]. For $k=n-1$,
Imahori  _et al._ [19] proposed a $2.75$-approximation algorithm. At the same
time, Westphal and Noparlik [28] claimed a $5.875$-approximation algorithm for
all $k\geq 4$ and $n\geq 6$. However, there were two flaws in the algorithm
and analysis. The first one is in the construction of the schedule which can
lead to the output of an infeasible solution. The second one is in the
analysis of the total cost which can lead to a worse approximation ratio. To
explain the flaws clearly, we give the details in the appendix.

In this paper, we will show that there is a 5-approximation algorithm for
TTP-$k$ with all $k$ and $n$. The approximation ratio can be further improved
to 4 if $k\geq n/2$. Our algorithm uses a similar construction in [28]. We
will avoid the flaw and introduce the algorithm in a randomized way, which
will simplify our analysis. For the analysis, we refined some lower bounds and
analyze the solution quality in a different way by using the refined bounds.

Our algorithm will be introduced in Section 2. In Section 2.1, we show the
framework of our approximation algorithm, and the randomzied algorithm to
generate our parameters. In Section 2.2, we explain the main construction
algorithm in detail and prove its feasibility. In Section 3, we analyze the
approximation quality of our algorithm. Specifically, in Section 3.1 we
propose some useful bounds, in Section 3.2 we do some analysis, and in Section
3.3, we improve the approximation ratio. Section 4 makes some concluding
remarks. We also show the flaw in the previous construction in Appendix A and
the flaw in the previous analysis in Appendix B.

##  2 The Algorithm

Let $n$ denote the number of teams, where $n$ is even. The set of $n$ teams is
denoted by $\\{t_{1},t_{2},\dots,t_{n}\\}$. We use $G=(V,E)$ to denote the
complete graph on $n$ vertices $\\{1,2,\dots,n\\}$ representing the $n$ teams.
There is a distance/length function $d:E\to\mathbb{R}_{\geq 0}$ on the edges
of $G$. The distance of edge $ij$, denoted by $d(i,j)$, is the distance
between the homes of teams $t_{i}$ and $t_{j}$. We also let $s(i)=\sum_{j\neq
i}d(i,j)$, i.e., the total distance of edges incident on vertex $i$ in $G$,
and let $\Delta=\sum_{i}s(i)$. Given any (Hamiltonian) cycle $T$ of graph $G$,
we use $d(T)$ to denote the length of $T$, i.e., the total length of edges on
$T$. We use $T^{*}$ to denote an optimal Hamiltonian cycle, i.e., the
Hamiltonian cycle with a minimum length. In this paper, we consider that $k$
is a part of the input. Recall that TTP-1 is infeasible [8], and for TTP-$k$
with $k\geq n$, the problem is equivalent with TTP-$(n-1)$. Hence, we assume
w.l.o.g. that $2\leq k<n$.

###  2.1 The Algorithm Framework

Assume that we are given a Hamiltonian cycle $T$ of graph $G$, which can be
computed by a polynomial-time approximation algorithm. Let
$\sigma:V\leftrightarrow\\{1,\dots,n\\}$ be a permutation of the $n$ teams,
i.e., a bijection label function that maps the $n$ teams. Specifically, we
assume that the team represented by the number $i$ is labeled as $t_{i}$. Let
$l\in\\{1,2,\dots,k\\}$ be a parameter. Given $\sigma$ and $l$, we will
construction a feasible schedule for the teams. The construction algorithm is
denoted by CONS($\sigma$,$l$). We delay the description of CONS($\sigma$,$l$)
to the next subsection.

For every different $\sigma$ and $l$ we can get a feasible solution. To get a
solution, we want to find good parameters $\sigma$ and $l$. We will use a
simple randomized algorithm to generate the two parameters. The algorithm can
be easily derandomized in polynomial time and it will simplify the analysis.

The randomized algorithm contains the following three steps.

Step 1. Select one vertex from $T$ such that the total distance of edges
incident on it is minimized, and label it as $n$.

Step 2. Let $T^{\prime}$ be the cycle obtained by shortcutting the vertex $n$
from $T$. W.l.o.g., orient $T^{\prime}$ with an arbitrary direction. To label
the vertices of $T^{\prime}$, we choose one vertex of $T^{\prime}$ uniformly
at random, label it as $1$, and then label the vertices $2,3,\dots,n-1$
following the orientation of $T^{\prime}$, respectively. Note that there are
$n-1$ cases to label the oriented cycle $T^{\prime}$.

Step 3. The team represented by the vertex $i$ is labeled as $t_{i}$.

  * •

If $k<n/2$, the parameter $l$ is taken from $\\{1,2,\dots,k\\}$ uniformly at
random;

  * •

Otherwise, let $l=n/2-1$.

The randomized algorithm will generate two randomized parameters $\sigma$ and
$l$. In order to simplify the argument and analysis, we first derandomize the
parameter $l$ as follows: If $k<n/2$, compute CONS($\sigma$,$l$) for each
$l\in\\{1,2,\dots,k\\}$, and return the best one from the $k$ schedules. The
derandomization only increases a factor of $k$ in the running time. Next, we
assume that $l$ is a fixed parameter chosen as above. When we talk about
expectation, it means the expectation with respect to $\sigma$.

###  2.2 The Construction Algorithm

In this subsection, we introduce the construction algorithm
CONS($\sigma$,$l$). Given fixed $\sigma$ and $l$, we describe the
construction. Recall that the schedule contains $2(n-1)$ days, and each day
contains $m\coloneqq n/2$ games. It can be split into two _seasons_ , where
the first $n-1$ days are seen as the first season, and the other $n-1$ days
are seen as the second season.

####  2.2.1 The framework of the construction

We first show the games in the first season.

On the first day of the schedule, the games are shown in Figure 1. The last
team $t_{n}$ is represented by a double-cycle node, while each of the other
$n-1$ teams is represented by a single-cycle. Within this figure, there are
$m$ directed edges between teams, where a directed edge from team
$t_{i^{\prime}}$ to team $t_{i^{\prime\prime}}$ means a game between these two
teams, with the game taking place at the home venue of team
$t_{i^{\prime\prime}}$. Thus, the $n$ teams form $m$ games. For the sake of
presentation, the setting of the directions of these edges is explained later.
We can currently ignore the boxes in the figure now.

$t_{20}$$t_{10}$$t_{1}$$t_{19}$$t_{11}$$t_{9}$$t_{2}$$t_{18}$$t_{12}$$t_{8}$$t_{3}$$t_{17}$$t_{13}$$t_{7}$$t_{4}$$t_{16}$$t_{14}$$t_{6}$$t_{5}$$t_{15}$
Figure 1: The schedule on the first day, where $n=20$, $k=4$, $l=2$, and $b=4$

On the second day of the schedule, the position of the double-cycle node
representing team $t_{n}$ remains unchanged. However, the positions of the
$n-1$ single-cycle nodes representing the other teams are altered by shifting
them one position in the counterclockwise direction. An illustration of the
schedule on the second day is shown in Figure 2.

$t_{20}$$t_{1}$$t_{11}$$t_{10}$$t_{2}$$t_{19}$$t_{12}$$t_{9}$$t_{3}$$t_{18}$$t_{13}$$t_{8}$$t_{4}$$t_{17}$$t_{14}$$t_{7}$$t_{5}$$t_{16}$$t_{15}$$t_{6}$
Figure 2: The schedule on the second day, where $n=20$, $k=4$, $l=2$, and
$b=4$

Analogously, we obtain the games on rest days in the first season based on the
rotation scheme.

The first season can be presented by
$\Gamma_{1}\cdot\Gamma_{2}\cdots\Gamma_{n-2}\cdot\Gamma_{n-1}$, where
$\Gamma_{i}$ denotes the $m$ games on the $i$-th day. In the first season, it
is easy to see that every pair of teams has played exactly once. Let
$\overline{\Gamma_{i}}$ denote the $m$ games of $\Gamma_{i}$ but with reversed
home venues. Then, there are still $n-1$ days of unarranged games
$\\{\overline{\Gamma_{1}},\overline{\Gamma_{2}},\dots,\overline{\Gamma_{n-1}}\\}$,
which will be arranged in the second season in the order of
$\overline{\Gamma_{n-2}\cdot\Gamma_{n-1}\cdot\Gamma_{1}\cdot\Gamma_{2}\cdots\Gamma_{n-3}}$.
Therefore, the complete schedule can be presented by

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

####  2.2.2 The details of the construction

Recall that $l\in\\{1,2,\dots,k\\}$ is an input of the algorithm. Let
$b\coloneqq\lceil\frac{m-l-1}{k}\rceil+2$. To determine the directions of the
edges in the schedule, we divide them into $b$ blocks, as shown in Figures 1
and 2. Each block contains a specific number of edges, known as its width. We
denote the width of the $i$-th block, from left to right, as $w_{i}$. In our
construction, we set $w_{1}=1$, $w_{2}=m-1-(b-3)k-l$, $w_{i}=k$ for
$i=3,\dots,b-1$, and $w_{b}=l$. Note that the sum of the widths of all the
blocks equals the total number of edges, i.e., $\sum_{i=1}^{b}w_{i}=m$.

When $k<n/2$, with $l\in\\{1,2,\dots,k\\}$, there are $k$ cases to consider.
On the other hand, when $k\geq n/2$, we only need to consider the case where
$l=n/2-1$. In this specific case, there are only two blocks: the first block
with width $w_{1}=1$ and the second block with width $w_{2}=m-1$.
Additionally, if $(m-1-l)\bmod k=0$, we have $w_{2}=k$; otherwise, we have
$w_{2}=(m-1-l)\bmod k$.

Note that the directions of the edges in the second season are arranged based
on the first season. Hence, we only explain the directions of the edges in the
first season. There are two rules.

Rule 1. Initially, the directions of edges in the same block typically are the
same, and the direction in each block alternatively changes from the $2$-nd
block to the $b$-th block. Moreover, the direction of the edge in the 1-st
block is from left to right while the directions of the edges in the 2-nd
block are from above to below. This arrangement ensures that, in Figure 1, the
directions of the edges in the 3-rd block are from below to above, the
directions of the edges in the 4-th block are from above to below, and so on.
Since every $i$-th block with $3\leq i\leq b-1$ has a width of $k$, this can
make sure that every team plays $k$-consecutive home/away games from the
beginning of the entry to the end of the exit within one season. And, it helps
prevent any team from playing more than $k$-consecutive home/away games since
the direction in each block alternatively changes. A special case is that

  * •

if $w_{2}=k$, we will reverse the direction of the most left edge in the 2-nd
block, i.e., the edge $t_{1}\rightarrow t_{19}$ in Figure 1, for all days in
the first season.

Therefore, there are at most $k-1$ edges with the same direction in the 2-nd
block. One can imagine that the 2-nd block is further divided into two blocks
in this case.

Rule 2. Then, we make sure that the direction of the most left edge, which is
incident on team $t_{n}$, changes every $k$-th day, while the directions of
the remaining $m-1$ edges remain unchanged. This means that for the edge
$t_{20}\rightarrow t_{10}$ in Figure 1, the direction is from left to right on
the 1-st day to the $k$-th day, from right to left on the $(k+1)$-th day to
the $2k$-th day, and so on. In the specific case where $k=4$, it is noteworthy
that the directions of the edges on the second day, as shown in Figure 2, are
the same as those on the first day depicted in Figure 1. Moreover, let
$r=(n-1)\bmod 2k$. A special case is that

  * •

if $r\leq k<n-1$, we will reverse the most left edge only on the 1-st day.

The reason is that we need to ensure that team $t_{n}$ dose not play more than
$k$-consecutive home/away games during the transition between the first and
second seasons.

####  2.2.3 The feasibility of the construction

We first show that in the construction all teams will not play more than
$k$-consecutive home/away games.

######  Lemma 1.

No teams play more than $k$-consecutive home/away games.

###### Proof.

Consider an arbitrary team $t_{i}$ with $i<n$. Recall that there are at most
$k-1$ edges with the same direction in the 2-nd block. The construction is
based on the rotation scheme. It is easy to verify that $t_{i}$ plays at most
$k$-consecutive home/away games in the first season. The second season uses
the same rotation scheme. Analogously, $t_{i}$ also plays at most
$k$-consecutive home/away games in the second season. If $t_{i}$ plays more
than $k$-consecutive home/away games, then these games must include the last
day of the first season and the first day of the second season, i.e.,
$\Gamma_{n-1}$ and $\overline{\Gamma_{n-2}}$. Therefore, $t_{i}$ plays both
home/away games in these two days. We assume w.l.o.g. that $t_{i}$ plays home
games. Then, it plays away games in $\Gamma_{n-2}$ and
$\overline{\Gamma_{n-1}}$. Note that these four days are arranged in the order
of
$\Gamma_{n-2}\cdot\Gamma_{n-1}\cdot\overline{\Gamma_{n-2}\cdot\Gamma_{n-1}}$.
Hence, there are at most $2$-consecutive home games containing $\Gamma_{n-1}$
and $\overline{\Gamma_{n-2}}$, a contradiction.

Next, we consider team $t_{n}$. Recall that $r=(n-1)\bmod 2k$. We consider the
home/away patterns of team $t_{n}$ in the first and the second seasons. For
the sake of presentation, we use ‘$H^{p}$’ and ‘$A^{p}$’ to denote
$p$-consecutive home games and $p$-consecutive away games, respectively. We
consider the following two cases.

Case 1: $r>k$. Recall that the direction of the most left edge (incident on
team $t_{n}$) changes every $k$-th day. The home/away pattern of team $t_{n}$
in the first season is $A^{k}H^{k}\cdots A^{k}H^{k}A^{k}H^{r-k}$. In the
second season, if $r-k=1$, the pattern is $HAH^{k}A^{k}\cdots
H^{k}A^{k}H^{k-1}$; otherwise, the pattern is $A^{2}H^{k}A^{k}\cdots
H^{k}A^{k}H^{k}A^{r-k-2}$. In both cases, the patterns in these two seasons
can be combined well without creating more than $k$-consecutive home/away
games.

Case 2: $r\leq k$. Recall that we further reverse the most left edge on the
1-st day if $r\leq k<n-1$. Note that we have $r\geq 1$ since $n$ is even. If
$k\geq n-1$, the pattern is obviously feasible. If $k<n-1$, since $r\leq k$,
we have $n-1>2k$. Therefore, the home/away pattern of team $t_{n}$ in the
first season is $HA^{k-1}H^{k}\cdots A^{k}H^{k}A^{r}$. In the second season,
if $r=1$, the pattern is $AHAH^{k-1}A^{k}\cdots H^{k}A^{k-1}$; otherwise, the
pattern is $H^{2}AH^{k-1}A^{k}\cdots H^{k}A^{k}H^{r-2}$. The patterns in these
two seasons will not create more than $k$-consecutive home/away games. ∎

######  Theorem 2.

The construction is feasible for any $k\geq 2$.

###### Proof.

Recall that $\Gamma_{i}$ denotes the $m$ games of the schedule on the $i$-th
day.

First, we prove that the schedule is a complete double round-robin. It is
well-known that the rotation scheme in the construction can decompose a
complete graph $G$ into $n-1$ edge-disjoint perfect matchings, i.e.,
$G=\Gamma_{1}\cup\Gamma_{2}\cup\cdots\Gamma_{n-2}\cup\Gamma_{n-1}$ if we take
$\Gamma_{i^{\prime}}$ as an undirected matching by taking each game
$t_{i}\rightarrow t_{j}$ on that day as an edge $t_{i}t_{j}$. Analogously, we
can take $\Gamma_{i^{\prime}}$ (resp., $\overline{\Gamma_{i^{\prime}}}$) as a
directed matching by taking each game $t_{i}\rightarrow t_{j}$ on that day as
a directed edge $t_{i}t_{j}$ (resp., $t_{j}t_{i}$), and then
$\Gamma_{1}\cup\Gamma_{2}\cup\cdots\Gamma_{n-2}\cup\Gamma_{n-1}\cup\overline{\Gamma_{1}\cup\Gamma_{2}\cup\cdots\Gamma_{n-2}\cup\Gamma_{n-1}}$
forms a bi-directed complete graph. Note that the bi-directed complete graph
represents the $n(n-1)$ games. Hence, all games are contained exactly once in
the $2(n-1)$ days
$\Gamma_{1}\cup\Gamma_{2}\cup\cdots\Gamma_{n-2}\cup\Gamma_{n-1}\cup\overline{\Gamma_{1}\cup\Gamma_{2}\cup\cdots\Gamma_{n-2}\cup\Gamma_{n-1}}$.
The schedule is a complete double round-robin.

Then, we prove that the schedule satisfies the no-repeat constraint. For each
pair of teams, the two games between them are arranged in $\Gamma_{i}$ and
$\overline{\Gamma_{i}}$ with some $i$, respectively. It is easy to see that
the schedule
$\Gamma_{1}\cdot\Gamma_{2}\cdots\Gamma_{n-2}\cdot\Gamma_{n-1}\cdot\overline{\Gamma_{n-2}\cdot\Gamma_{n-1}\cdot\Gamma_{1}\cdot\Gamma_{2}\cdots\Gamma_{n-3}}$
satisfies the constraint.

Last, for the bounded-by-$k$ constraint, it follows directly from Lemma 1. ∎

Next, we are ready to analyze the approximation quality of our algorithm in
Section 2.1.

##  3 Analyzing the Approximation Quality

In this section, we introduce a novel framework that differs from the one
presented in [28]. Our refined analysis within this framework yields an
improved 5-approximation ratio. Importantly, this ratio holds for a wide range
of meaningful values for the parameters $k$ and $n$. Specifically, it applies
to any $k$ and $n$ satisfying the conditions $n>k\geq 2$ and $n\geq 4$.

To facilitate the analysis, we use OPT to denote the total traveling distance
of all teams in an optimal solution. Next, we present several useful bounds.

###  3.1 Some Bounds

First, we recall some well-known lower bounds for TTP-$k$.

######  Lemma 3 ([28]).

$nd(T^{*})\leq\mbox{OPT}$.

######  Lemma 4 ([28]).

$\Delta\leq(k/2)\cdot\mbox{OPT}$.

Note that Imahori _et al._ [19] proved that $\Delta\leq(n^{2}/4)d(T^{*})$. By
Lemma 3, we have the following lemma.

######  Lemma 5 ([19]).

$\Delta\leq(n/4)\cdot\mbox{OPT}$.

Then, to analyze the weight of our schedule, we define some notations and
explore their properties. Recall that the construction contains $2(n-1)$ days,
and each day contains $m=n/2$ games. Let $d_{i}(j)$ (resp., $e_{i}(j)$) denote
the distance (resp., edge) between two vertices representing the two teams in
the $i$-th game (from left to right) on the $j$-th day, where $1\leq i\leq m$
and $1\leq j\leq 2(n-1)$. For example, in Figure 1, we have
$d_{1}(1)=d(20,10)$ and $d_{2}(1)=d(1,19)$.

######  Lemma 6.

$\sum_{i=1}^{m}\sum_{j=1}^{2(n-1)}d_{i}(j)=\Delta$.

###### Proof.

Since the schedule is a double round-robin, it contains exactly two games
between any pair of two teams. Recall that $\Delta$ is twice the total
distance of all edges in $G$. So, the lemma holds. ∎

######  Lemma 7.

$\sum_{j=1}^{2(n-1)}d_{1}(j)=2s(n)$.

###### Proof.

It follows directly from that the most left game always involves team $t_{n}$,
and $t_{n}$ meets every other team twice in the double round-robin schedule. ∎

######  Lemma 8.

For any $1\leq i\leq m$ and $1\leq j\leq 2(n-1)$, we have
$\mathbb{E}[d_{i}(j)]=\frac{1}{2(n-1)}\sum_{j=1}^{2(n-1)}d_{i}(j)$.

###### Proof.

The construction is based on the rotation scheme, which makes sure that in the
construction the positions of the $n-1$ teams
$\\{t_{1},t_{2},\dots,t_{n-1}\\}$ always correspond to the same cycle
$T^{\prime}$ on different days. Recall that we label $T^{\prime}$ in the order
of $1,2,\dots,n-1$ uniformly at random from the $n-1$ cases and $d_{i}(j)$ is
the distance of edge $e_{i}(j)$.

Case 1: $i=1$. It is easy to see that $e_{i}(j)$ corresponds to an edge
incident to $n$. There are $n-1$ edges with a total weight of $s(n)$. The
probability of each of them being $e_{i}(j)$ is $\frac{1}{n-1}$. Hence, by
Lemma 7, we have $\mathbb{E}[d_{i}(j)]=\frac{1}{n-1}\cdot
s(n)=\frac{1}{2(n-1)}\sum_{j=1}^{2(n-1)}d_{i}(j)$.

Case 2: $i>1$. By the construction, we know that $e_{i}(j)$ corresponds to an
edge with the labels of its two vertices differing by $i-1$ on $T^{\prime}$.
Since $T^{\prime}$ contains $n-1$ (odd) vertices, there are $n-1$ such edges
with a total weight of $\frac{1}{2}\sum_{j=1}^{2(n-1)}d_{i}(j)$. The
probability of each of them being $e_{i}(j)$ is also $\frac{1}{n-1}$. Hence,
we have $\mathbb{E}[d_{i}(j)]=\frac{1}{2(n-1)}\sum_{j=1}^{2(n-1)}d_{i}(j)$.

So, the lemma holds. ∎

Note that the part $\sum_{j=1}^{2(n-1)}d_{i}(j)$ in Lemma 8 is a constant for
any $1\leq i\leq m$ (here the constant means a value that stays unchanged for
the $n-1$ cases of labeling $1,2,\dots,n-1$). For $i=1$, we have
$\sum_{j=1}^{2(n-1)}d_{i}(j)=2s(n)$ by Lemma 7, which is a constant obviously.
For $i>1$, by the labels of teams in the schedule,
$\sum_{j=1}^{2(n-1)}d_{i}(j)$ is twice the total distance of all edges where
the labels of vertices of each edge differ by $i-1$ on the cycle $T^{\prime}$,
which is also a constant.

######  Lemma 9.

For any $1\leq j\leq 2(n-1)$, we have
$\mathbb{E}[\sum_{i=1}^{m}d_{i}(j)]=\frac{\Delta}{2(n-1)}$.

###### Proof.

Note that
$\mathbb{E}\left[\sum_{i=1}^{m}d_{i}(j)\right]=\sum_{i=1}^{m}\mathbb{E}[d_{i}(j)]$.
By Lemmas 6 and 8, we have

$\sum_{i=1}^{m}\mathbb{E}[d_{i}(j)]=\frac{1}{2(n-1)}\sum_{i=1}^{m}\sum_{j=1}^{2(n-1)}d_{i}(j)=\frac{\Delta}{2(n-1)}.$

∎

######  Lemma 10.

For any $1\leq i\leq m$ and $1\leq j\leq 2(n-1)$, we have
$\mathbb{E}[d_{i}(j)]\leq 2\cdot\mathbb{E}[d_{1}(j)]$.

###### Proof.

The case $i=1$ obviously holds. We consider $i>1$. By Lemma 8, it is
sufficient to prove

$\sum_{j=1}^{2(n-1)}d_{i}(j)\leq 2\sum_{j=1}^{2(n-1)}d_{1}(j).$

In the construction, there are two teams in the $i$-th game, from left to
right, on the $j$-th day, including one upper team and one lower team for each
$i>1$. Let $a_{i}(j)$ and $b_{i}(j)$ be the vertices representing the upper
and lower teams, respectively. For example, in Figure 1, we have $a_{2}(1)=1$
and $b_{2}(1)=19$. Then, we have $d_{i}(j)=d(a_{i}(j),b_{i}(j))$. By the
triangle inequality, we have $d(a_{i}(j),b_{i}(j))\leq
d(a_{i}(j),n)+d(n,b_{i}(j))$. Hence,

$\sum_{j=1}^{2(n-1)}d_{i}(j)=\sum_{j=1}^{2(n-1)}d(a_{i}(j),b_{i}(j))\leq\sum_{j=1}^{2(n-1)}(d(a_{i}(j),n)+d(n,b_{i}(j))).$

By the rotation scheme of the construction, it is easy to see that each team
of $\\{t_{1},t_{2},\dots,t_{n-1}\\}$ goes through twice on the upper and lower
positions, respectively. Hence, by Lemma 7, we have

$\sum_{j=1}^{2(n-1)}(d(a_{i}(j),n)+d(n,b_{i}(j)))=\sum_{i=1}^{n-1}(2d(i,n)+2d(n,i))=4s(n)=2\sum_{j=1}^{2(n-1)}d_{1}(j).$

∎

######  Lemma 11.

For any $1\leq j\leq 2(n-1)$, we have
$\mathbb{E}[d_{1}(j)]\leq\frac{\Delta}{n(n-1)}$.

###### Proof.

By Lemmas 7 and 8, we have

$\mathbb{E}[d_{1}(j)]=\frac{1}{2(n-1)}\sum_{j=1}^{2(n-1)}d_{1}(j)=\frac{1}{2(n-1)}\cdot
2s(n)\leq\frac{\Delta}{n(n-1)},$

where the inequality follows from $s(n)\leq(1/n)\Delta$ because the vertex $n$
is selected with the total distance of edges incident on it minimized in the
algorithm. ∎

######  Lemma 12.

For any $1\leq j\leq 2(n-1)$, we have
$\mathbb{E}[d_{2}(j)]=\frac{d(T^{\prime})}{n-1}$.

###### Proof.

Recall that $\sum_{j=1}^{2(n-1)}d_{i}(j)$ is twice the total distance of all
edges where the labels of vertices of each edge differ by $i-1$ on the cycle
$T^{\prime}$. So, we have $\sum_{j=1}^{2(n-1)}d_{2}(j)=2d(T^{\prime})$. By
Lemma 8, we have

$\mathbb{E}[d_{2}(j)]=\frac{1}{2(n-1)}\sum_{j=1}^{2(n-1)}d_{2}(j)=\frac{1}{2(n-1)}\cdot
2d(T^{\prime})=\frac{d(T^{\prime})}{n-1}.$

∎

###  3.2 The Analysis

Recall that all teams are at home on the $0$-th and $(2n-1)$-th days. To
analyze the expected cost of the schedule, we calculate the total expected
cost of all _moves_ of all teams in the schedule, where all teams make one
move from the game venue on the $i$-th day to the game venue on the $(i+1)$-th
day ($0\leq i\leq 2n-2$). Note that if a team plays two home games on two
consecutive days, then the cost of the move is 0. If a team plays two away
games on two consecutive days, we call the move an _away-move_ , which
corresponds to a move between two opponents’ venues. If a team plays only one
away game on two consecutive days, we call the move a _home-move_ , which
corresponds to a move from/to its home venue. Then, we only need to consider
all teams’ away-moves and home-moves.

For the sake of analysis, we make two assumptions that will not decrease the
cost of the schedule by the triangle inequality.

######  Assumption 13.

We assume that there is a home day between the last day of the first season
and the first day of the second season, where all teams are at home.

After Assumption 13, we can analyze the total expected cost of all moves from
the $0$-th day to the home day in the first season and then from the home day
to the $(2n-1)$-th day in the second season, separately.

######  Assumption 14.

Supposing team $t_{i}$ plays with $t_{n}$ on the $j$-th day, we assume that
both $t_{i}$ and $t_{n}$ return home after the games on the $(j-1)$-th and the
$j$-th days, respectively.

Both Assumptions 13 and 14 will not decrease the cost of the schedule by the
triangle inequality. Typically, a team only makes one move on two consecutive
days. However, after Assumption 14, a team may make an extra move. For
example, $t_{i}$ plays an away game with $t_{j}$ on the $(i^{\prime}-1)$-th
day, and then plays an away game with $t_{n}$ on the $i^{\prime}$-th day,
where $t_{i}$ should make one move from the venues of $t_{j}$ to $t_{n}$.
After the assumption, $t_{i}$ will make two moves: one is from the venues of
$t_{j}$ to $t_{i}$ on the $(i^{\prime}-1)$-th day, and the other is from the
venues of $t_{i}$ to $t_{n}$ on the $i^{\prime}$-th day. Both moves of $t_{i}$
involve its home venue, and hence are home-moves. Moreover, after Assumption
14, a team makes an away-move only if it plays two consecutive away games in
the same block within one season.

Since $\mathbb{E}[d_{i}(j)]$, the expected distance of edge $e_{i}(j)$, is
always the same for any $1\leq j\leq 2(n-1)$, we simply let
$d_{i}\coloneqq\mathbb{E}[d_{i}(j)]$ and denote the corresponding edge by
$e_{i}$.

Next, we analyze the total expected cost of all moves in the first season.

From the $0$-th day to the $1$-st day. Since all teams are at home on the
$0$-th day and there are $m$ games on the $1$-st day, we know that there are
$m$ home-moves corresponding to the $m$ edges $e_{1},\dots,e_{m}$,
respectively. The total expected cost of all moves is

$\displaystyle\sum_{i=1}^{m}d_{i}=\frac{\Delta}{2(n-1)},$ (1)

where the equation follows from Lemma 9.

From the $i$-th day to the $(i+1)$-th day ($1\leq i\leq n-2$). There are two
cases: $k<n/2$ and $k\geq n/2$.

Case 1: $k<n/2$. Recall that the algorithm selects the best $l$ from
$\\{1,2,\dots,k\\}$, and the construction contains
$b=\lceil\frac{m-l-1}{k}\rceil+2$ blocks, where the widths are $w_{1}=1$,
$w_{2}=m-1-(b-3)k-l$, $w_{i}=k$ ($i=3,\dots,b-1$), and $w_{b}=l$. So, these
$b$ blocks can be presented by

$(e_{1}),(e_{2},\dots,e_{1+w_{2}}),(e_{2+w_{2}},\dots,e_{1+w_{2}+w_{3}}),\dots,(e_{m-1+l},\dots,e_{m}).$

We first consider away-moves. After Assumption 14, an away-move happens only
in the same block. By the construction, it corresponds to an edge of
$T^{\prime}$. Since we label $T^{\prime}$ uniformly at random from the $n-1$
cases, the expected cost of an away-move is $\frac{d(T^{\prime})}{n-1}$, which
equals to $d_{2}$ by Lemma 12. Recall that $\sum_{i=1}^{b}w_{i}=m$. Typically,
there are $w_{i}-1$ away-moves in the $i$-th block with width $w_{i}$, and
then $\sum_{i=1}^{b}(w_{i}-1)=m-b$ away-moves in total. One special case is
that when $w_{2}=k$, i.e., $(m-l-1)\bmod k=0$, we further reverse the
direction of the most left edge in the $2$-nd block, there will be one less
away-move in the $2$-nd block, and then we have $m-b-1$ away-moves in total
(we can imagine that the $2$-nd block is divided into two blocks, and hence
there are $b+1$ blocks in total). For all $k$ cases of
$l\in\\{1,2,\dots,k\\}$, there is only one case with $w_{2}=k$. Recall that
$b=\left\lceil\frac{m-1-l}{k}\right\rceil+2$. Hence, for all these $k$ cases,
the total expected cost of all away-moves are

$\displaystyle\sum_{l=1}^{k}\left(m-\left\lceil\frac{m-1-l}{k}\right\rceil-2\right)d_{2}-d_{2}$
$\displaystyle\leq\sum_{l=1}^{k}\left(m-\left\lceil\frac{m-1-l}{k}\right\rceil-2\right)d_{2}$
$\displaystyle=(l_{0}-1)\left(m-\frac{m-1-l_{0}}{k}-3\right)d_{2}+(k-l_{0}+1)\left(m-\frac{m-1-l_{0}}{k}-2\right)d_{2}$
$\displaystyle=(k-1)(m-2)d_{2},$

where $l_{0}$ in the second equality is the number satisfying
$(m-l_{0}-1)\bmod k=0$ and $l_{0}\in\\{1,2,\dots,k\\}$.

Then, we consider home-moves. Consider an arbitrary block
$(e_{i},\dots,e_{j})$, where we call the edges $e_{i}$ and $e_{j}$ _boundary
edges_. Note that the boundary edges may be the same. After Assumption 14, we
have that there are two home-moves corresponding to the _boundary edges_. For
example, in Figure 1, we consider the $1$-st block $(e_{1})$ from the $1$-st
day to the $2$-nd day. We can see that $t_{20}$ takes a home-move from the
venues of $t_{10}$ to $t_{20}$ on the $1$-st day and a home-move from the
venues of $t_{20}$ to $t_{1}$ on the $2$-nd day. Both home-moves correspond to
the same boundary edge $e_{1}$. Note that for the special case with $w_{2}=k$,
we imagine that the $2$-nd block $(e_{2},e_{3},\dots,e_{k+1})$ is further
divided into two blocks $(e_{2})$ and $(e_{3},\dots,e_{k+1})$, and then we
will have two more home-moves corresponding to the edges $e_{2}$ and $e_{3}$,
respectively. For all $k$ cases of $l\in\\{1,2,\dots,k\\}$, there must be two
cases such that the edge $e_{i}$ ($3\leq i\leq m-1$) is a boundary edge in
some block, one case such that the edge $e_{2}$ (resp., $e_{m}$) is the only
boundary edge in the $2$-nd block (resp., the last block). Hence, for all
these $k$ cases, the total expected cost of all home-moves are

$\displaystyle
2kd_{1}+(k+1)d_{2}+2\sum_{i=3}^{m-1}d_{i}+(k+1)d_{m}+(d_{2}+d_{3})$
$\displaystyle=2kd_{1}+kd_{2}+kd_{m}+2\sum_{i=1}^{m}d_{i}+d_{3}-2d_{1}-d_{m}$
$\displaystyle\leq 4kd_{1}+kd_{2}+2\sum_{i=1}^{m}d_{i}$
$\displaystyle=4kd_{1}+kd_{2}+\frac{\Delta}{n-1},$

where the inequality follows from $d_{m}\leq 2d_{1}$ and $d_{3}\leq 2d_{1}$ by
Lemma 10, and the last equality follows from Lemma 9.

For all $k$ cases of $l\in\\{1,2,\dots,k\\}$, there must be one case such that
the total expected cost of all moves is bounded by

$\displaystyle 4d_{1}+d_{2}+\frac{\Delta}{k(n-1)}+\frac{(k-1)(m-2)d_{2}}{k}.$
(2)

Case 2: $k\geq n/2$. There are only two blocks: $(e_{1})$ and
$(e_{2},\dots,e_{m})$. There are $m-2$ away-moves with an expected cost of
$(m-2)d_{2}$, and four home-moves with an expected cost of
$2d_{1}+d_{2}+d_{m}$. Therefore, the total expected cost of all moves is

$\displaystyle 2d_{1}+d_{2}+d_{m}+(m-2)d_{2}=2d_{1}+(m-1)d_{2}+d_{m}\leq
4d_{1}+(m-1)d_{2},$ (3)

where the inequality follows from $d_{m}\leq 2d_{1}$ by Lemma 10.

From the $(n-1)$-th day to the home day. Since there are $m$ games on the
$(n-1)$-th day and all teams are at home on the home day, we know that there
are $m$ home-moves corresponding to the edges $e_{1},\dots,e_{m}$,
respectively. The total expected cost of all moves is

$\displaystyle\sum_{i=1}^{m}d_{i}=\frac{\Delta}{2(n-1)},$ (4)

where it follows from Lemma 9.

We can analyze the total expected cost of all moves in the first season.

Case 1: $k\leq n/2$. For the best choice of $l$, by (1), (2), and (4), the
expected cost of moves in the first season is

$\displaystyle\frac{\Delta}{2(n-1)}+(n-2)\left(4d_{1}+d_{2}+\frac{\Delta}{k(n-1)}+\frac{(k-1)(m-2)d_{2}}{k}\right)+\frac{\Delta}{2(n-1)}$
$\displaystyle\leq\frac{\Delta}{n-1}+4(n-2)d_{1}+(n-1)d_{2}+(1/k)\Delta+(1-1/k)(m-2)(n-1)d_{2}$
$\displaystyle\leq\frac{\Delta}{n-1}+\frac{4(n-2)\Delta}{n(n-1)}+d(T^{\prime})+(1/k)\Delta+(1-1/k)(m-2)d(T^{\prime})$
$\displaystyle=\frac{(5n-8)\Delta}{n(n-1)}+d(T^{\prime})+(1/k)\Delta+(1-1/k)(m-2)d(T^{\prime})$
$\displaystyle\leq(5/n)\Delta+(1/k)\Delta+(1-1/k)md(T),$

where the second inequality follows from $d_{1}\leq\frac{\Delta}{n(n-1)}$ and
$d_{2}=\frac{d(T^{\prime})}{n-1}$ by Lemmas 11 and 12, and the last inequality
follows from $d(T^{\prime})\leq 2(1-1/k)d(T^{\prime})$ and $d(T^{\prime})\leq
d(T)$ by the triangle inequality.

Case 2: $k\geq n/2$. For the best choice of $l$, by (1), (3), and (4), the
expected cost of moves in the first season is

$\displaystyle\frac{\Delta}{2(n-1)}+(n-2)\left(4d_{1}+(m-1)d_{2}\right)+\frac{\Delta}{2(n-1)}$
$\displaystyle\leq\frac{\Delta}{n-1}+4(n-2)d_{1}+(n-1)(m-1)d_{2}$
$\displaystyle\leq\frac{\Delta}{n-1}+\frac{4(n-2)\Delta}{n(n-1)}+(m-1)d(T^{\prime})$
$\displaystyle=\frac{(5n-8)\Delta}{n(n-1)}+(1-1/m)md(T^{\prime})$
$\displaystyle\leq(5/n)\Delta+(1-1/k)md(T),$

where the second inequality follows from $d_{1}\leq\frac{\Delta}{n(n-1)}$ and
$d_{2}=\frac{d(T^{\prime})}{n-1}$ by Lemmas 11 and 12, and the last inequality
follows from $m=n/2\leq k$ and $d(T^{\prime})\leq d(T)$ by the triangle
inequality.

Note that based on Assumptions 13 and 14, we can easily get that the total
expected cost of all moves in the second season is the same as that in the
first season. So, the total expected cost is at most
$(10/n)\Delta+(2/k)\Delta+(1-1/k)nd(T)$ for $k<n/2$ and
$(10/n)\Delta+(1-1/k)nd(T)$ for $k\geq n/2$.

Since we label the vertices on $T^{\prime}$ uniformly at random from the $n-1$
cases, to derandomize the algorithm, we can simply enumerate all these cases
and choose the best one. Consider the running time. In each case, there are
$k$ choices of $l$ for $k<n/2$ and one choice of $l$ for $k\geq n/2$.
Moreover, for each fixed $l$, the construction takes $O(n^{2})$ time. Hence,
the running time of the deterministic algorithm is $O(n^{3}k)$ for $k<n/2$ and
$O(n^{3})$ for $n\geq k/2$. We can get the following theorem.

######  Theorem 15.

For TTP-$k$ with $k\geq 2$, there is a polynomial-time algorithm that can
generate a solution with a weight of at most
$(10/n)\Delta+(2/k)\Delta+(1-1/k)nd(T)$, where $T$ is a given Hamiltonian
cycle of graph $G$. If $k\geq n/2$, the upper bound can be improved to
$(10/n)\Delta+(1-1/k)nd(T)$.

Note that Yamaguchi _et al._ [30] proposed an algorithm that can generate a
solution with a weight of at most $O(1/n)\Delta+(2/k)\Delta+(1-1/k)nd(T)$ for
TTP-$k$ with $k\geq 3$. Theorem 15 implies that the construction in this paper
has a better upper bound than that in [30]. Their algorithm is more
complicated, and it is not even easy to compute an upper bound
$(c/n)\Delta+(2/k)\Delta+(1-1/k)d(T)$ with some small constant $c$. Since we
have $\Delta=O(k)\cdot\mbox{OPT}$ by Lemma 4, their result only implies an
$O(1)$-approximation for TTP-$k$ with $k=\Theta(n)$. It is worth noting that
their schedule satisfies an additional mirrored constraint, i.e., the second
season is directly arranged by reversing the home venues in the first season.
Therefore, we suspect that the constant $c$ in their algorithm is much larger
than $10$, even by a tighter analysis.

###  3.3 The Approximation Ratio

Recall that the construction is based on a given Hamiltonian cycle $T$ of
graph $G$. We simply use the well-known $3/2$-approximation algorithm, which
takes $O(n^{3})$ time. Then, we have the following lemma.

######  Lemma 16 ([7, 24]).

$d(T)\leq(3/2)d(T^{*})$.

######  Theorem 17.

For TTP-$k$ with $k\geq 2$, there is a polynomial-time $5$-approximation
algorithm. If $k\geq n/2$, the approximation ratio can be improved to $4$.

###### Proof.

First, we consider $k<n/2$. By Theorem 15, the weight is bounded by
$(10/n)\Delta+(2/k)\Delta+(1-1/k)d(T)$. We can get that

$\displaystyle(10/n)\Delta+(2/k)\Delta+(1-1/k)nd(T)$
$\displaystyle\leq(10/n)\Delta+(2/k)\Delta+(3/2)(1-1/k)nd(T^{*})$
$\displaystyle\leq(5k/n)\cdot\mbox{OPT}+\mbox{OPT}+(3/2)(1-1/k)\cdot\mbox{OPT}$
$\displaystyle\leq(5/2)\cdot\mbox{OPT}+\mbox{OPT}+(3/2)\cdot\mbox{OPT}$
$\displaystyle=5\cdot\mbox{OPT},$

where the first inequality follows from $d(T)\leq(3/2)d(T^{*})$ by Lemma 16,
the second inequality follows from $nd(T^{*})\leq\mbox{OPT}$ and
$\Delta\leq(k/2)\cdot\mbox{OPT}$ by Lemmas 3 and 4, and the last inequality
follows from $k<n/2$.

Then, we consider $k\geq n/2$. By Theorem 15, the weight is bounded by

$\displaystyle(10/n)\Delta+(1-1/k)nd(T)$
$\displaystyle\leq(10/n)\Delta+(3/2)nd(T^{*})$
$\displaystyle\leq(5/2)\cdot\mbox{OPT}+(3/2)\cdot\mbox{OPT}$
$\displaystyle=4\cdot\mbox{OPT},$

where the first inequality follows from $d(T)\leq(3/2)d(T^{*})$ by Lemma 16,
and the second inequality follows from $nd(T^{*})\leq\mbox{OPT}$ and
$\Delta\leq(n/4)\cdot\mbox{OPT}$ by Lemmas 3 and 5. ∎

##  4 Conclusion

In this paper, we present a 5-approximation algorithm for TTP-$k$, which not
only addresses previous flaws but also significantly improves previous
results. In our algorithm, we simply use the simple 3/2-approximation
algorithm for TSP. Recently, the TSP ratio was slightly improved to
$3/2-\varepsilon$, where the improvement $\varepsilon$ is about $10^{-36}$
[20]. By utilizing the improved approximation algorithm for TSP, we may also
be able to slightly improve the result. For the case $k=n-1$, our ratio is
worse than the current-best ratio $2.75$ in [19]. It would be interesting to
know whether our technique in this paper can also be used to improve the ratio
for the case $k=n-1$.

## 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] Aris Anagnostopoulos, Laurent Michel, Pascal Van Hentenryck, and Yannis Vergados.  A simulated annealing approach to the traveling tournament problem.  Journal of Scheduling, 9(2):177–193, 2006.
  * [2] Salomon Bendayan, Joseph Cheriyan, and Kevin K. H. Cheung.  Unconstrained traveling tournament problem is apx-complete.  CoRR, abs/2212.09165, 2022.
  * [3] Rishiraj Bhattacharyya.  Complexity of the unconstrained traveling tournament problem.  Operations Research Letters, 44(5):649–654, 2016.
  * [4] 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.
  * [5] Diptendu Chatterjee.  Complexity of traveling tournament problem with trip length more than three.  CoRR, abs/2110.02300, 2021.
  * [6] 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.
  * [7] Nicos Christofides.  Worst-case analysis of a new heuristic for the travelling salesman problem.  Technical report, Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group, 1976.
  * [8] Dominique de Werra.  Some models of graphs for scheduling sports competitions.  Discrete Applied Mathematics, 21(1):47–65, 1988.
  * [9] Luca Di Gaspero and Andrea Schaerf.  A composite-neighborhood tabu search approach to the traveling tournament problem.  Journal of Heuristics, 13(2):189–207, 2007.
  * [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] Kelly Easton, George Nemhauser, and Michael Trick.  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, pages 100–109, 2003.
  * [13] Marc Goerigk, Richard Hoshino, Ken-ichi Kawarabayashi, and Stephan Westphal.  Solving the traveling tournament problem by packing three-vertex paths.  In Twenty-Eighth AAAI Conference on Artificial Intelligence, pages 2271–2277, 2014.
  * [14] Marc Goerigk and Stephan Westphal.  A combined local search and integer programming approach to the traveling tournament problem.  Ann. Oper. Res., 239(1):343–354, 2016.
  * [15] Marc Goerigk and Stephan Westphal.  A combined local search and integer programming approach to the traveling tournament problem.  Annals of Operations Research, 239(1):343–354, 2016.
  * [16] 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.
  * [17] Richard Hoshino and Ken-ichi Kawarabayashi.  An approximation algorithm for the bipartite traveling tournament problem.  Mathematics of Operations Research, 38(4):720–728, 2013.
  * [18] Shinji Imahori.  A 1+O(1/N) approximation algorithm for TTP(2).  CoRR, abs/2108.08444, 2021.
  * [19] 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.
  * [20] Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan.  A (slightly) improved approximation algorithm for metric TSP.  In STOC 2021, pages 32–45, 2021.
  * [21] 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.
  * [22] Andrew Lim, Brian Rodrigues, and Xingwen Zhang.  A simulated annealing and hill-climbing algorithm for the traveling tournament problem.  European Journal of Operational Research, 174(3):1459–1478, 2006\.
  * [23] Ryuhei Miyashiro, Tomomi Matsui, and Shinji Imahori.  An approximation algorithm for the traveling tournament problem.  Annals of Operations Research, 194(1):317–324, 2012.
  * [24] Anatolii Ivanovich Serdyukov.  Some extremal bypasses in graphs.  Upravlyaemye Sistemy, 17:76–79, 1978.
  * [25] Clemens Thielen and Stephan Westphal.  Complexity of the traveling tournament problem.  Theoretical Computer Science, 412(4):345–351, 2011.
  * [26] Clemens Thielen and Stephan Westphal.  Approximation algorithms for TTP(2).  Mathematical Methods of Operations Research, 76(1):1–20, 2012.
  * [27] Michael Trick.  Challenge traveling tournament instances.  Accessed: 2022-4-01, 2022.
  * [28] Stephan Westphal and Karl Noparlik.  A 5.875-approximation for the traveling tournament problem.  Annals of Operations Research, 218(1):347–360, 2014.
  * [29] 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.
  * [30] Daisuke Yamaguchi, Shinji Imahori, Ryuhei Miyashiro, and Tomomi Matsui.  An improved approximation algorithm for the traveling tournament problem.  Algorithmica, 61(4):1077–1091, 2011.
  * [31] 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.
  * [32] 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.
  * [33] Jingyang Zhao and Mingyu Xiao.  Practical algorithms with guaranteed approximation ratio for TTP with maximum tour length two.  CoRR, abs/2212.12240, 2022.
  * [34] 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\.

##  Appendix A The Flaw in the Previous Construction Algorithm

Westphal and Noparlik’s construction [28] only makes sure that the direction
of the most left edge (incident on team $t_{n}$) changes every $k$-th day in
the first season. Note that in our construction we deal with one more case: if
$r\leq k<n-1$ we further reverse the most left edge on the 1-st day.

We show that team $t_{n}$ may play more than $k$-consecutive home/away games
in Westphal and Noparlik’s construction, thus leading to an infeasible
schedule for TTP-$k$.

######  Lemma 18.

In Westphal and Noparlik’s construction, team $t_{n}$ plays more than
$k$-consecutive home games if and only if $r\leq k<n-1$.

###### Proof.

By a similar argument in the proof of Lemma 1, we consider the following two
cases. Note that the direction of the most left edge changes every $k$-th day.

Case 1: $r>k$. The home/away pattern of team $t_{n}$ in the first season is
$A^{k}H^{k}\cdots A^{k}H^{k}A^{k}H^{r-k}$. In the second season, if $r-k=1$,
the pattern is $HAH^{k}A^{k}\cdots H^{k}A^{k}H^{k-1}$; otherwise, the pattern
is $A^{2}H^{k}A^{k}\cdots H^{k}A^{k}H^{k}A^{r-k-2}$. In both cases, the
patterns in these two seasons can be combined well without creating more than
$k$-consecutive home/away games.

Case 2: $r\leq k$. Similarly, we have $n-1>2k$. The home/away pattern of team
$t_{n}$ in the first season is $A^{k}H^{k}\cdots A^{k}H^{k}A^{r}$. In the
second season, if $r=1$, the pattern is $AHH^{k}A^{k}\cdots H^{k}A^{k-1}$;
otherwise, the pattern is $H^{2}H^{k}A^{k}\cdots H^{k}A^{k}H^{r-2}$. In both
cases, the pattern in the second season can create more than $k$-consecutive
home games. ∎

Lemma 18 shows that when $r\leq k<n-1$, the construction in [28] is
infeasible. Note that if $k=O(1)$, the construction is infeasible for at least
half of the instances. Their construction was also considered for $k=2$ in
[26], where there are two cases: even $n/2$ and odd $n/2$. But, it fails for
the case of odd $n/2$ with the same reason. Some experimental algorithms [26,
28, 15] take the output of their constructions as an initial solution, and
then optimize it using some heuristic methods. However, we are unaware whether
the experimental results are correct due to this flaw.

##  Appendix B The Flaw in the Previous Analysis

Westphal and Noparlik proved an approximation ratio of
$2+2k/n+k/(n-1)+3/n+3/(2\cdot k)$ [28]. For any constant $k>10$, the
approximation ratio achieves $2+3/(2\cdot k)+O(1/n)$, which is even better
than the approximation ratio $(5k-7)/(2k)+O(1/n)$ in [30]. Note that the
latter approximation ratio is obtained using some stronger lower bounds than
the former one. Indeed, there is a flaw in Westphal and Noparlik’s analysis.
In their analysis, the cost of the schedule was divided into several parts
(note that our analysis is based on a different framework).

######  Lemma 19 ([28]).

Given a Hamiltonian cycle $T$ of graph $G$, the cost of the schedule is
bounded by $C_{h}+C_{a}+C_{s}+C_{l}+C_{r}+C_{o}$, where

  * •

$C_{h}\leq(2/n)\Delta$;

  * •

$C_{a}\leq(2/n)\Delta$;

  * •

$C_{s}\leq\frac{2(\Delta-2s(n))}{n-1}$;

  * •

$C_{l}\leq 2d(T)$;

  * •

$C_{r}=2\cdot\left(\sum_{i=1}^{n/2}d(i,i+n/2-1)+\sum_{i=n/2+1}^{n}d(i,i-n/2)\right)$;

  * •

$C_{o}\leq\frac{2\Delta+(n-2)d(T)}{k}$.

To see the flaw, we give a counterexample. We consider TTP-$k$ with
$k=\Theta(n)$ and the complete graph $G$ where the length of each edge is a
unit. We can get $s(n)=n-1$ and $\Delta=n(n-1)$. Note that the length of any
Hamiltonian cycle of graph $G$ is $n$. Hence, we have $d(T)=n$. Therefore, by
Lemma 19, we have

$\displaystyle C_{h}+C_{a}+C_{s}+C_{l}+C_{r}+C_{o}$
$\displaystyle\leq(2/n)\Delta+(2/n)\Delta+\frac{2(\Delta-2s(n))}{n-1}+2d(T)$
$\displaystyle\quad\
+2\cdot\left(\sum_{i=1}^{n/2}d(i,i+n/2-1)+\sum_{i=n/2+1}^{n}d(i,i-n/2)\right)+\frac{2\Delta+(n-2)d(T)}{k}$
$\displaystyle=2(n-1)+2(n-1)+2(n-2)+2n+2n+\frac{2n(n-1)+n(n-2)}{k}$
$\displaystyle=\Theta(n).$

For this example, the analyzed cost of the schedule is bounded by $\Theta(n)$.
However, it is easy to see that in an optimal schedule, the traveling distance
of each team is $\Theta(n)$, and then the total traveling distance of all
teams is $\Theta(n^{2})$, a contradiction.

The flaw is due to the analysis of the cost $C_{o}$ and the cost of this part
is also the main cost of the schedule. Note that a simple refined analysis may
lead us to get

$C_{o}\leq(2/k)\Delta+(n-2)d(T),$

with an approximation ratio $7/2+2k/n+k/(n-1)+3/n$ instead of
$2+2k/n+k/(n-1)+3/n+3/(2\cdot k)$, i.e., the term $3/(2\cdot k)$ in their
claimed approximation ratio should be $3/2$. When $k=\Theta(n)$, the
approximation ratio is bounded by $6.5+O(1/n)$ instead of the claimed
$5+O(1/n)$. For any $n>k\geq 4$ and $n\geq 6$, the approximation ratio is
bounded by $6.667$ instead of the claimed $5.875$.