such a character would have to satisfy $k_{\tau_{2}}=0$ and
$k_{\tau_{1}},k_{\tau_{4}},k_{\tau_{5}},k_{\tau_{6}}\in\\{\pm 1\\}$. However,
there exists an $\mathcal{H}^{\bullet}$-shady character, namely
$\Psi_{\mathrm{shady}}=\Psi_{1}$. Moreover, $\Psi_{\mathrm{shady}}^{\pm 1}$
are the only $\mathcal{H}^{\bullet}$-shady characters of $L$, so that the
$1$st Betti numbers of $Y_{1}$ and $Y_{c}$ differ by $1$. In fact, we can
independently compute the homology and see that we have

$H_{1}(P\Gamma_{1},\mathbb{Z})\cong(\mathbb{Z}/2\mathbb{Z})^{4}\quad\text{ and
}\quad
H_{1}(P\Gamma_{c},\mathbb{Z})\cong(\mathbb{Z}/2\mathbb{Z})^{3}\oplus\mathbb{Z}.$

The maximal cyclic subgroups of $P\Gamma_{1}$ have order $2$ or $6$, and the
maximal cyclic subgroups of $P\Gamma_{c}$ have order $2$ or $3$.

The eigenvalues of the Hecke operators acting on
$H_{1}(\mathcal{Y},\mathbb{Q})=\mathbb{Q}$ are rational, so one expects them
to correspond to an elliptic curve $E$ over $F$. In this case, since this
cohomology class comes from a Hecke character, CM theory implies that this
elliptic curve exists, and one can find it explicitly:

$E:y^{2}+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6},$

where

$\displaystyle a_{2}$ $\displaystyle=$
$\displaystyle\alpha^{5}-\alpha^{4}-3\alpha^{3}+\alpha^{2}+3\alpha+2,$
$\displaystyle a_{3}$ $\displaystyle=$
$\displaystyle\alpha^{5}-\alpha^{4}-3\alpha^{3}+\alpha^{2}+\alpha+2,$
$\displaystyle a_{4}$ $\displaystyle=$ $\displaystyle\alpha^{3}-2\alpha,$
$\displaystyle a_{6}$ $\displaystyle=$ $\displaystyle
12159\alpha^{5}-15642\alpha^{4}-31998\alpha^{3}+9172\alpha^{2}+21688\alpha+42423.$

In other words, the fact that the elliptic curve $y^{2}+y=x^{3}$ with
$j$-invariant $0$, after base-change to $F$ and a sextic twist, acquires
everywhere good reduction, is an algebraic explanation for the fact that
$Y_{1}$ and $Y_{c}$ are not $1$-isospectral!

Figure 3. Isospectral $3$-orbifolds with distinct Betti numbers (volume
$\approx 3.397$)

The following example proves Theorem E. It is an example of non-isospectral
$3$-orbifolds forming a Vignéras pair with no $\mathcal{H}^{*}$-shady
character and non-zero $1$st Betti numbers; in particular their regulator
ratio is rational for a non-trivial reason.

######  Example 7.8.

Let $F=\mathbb{Q}(\alpha)$ where
$\alpha^{4}-2\alpha^{3}+7\alpha^{2}-6\alpha-3=0$. The field $F$ is a number
field of discriminant $-10224$ and signature $(2,1)$ (LMFDB 4.2.10224.2). Let
$D$ be the unique quaternion division algebra ramified at every real place and
no finite place of $F$. Let $\mathfrak{N}=(1)$. We have $C\cong
C_{\operatorname{iso}}\cong C_{2}$, which therefore has a single non-trivial
character $\chi$, corresponding to the quadratic extension $L=F(\zeta_{12})$.
Let $\sigma$ be the non-trivial automorphism of $L/F$.

Let $C=\\{1,c\\}$. We have

$\operatorname{vol}(Y_{1})=\operatorname{vol}(Y_{c})=\frac{10224^{3/2}\zeta_{F}(2)}{2^{8}\pi^{6}}=5.902455\dots.$

Take representatives $(\tau_{k})_{k}$ of $\operatorname{Hom}(L,\mathbb{C})$
modulo complex conjugation such that

$\displaystyle(\tau_{k}(\zeta_{12}))_{k}$ $\displaystyle=$
$\displaystyle(e^{-5\frac{2\pi}{12}i},e^{-5\frac{2\pi}{12}i},e^{\frac{2\pi}{12}i},e^{-\frac{2\pi}{12}i}),$
$\displaystyle(\tau_{k}(\alpha))_{k}$ $\displaystyle\approx$
$\displaystyle(1.345,-0.345,0.500-2.493i,0.500-2.493i).$

We compute the group $\operatorname{\mathbf{HC}}_{L,(1)}$ of unitary Hecke
characters. It is isomorphic to $\mathbb{Z}^{7}\times\mathbb{R}$. Let
$\Psi_{1},\dots,\Psi_{7}$ denote the computed basis of the canonical
complement of $\|\cdot\|^{i\mathbb{R}}$. We display the $\Psi_{j}$ as above.

| $\Psi_{1}$ | $\Psi_{2}$ | $\Psi_{3}$ | $\Psi_{4}$ | $\Psi_{5}$ | $\Psi_{6}$ | $\Psi_{7}$
---|---|---|---|---|---|---|---
$\tau_{1}$ | $(1,0)$ | $(3,0)$ | $(-2,0)$ | $(-2,0.714)$ | $(-3,-0.140)$ | $(0,-0.140)$ | $(0,0.953)$
$\tau_{2}$ | $(1,0)$ | $(3,0)$ | $(-2,0)$ | $(-2,-0.714)$ | $(-4,0.140)$ | $(1,0.140)$ | $(0,0.239)$
$\tau_{3}$ | $(-19,0)$ | $(-33,0)$ | $(26,-0.480)$ | $(26,0)$ | $(43,-0.215)$ | $(-9,0.215)$ | $(-6,-0.356)$
$\tau_{4}$ | $(19,0)$ | $(33,0)$ | $(-26,0.480)$ | $(-26,0)$ | $(-42,0.215)$ | $(10,-0.215)$ | $(6,-0.836)$

We then compute the subgroup $\operatorname{\mathbf{HC}}_{L,(1)}^{-}$ of
unitary Hecke characters $\Psi$ such that $\Psi^{\sigma}\Psi$ has finite
order. It admits a basis $\Psi_{1}^{\prime},\dots,\Psi_{4}^{\prime}$, where

$\Psi_{1}^{\prime}=\Psi_{1},\quad\Psi_{2}^{\prime}=\Psi_{2},\quad\Psi_{3}^{\prime}=\Psi_{3},\quad\Psi_{4}^{\prime}=\Psi_{5}^{-1}\Psi_{6}.$

We display the $\Psi_{j}^{\prime}$ as above.

| $\Psi_{1}^{\prime}$ | $\Psi_{2}^{\prime}$ | $\Psi_{3}^{\prime}$ | $\Psi_{4}^{\prime}$
---|---|---|---|---
$\tau_{1}$ | $(1,0)$ | $(3,0)$ | $(-2,0)$ | $(3,0)$
$\tau_{2}$ | $(1,0)$ | $(3,0)$ | $(-2,0)$ | $(5,0)$
$\tau_{3}$ | $(-19,0)$ | $(-33,0)$ | $(26,-0.480)$ | $(-52,0.430)$
$\tau_{4}$ | $(19,0)$ | $(33,0)$ | $(-26,0.480)$ | $(52,-0.430)$

Projecting on the values $(k_{\tau_{1}},k_{\tau_{2}},k_{\tau_{3}})$, we obtain
a lattice generated by the columns of a matrix, say $B$, and with LLL-reduced
basis with matrix $B^{\prime}$, where

$B=\begin{pmatrix}1&3&-2&3\\\ 1&3&-2&5\\\
-19&-33&26&-52\end{pmatrix},\quad\quad B^{\prime}=\begin{pmatrix}-1&-2&1\\\
1&-2&1\\\ 0&2&5\end{pmatrix}.$

From this it is clear that there is no $\mathcal{H}^{\bullet}$-shady character
of $L$, as such a character would have to satisfy $k_{\tau}\in\\{\pm 1\\}$ for
all $\tau\in\operatorname{Hom}(L,\mathbb{C})$. However, there exists an
$\Omega^{\bullet}$-shady character of $L$, namely
$\Psi_{\mathrm{shady}}=(\Psi_{1}^{\prime})^{-1}(\Psi_{2}^{\prime})^{-1}\Psi_{4}^{\prime}$,
and the set of $\Omega^{\bullet}$-shady characters is
$\Psi_{\mathrm{shady}}^{\pm 1}\Psi_{0}^{\mathbb{Z}}$, where
$\Psi_{0}=(\Psi_{1}^{\prime})^{-1}(\Psi_{2}^{\prime})^{-1}(\Psi_{3}^{\prime})^{-2}$:

| $\Psi_{\mathrm{shady}}$ | $\Psi_{0}$
---|---|---
$\tau_{1}$ | $(-1,0)$ | $(0,0)$
$\tau_{2}$ | $(1,0)$ | $(0,0)$
$\tau_{3}$ | $(0,0.430)$ | $(0,0.960)$
$\tau_{4}$ | $(0,-0.430)$ | $(0,-0.960)$

For all $n\in\mathbb{Z}$, the character $\Psi_{\mathrm{shady}}\Psi_{0}^{n}$
contributes an eigenvalue $\lambda(n)\approx 1+4(0.430+0.960n)^{2}$ to the
Laplace spectrum of $\Omega^{1}(\mathcal{Y})$ by Proposition 5.25. The first
few corresponding eigenvalues are

$1.741\dots,\quad 2.123\dots,\quad 8.735\dots,\quad 9.883\dots,\quad
23.107\dots,\quad 25.020\dots.$

Only $\Psi_{\mathrm{shady}}^{\pm 1}$ contribute to the eigenvalue
$\lambda(0)$, so by Lemma 7.2, the orbifolds $Y_{1}$ and $Y_{c}$ are not
$1$-isospectral. Since these characters are also $\Omega^{0}$-shady, by the
same argument these orbifolds are also not $0$-isospectral.

Since there is no $\mathcal{H}^{\bullet}$-shady character of $L$, by Theorem
5.34, we have

$\frac{\operatorname{Reg}_{1}(Y_{1})^{2}}{\operatorname{Reg}_{1}(Y_{c})^{2}}\in\mathbb{Q}^{\times},$

and the Betti numbers of $Y_{1}$ and $Y_{c}$ are equal. In fact, we have

$H_{1}(P\Gamma_{1},\mathbb{Z})\cong(\mathbb{Z}/2\mathbb{Z})^{2}\oplus\mathbb{Z}\quad\text{
and }\quad
H_{1}(P\Gamma_{c},\mathbb{Z})\cong(\mathbb{Z}/2\mathbb{Z})^{2}\oplus\mathbb{Z},$

and in particular both $1$st Betti numbers are $1$, so the rationality of the
ratio of regulators is a non-trivial statement. Moreover, since the orbifolds
are not isospectral, the Cheeger–Müller theorem does not say anything about
this rationality.

The maximal cyclic subgroups of $P\Gamma_{1}$ have order $2$, $3$, $4$ or
$12$, and the maximal cyclic subgroups of $P\Gamma_{c}$ have order $2$ or $3$.

Figure 4. Non-isospectral $3$-orbifolds with Betti number $1$ and rational
regulator square quotient (volume $\approx 5.902$)

## References

  * [1] C. C. Adams, Limit volumes of hyperbolic three-orbifolds, J. Differ. Geom. 34 no. 1 (1991), 115–141.
  * [2] A. Ash, Galois representations attached to mod $p$ cohomology of $\operatorname{GL}(n,\mathbb{Z})$, Duke Math. J. 65 no. 2 (1992), 235–255.
  * [3] A. I. Badulescu, Global Jacquet–Langlands correspondence, multiplicity one and classification of automorphic representations, Invent. Math. 172 (2007), 383–438.
  * [4] A. Bartel and A. Page, Torsion homology and regulators of isospectral manifolds, J. Topology 9 no. 4 (2016), 1237–1256.
  * [5] A. Bartel and A. Page, Group representations in the homology of 3-manifolds, Comment. Math. Helv. 94 no. 1 (2019), 67–88.
  * [6] N. Bergeron and A. Venkatesh, The asymptotic growth of torsion homology for arithmetic groups, J. Inst. Math. Jussieu 12 no. 2 (2013), 391–447.
  * [7] N. Bergeron, M. H. Şengün and A. Venkatesh, Torsion homology growth and cycle complexity of arithmetic manifolds, Duke Math. J. 165 no. 9 (2016), 1629–1693.
  * [8] N. Bergeron and L. Clozel, Spectre automorphe des variétés hyperboliques et applications topologiques, Astérisque 303 (2005).
  * [9] A. Borel and N. Wallach, Continuous cohomology, discrete subgroups, and representations of reductive groups, 2nd edition, Mathematical Surveys and Monographs 67, American Mathematical Society, Providence, RI, 2000.
  * [10] D. Bump, Automorphic Forms and Representations, Cambridge Studies in Advanced Mathematics 55, Cambridge University Press, Cambridge, 1997.
  * [11] C. J. Bushnell and G. Henniart, The Local Langlands Conjecture for $\operatorname{GL}(2)$, Grundlehren der mathematischen Wissenschaften 335, Springer–Verlag Berlin Heildelberg, 2006.
  * [12] J. F. Brock and N. M. Dunfield, Injectivity radii of hyperbolic integer homology $3$-spheres, Geom. Topol. 19 no. 1 (2015), 497–523.
  * [13] F. Calegari and D. Geraghty, Modularity lifting beyond the Taylor–Wiles method, Invent. Math. 211 (2018), 297–433.
  * [14] F. Calegari and A. Venkatesh, A torsion Jacquet–Langlands correspondence, Asterisque 409 (2019).
  * [15] A. Caraiani and J. Newton, On the modularity of elliptic curves over imaginary quadratic fields, preprint, arXiv:2301.10509 [math.NT] (2023).
  * [16] F. C. Caramello Jr., Introduction to Orbifolds, preprint, arXiv:1909.08699v6 [math.DG] (2022).
  * [17] W. Casselman, On Some Results of Atkin and Lehner, Math. Ann. 201 (1973), 301–314.
  * [18] J. Cheeger, Analytic torsion and the heat equation, Ann. of Math. 109 (1979), 259–322.
  * [19] H. Cohen, Advanced Topics in Computational Number Theory, Graduate Texts in Mathematics 193, Springer–Verlag New York, 2000.
  * [20] D. DeTurck and C. S. Gordon, Isospectral deformations II: trace formulas, metrics, and potentials, with an appendix by K. B. Lee, Comm. Pure Appl. Math. 42 no. 8 (1989), 1067–1095.
  * [21] T. Dokchitser and V. Dokchitser, Regulator constants and the parity conjecture, Invent. Math. 178 no. 1 (2009), 23–71.
  * [22] P. G. Doyle and J. P. Rossetti, Laplace-isospectral hyperbolic $2$-orbifolds are representation-equivalent, preprint, arXiv:1103.4372v2 [math.DG] (2014).
  * [23] D. Eisenbud, Commutative algebra with a view toward algebraic geometry, Graduate Texts in Mathematics 150, Springer-Verlag, New York, 1995.
  * [24] P. X. Gallagher, Determinants of representations of finite groups, Abh. Math. Semin. Univ. Hambg. 28 (1965), 162–167.
  * [25] I. M. Gel’fand and I. I. Pyatetski-Shapiro, Automorphic functions and the theory of representations. (Russian), Trudy Moskov. Mat. Obšč. 12 (1963), 389–412.
  * [26] P. Gérardin and J.-P. Labesse, The solution of a base change problem for ${\operatorname{GL}}(2)$ (following Langlands, Saito, Shintani), in: Automorphic forms, representations and $L$-functions (Proc. Sympos. Pure Math., Oregon State Univ., Corvallis, Ore., 1977), Part 2, Proc. Sympos. Pure Math. XXXIII, Amer. Math. Soc., Providence, RI, 1979, pp. 115–133.
  * [27] J. R. Getz and H Hahn, An Introduction to Automorphic Representations with a view toward trace formulae, Graduate Texts in Mathematics 300, Springer, Cham, 2024.
  * [28] R. Godement, The spectral decomposition of cusp forms, Proc. Sympos. Pure Math. 9, Amer. Math. Soc., Providence, R. I., 1966, 225–234.
  * [29] C. S. Gordon, Riemannian manifolds isospectral on functions but not on $1$-forms, J. Differential Geometry 24 (1986), 79–96.
  * [30] C. S. Gordon, Survey of isospectral manifolds. Handbook of differential geometry, Vol. I (2000), 747–778.
  * [31] C. S. Gordon, Orbifolds and their spectra, in: Spectral Geometry, Proceedings of Symposia in Pure Mathematics 84 A. H. Barnett, C. S. Gordon, P. A. Perry and A. Uribe (eds.), 2012, pp. 49–71.
  * [32] G. Harder, Eisenstein cohomology of arithmetic groups. The case $\operatorname{GL}_{2}$, Invent. Math. 89 (1987), 37–118.
  * [33] H. Jacquet and R. P. Langlands, Automorphic Forms on $\operatorname{GL}(2)$, Lecture Notes in Mathematics 114, Springer-Verlag, Berlin, 1970.
  * [34] M. Kac, Can one hear the shape of a drum? Amer. Math. Monthly 73 (1966), 1–23.
  * [35] D. Kelmer, A refinement of strong multiplicity one for spectra of hyperbolic manifolds, Trans. Amer. Math. Soc. 366 no. 11 (2014), 5925–5961.
  * [36] J. Labesse and R. P. Langlands, L-Indistinguishability For SL(2), Canad. J. Math. 31 no. 4 (1979), 726–785. doi:10.4153/CJM-1979-070-3
  * [37] T. Y. Lam, A First Course in Noncommutative Rings, Graduate Texts in Mathematics 131, Springer-Verlag, New York, 1991.
  * [38] S. Lang, Algebraic Number Theory, 2nd ed., Graduate Texts in Mathematics 110, Springer-Verlag, New York, 1994.
  * [39] R. P. Langlands, Base Change for $\operatorname{GL}(2)$, Annals of Math. Studies 96, Princeton U. P., Princeton, 1980.
  * [40] E. A. Lauret and B. Linowitz, The spectral geometry of hyperbolic and spherical manifolds: analogies and open questions, New York J. Math. 30 (2024), 682–721.
  * [41] E. A. Lauret, R. J. Miatello and J. P. Rossetti, Representation equivalence and $p$-spectrum of constant curvature space forms, J. Geom. Anal. 25 (2015), 564–591.
  * [42] E. A. Lauret, R. J. Miatello and J. P. Rossetti, Spectra of lens spaces from 1-norm spectra of congruence lattices, Int. Math. Res. Not. IMRN 2016 (2016), 1054–1089.
  * [43] B. Linowitz, Selective orders in central simple algebras and isospectral families of arithmetic manifolds, Manuscripta Math. 147 (2015), 399–413.
  * [44] B. Linowitz and J. Voight , Small isospectral and nonisometric orbifolds of dimension $2$ and $3$, Math. Z. 281 no. 1 (2015), 523–569.
  * [45] T. H. Marshall and G. J. Martin, Minimal co-volume hyperbolic lattices, II: Simple torsion in a Kleinian group, Ann. of Math. 176 no. 1 (2012), 261–301.
  * [46] H. Matsumura, Commutative ring theory, Cambridge Studies in Advanced Mathematics 8 (2nd ed.), Cambridge University Press, Cambridge, 1989.
  * [47] Y. Matsushima, A formula for the Betti numbers of compact locally symmetric Riemannian manifolds, J. Diff. Geom. 1 (1967), 99–109.
  * [48] P. Molin and A. Page, Computing groups of Hecke characters, Res. Number Theory 8 (2022).
  * [49] W. Müller, Analytic torsion and R-torsion of Riemannian manifolds, Adv. Math. 28 (1978), 233–305.
  * [50] W. Müller, Analytic torsion and R-torsion for unimodular representations, J. Amer. Math. Soc. 6 (1993), 721–753.
  * [51] S. Patrikis, Variations on a theorem of Tate, Memoirs of the AMS 258 no. 1238 (2019).
  * [52] R. Perlis, On the equation $\zeta_{K}(s)=\zeta_{K^{\prime}}(s)$, J. Number Theory 9 (1977), 342–360.
  * [53] H. Pesce, Variétés hyperboliques et elliptiques fortement isospectrales, J. Funct. Anal. 134 (1995), 363–391.
  * [54] J. Raimbault, Analytic torsion, regulators and arithmetic hyperbolic manifolds, P. Charollois (ed.) et al., Arithmetic L-functions and differential geometric methods. Regulators IV, May 2016, Paris. Cham: Birkhäuser. Prog. Math. 338 (2021), 179–212.
  * [55] C. S. Rajan, On isospectral arithmetical spaces, Amer. J. Math. 129 no. 3 (2007), 791–806.
  * [56] C. S. Rajan, Some questions on spectrum and arithmetic of locally symmetric spaces Adv. Stud. Pure Math. 58 (2010), 137–157.
  * [57] I. Reiner, Maximal Orders, Academic Press Inc., London, 1975.
  * [58] S. Rosenberg, The Laplacian on a Riemannian Manifold, LMSST 31, Cambridge University Press, 1997.
  * [59] R. Schmidt, Some remarks on local newforms for $\operatorname{GL}(2)$, J. Ramanujan Math. Soc. 17 no. 2 (2002), 115–147.
  * [60] P. Scholze, On torsion in the cohomology of locally symmetric varieties, Annals Math. 182 no. 3 (2015), 945–1066.
  * [61] J.-P. Serre, Propriétés galoisiennes des points d’ordre fini des courbes elliptiques, Invent. Math. 15 (1972), 259–331.
  * [62] T. Sunada, Riemannian coverings and isospectral manifolds, Annals Math. 121 no. 1 (1985), 169–186.
  * [63] Y. Taguchi, Induction formula for the Artin conductors of mod $\ell$ Galois representations, Proc. Amer. Math. Soc. 130 no.10 (2002), 2865–2869.
  * [64] A. Tenie, Strongly isospectral hyperbolic 3-manifolds with nonisomorphic rational cohomology rings, preprint, arXiv:2111.11454 [math.GT] (2021).
  * [65] M.-F. Vignéras, Représentations $l$-modulaires d’un groupe réductif $p$-adique avec $l\neq p$, Progress in Mathematics 137, Birkhäuser, Boston, Boston, 1996.
  * [66] M.-F. Vignéras, Variétés riemanniennes isospectrales et non isométriques, Ann. of Math. (2) 112 no.1 (1980), 21–32.
  * [67] J. Voight, Quaternion Algebras, Graduate Texts in Mathematics 288, Springer, Cham, 2021.
  * [68] A. Weil, On a certain type of characters of the idèle-class group of an algebraic number-field, Proceedings of the international symposium on algebraic number theory, Tokyo & Nikko, 1955 (Tokyo), Science Council of Japan, 1956, 1–7.
  * [69] J. A. Wolf, Isospectrality for Spherical Space Forms, Result. Math. 40 (2001), 321–338.


# A 3-Approximation Algorithm for a Particular Case of the Hamiltonian
$p$-Median Problem

Michel Wan Der Maas Soares
<EMAIL_ADDRESS>Dilson Lucas Pereira
<EMAIL_ADDRESS>
Departamento de Computação Aplicada
Universidade Federal de Lavras

(2019)

## Abstract

Given a weighted graph $G$ with $n$ vertices and $m$ edges, and a positive
integer $p$, the Hamiltonian $p$-median problem consists in finding $p$ cycles
of minimum total weight such that each vertex of $G$ is in exactly one cycle.
We introduce an $O(n^{6})$ 3-approximation algorithm for the particular case
in which $p\leq\lceil\frac{n-2\lceil\frac{n}{5}\rceil}{3}\rceil$. An
approximation ratio of 2 might be obtained depending on the number of
components in the optimal 2-factor of $G$. We present computational
experiments comparing the approximation algorithm to an exact algorithm from
the literature. In practice much better ratios are obtained. For large values
of $p$, the exact algorithm is outperformed by our approximation algorithm.

Keywords: Hamiltonian $p$-median problem, approximation algorithms, 2-factor,
matching

##  1 Introduction

Given a graph $G=(V,E)$ with $n$ vertices and $m$ edges, a positive integer
$p$, and a set of edge weights $\\{c_{e}\in\mathbb{R}_{+}:e\in E\\}$, the
Hamiltonian $p$-median problem (H$p$MP) asks for $p$ cycles of minimum total
weight, such that each vertex of $G$ is in exactly one cycle. A cycle is
defined as a sequence of vertices $(v_{1},v_{2},\ldots,v_{k},v_{1})$ such that
$k\geq 3$, $\\{v_{k},v_{1}\\}\in E$, $\\{v_{i},v_{i+1}\\}\in E$ for $1\leq
i<k$, and $v_{i}\neq v_{j}$, for $1\leq i<j\leq k$. Note that the problem has
a feasible solution only if $p\leq\left\lfloor\frac{n}{3}\right\rfloor$. In
what follows, we assume that $E$ is complete and the edge weights satisfy the
triangle inequality.

A particular case of the H$p$MP, when $p=1$, is the traveling salesman problem
(TSP) [3], one of the best known NP-Hard combinatorial optimization problems.
Consequently, the H$p$MP is also NP-Hard. In fact, the TSP can be reduced to
the H$p$MP for any value of $p$.

The H$p$MP was introduced by Branco and Coelho [1]. Formulations and exact
approaches were studied in [6, 13, 8, 7, 11, 5]. A polyhedral study was
conducted in [9]. An iterated local search heuristic was introduced in [5].
Not many heuristic approaches have been proposed for the problem.

Since polynomial time approximation algorithms exist for the TSP [12], a
natural research question is whether such algorithms exist for the H$p$MP. In
this paper, we introduce a 3-approximation algorithm that runs in $O(n^{6})$
for the particular case of the H$p$MP in which
$p\leq\lceil\frac{n-2\lceil\frac{n}{5}\rceil}{3}\rceil$. To the best of our
knowledge, this is the first approximation algorithm proposed for the problem.

The rest of the paper is organized as follows. The approximation algorithm is
introduced in Section 2, along with complexity and approximation results. In
Section 3, we present some experimental results, comparing the approximation
to an exact algorithm. Concluding remarks are given in Section 4.

##  2 The Approximation Algorithm

Before presenting the algorithm, we introduce some notation. The notation
$S\subseteq G$ is used to indicate that $S$ is a subgraph of $G$. Given
$S\subseteq G$, we let $V(S)$ denote its set of vertices and $E(S)$ denote its
set of edges. We define the weight of $S$ as $c(S)=\sum_{e\in E(S)}c_{e}$. We
refer to cycles containing exactly $k$ vertices as $k$-cycles. The optimal
H$p$MP solution is denoted $H^{*}$.

The approximation algorithm we propose is based on the concept of 2-factors. A
2-factor of a graph is a set of cycles such that each vertex is in exactly one
cycle. A related concept is that of 2-matchings, the difference being that
2-matchings might have cycles containing only 2 vertices. Given a weighted
graph, a 2-factor having minimum total weight can be found in polynomial time,
using matching techniques. One possible approach, presented in [2], is
reproduced in Section 2.1. As any feasible H$p$MP solution is a 2-factor, the
minimum weight 2-factor yields a lower bound on the optimal H$p$MP solution.

The approximation algorithm is presented in Algorithm 1.

1:Find a minimum weight 2-factor $F$ of $G$. Note that $c(F)\leq c(H^{*})$.
Let $q$ be the number of cycles in $F$.

2:if $q=p$ then

3: $H\leftarrow F$.

4:else

5: if $q>p$ then

6: Find a spanning tree $T$ of $G$, remove its $p-1$ edges with largest
weight. Note that after the removal $c(T)\leq c(H^{*})$ and the number of
components in $T$ is $p$, but some of its components might be singletons.

7: Since $T$ has $p$ components, its union with $F$ will create a graph with
$p$ or less components. Add to $F$ edges of $T$ connecting different
components of $F$ until it has $p$ components. Note that after this $c(F)\leq
2c(H^{*})$.

8: Transform $F$ into a multigraph by duplicating the edges that were added
from $T$, $c(F)\leq 3c(H^{*})$.

9: else if $q<p$ then

10: while $F$ does not have $p$ components do

11: Select a component of $F$ with at least six vertices. For the special case
of $p\leq\lceil\frac{n-2\lceil\frac{n}{5}\rceil}{3}\rceil$ such a component
always exists. This component is either a cycle
$(v_{1},v_{2},\ldots,v_{k},v_{1})$ or a path $(v_{1},v_{2},\ldots,v_{k})$.
Irrespective of the case, replace it by two paths $(v_{1},v_{2},v_{3})$ and
$(v_{4},\ldots,v_{k})$. Note that this does not increase $c(F)$, i.e.,
$c(F)\leq c(H^{*})$.

12: end while

13: Transform $F$ into a multigraph by duplicating all of its edges, $c(F)\leq
2c(H^{*})$.

14: end if

15: Note that $F$ is a multigraph with $p$ connected components in which the
degree of each vertex is even. The approximate solution $H$ is obtained by
following an Eulerian tour for each component of $F$, skipping vertices
already visited.

16:end if

17:Return $H$. If case $q=p$ was executed $H$ is an optimal solution. If case
$q>p$ was executed, $H$ is a 3-approximation. If case $q<p$ was executed, $H$
is a 2-approximation.

Algorithm 1 H$p$MP approximation algorithm.

For general values of $p$, it might happen that in step 11 the number of
components in $F$ is less than $p$ and there are no components with six or
more vertices. As an example, if $n=10$, $p=3$, and the optimal 2-factor has 2
connected components with 5 vertices each, the algorithm will fail. This type
of problem is caused by components of $F$ whose number of vertices is not a
multiple of 3. When splitting components in step 11, a component with $k$
vertices will have $k\mod 3$ vertices that cannot be left alone, as they are
not enough to form a cycle. If we try to connect them to vertices coming from
other components we might violate the approximation ratio guarantee. For the
special case we consider,
$p\leq\lceil\frac{n-2\lceil\frac{n}{5}\rceil}{3}\rceil$, a component with at
least six vertices will always exist in step 11. This is proven below, we will
need the following result first:

######  Lemma 1.

Given a 2-factor $F$ of $G$ composed of $q$ cycles $\\{C_{1},\ldots,C_{q}\\}$
let $l(F)=\sum_{i=1}^{q}(|V(C_{i})|\mod 3)$ be the number of vertices that
cannot form cycles by themselves in step 11 of Algorithm 1. Then, the maximum
possible value of $l(F)$ over all 2-factors of $G$ is not greater than
$2\left\lceil\frac{n}{5}\right\rceil$.

###### Proof.

We first show that the maximum of $l(F)$ is attained when $F$ is a 2-factor
having the maximum possible number of 5-cycles. Let $F^{*}$ be a 2-factor
attaining the maximum value of $l$. Let $r$ be the size of the largest cycle
of $F^{*}$. If $F^{*}$ is not a 2-factor with the maximum possible number of
5-cycles, we can always construct another two factor from $F^{*}$ having one
more 5-cycle than $F^{*}$ without decreasing $l(F^{*})$. If $r\geq 8$, replace
the corresponding cycle by two cycles, one containing 5 and the other
containing the remaining vertices. If $r\leq 7$, there must be another cycle
with number of vertices $r^{\prime}$ such that $r^{\prime}\leq 7$ and
$r^{\prime}\neq 5$, otherwise $F^{*}$ has the maximum possible number of
5-cycles. Now, it is a matter of examining the possibilities and showing that
for each of them we can construct another 2-factor having more 5-cycles than
$F^{*}$ yielding the same value (or a larger value) of $l(F^{*})$. The
possibilities are:

  * •

$r=7$ and $r^{\prime}=7$, we can generate cycles with 5, 5, and 4 vertices,
respectively.

  * •

$r=7$ and $r^{\prime}=6$, we can generate cycles with 5, 5, and 3 vertices,
respectively.

  * •

$r=7$ and $r^{\prime}=4$, we can generate cycles with 5 and 6 vertices,
respectively.

  * •

$r=7$ and $r^{\prime}=3$, we can generate cycles with 5 and 5 vertices,
respectively.

  * •

$r=6$ and $r^{\prime}=6$, we can generate cycles with 5 and 7 vertices,
respectively.

  * •

$r=6$ and $r^{\prime}=4$, we can generate cycles with 5 and 5 vertices,
respectively.

  * •

$r=6$ and $r^{\prime}=3$, we can generate cycles with 5 and 4 vertices,
respectively.

  * •

$r=4$ and $r^{\prime}=4$, we can generate cycles with 5 and 3 vertices,
respectively.

  * •

$r=4$ and $r^{\prime}=3$, $F^{*}$ already has the maximum number of 5-cycles.

Now, if $F$ has the maximum number of 5-cycles, than it has at least
$\left\lfloor\frac{n}{5}\right\rfloor-1$ 5-cycles. The possible values for the
remaining $n-(\left\lfloor\frac{n}{5}\right\rfloor-1)$ vertices are
$5,\ldots,9$. If there are 5 remaining vertices, the maximum of $l(F)$ is
attained by organizing them into a 5 cycle, in which case $l(F)=2\frac{n}{5}$.
If there are 6 remaining vertices, the maximum of $l(F)$ is attained by
organizing them into a 6-cycle, in which case
$l(F)=2(\left\lfloor\frac{n}{5}\right\rfloor-1)$. If there are 7, the maximum
is attained by organizing them into a 7-cycle,
$l(F)=2(\left\lfloor\frac{n}{5}\right\rfloor-1)+1$. If there are 8, by
organizing them into a 5-cycle and a 3-cycle,
$l(F)=2\left\lfloor\frac{n}{5}\right\rfloor$. And if there are 9, by
organizing them into a 5-cycle and a 4-cycle,
$l(F)=2\left\lfloor\frac{n}{5}\right\rfloor+1$. In all these cases, $l(F)\leq
2\left\lceil\frac{n}{5}\right\rceil$. ∎

######  Proposition 1.

It is possible to split any 2-factor of a graph $G$ into at least
$\left\lceil\frac{n-2\left\lceil\frac{n}{5}\right\rceil}{3}\right\rceil$
connected components containing at least 3 vertices each.

###### Proof.

Given a 2-factor $F$ of $G$ composed of $q$ cycles $\\{C_{1},\ldots,C_{q}\\}$,
the maximum number of connected components with at least 3 vertices it can be
split into is
$\frac{n-l(F)}{3}\geq\left\lceil\frac{n-2\left\lceil\frac{n}{5}\right\rceil}{3}\right\rceil$,
since $l(F)\leq 2\left\lceil\frac{n}{5}\right\rceil$ and the number of
resulting components is integer. ∎

Thus, for
$p\leq\left\lceil\frac{n-2\left\lceil\frac{n}{5}\right\rceil}{3}\right\rceil$,
Algorithm 1 is guaranteed to find a feasible solution.

######  Theorem 1.

For the special case of the H$p$MP with
$p\leq\lceil\frac{n-2\lceil\frac{n}{5}\rceil}{3}\rceil$, Algorithm 1 finds a
solution $H$ with $c(H)\leq 3c(H^{*})$ in $O(n^{6})$ time.

###### Proof.

The dominating term in the computational complexity of Algorithm 1 is given by
step 1. The minimum weight 2-factor of a graph $G$ can be found by executing a
minimum weight perfect matching (MWPM) algorithm on an auxiliary graph
$G^{\prime}$ with $O(n^{2})$ vertices and $O(m)$ edges, obtained from $G$. The
MWPM of a graph $G$ can be found in $O(n^{2}m)$ [4], thus, finding the MWPM of
$G^{\prime}$ is $O(n^{6})$ as we assume $E$ to be complete. The approximation
factor was proven along the algorithm description. ∎

For the sake of completeness, in the next section we present a scheme for
finding a minimum weight 2-factor of $G$.

###  2.1 Finding minimum weight 2-factors of $G$

Minimum weight 2-factors of $G$ can be found on a appropriately defined
auxiliary graph, as described in [2], pp. 185. First, define a graph
$G^{\prime}=\\{V^{\prime},E^{\prime}\\}$: Replace each edge $e=\\{u,v\\}$ of
$E$ by two new vertices $a_{e}^{u}$ and $a_{e}^{v}$ and three new edges
$\\{u,a_{e}^{u}\\}$, $\\{a_{e}^{u},a_{e}^{v}\\}$, and $\\{a_{e}^{v},v\\}$.

Now, define a graph $G^{\prime\prime}=\\{V^{\prime\prime},E^{\prime\prime}\\}$
from $G^{\prime}$: For each original vertex $v\in V\cap V^{\prime}$, replace
it by two new vertices $b^{\prime}_{v}$ and $b_{v}^{\prime\prime}$. Replace
every edge $\\{v,a_{e}^{v}\\}$ by two new edges
$\\{b^{\prime}_{v},a_{e}^{v}\\}$ and $\\{b^{\prime\prime}_{v},a_{e}^{v}\\}$,
both with weight
$c^{\prime\prime}_{\\{b^{\prime}_{v},a_{e}^{v}\\}}=c^{\prime\prime}_{\\{b^{\prime\prime}_{v},a_{e}^{v}\\}}=\frac{c_{e}}{2}$.
Let $c^{\prime\prime}_{e}=0$ for any other edge in $E^{\prime\prime}$.

An edge $e=\\{u,v\\}\in E$ is in the minimum weight 2-factor of $G$ if and
only if $\\{b^{\prime}_{u},a_{e}^{u}\\}$ or
$\\{b^{\prime\prime}_{u},a_{e}^{u}\\}$ is in the minimum weight perfect
matching of $G^{\prime\prime}$, in which case either
$\\{b^{\prime}_{v},a_{e}^{v}\\}$ or $\\{b^{\prime\prime}_{v},a_{e}^{v}\\}$
will also be in the matching.

##  3 Computational Experiments

In this section, we present results from computational experiments that were
conducted to evaluate the practical approximation ratio of the algorithm
introduced here, as well as its performance in comparison to an exact
algorithm.

We consider the instances with 100 vertices among those proposed in
Gollowitzer et al. [8], they comprise 5 complete Euclidean graphs whose
vertices were randomly generated by sampling 100 points in the square
$[0,100]^{2}$. These instances are numbered 1-5. Besides these 5 instances, 5
more instances were generated following the same scheme. These instances are
numbered 6-10. Since $n=100$ in all instances, the special H$p$MP case for
which our algorithm was devised consists of the instances with $p\leq 20$.
Besides values of $p$ in this range we also considered larger values, in order
to evaluate the algorithm’s behavior for more general values of $p$. The
following values of $p$ were considered: $\\{2,10,18,26,33\\}$.

Gollowitzer et al. [7] propose several models from the H$p$MP. The exact
algorithm we use in the experiments is the one based on “model 1”, the best
performing algorithm in that reference. We had access to its source code and
ported it to the version 12.63 of the IBM CPLEX solver.

The computational experiments were carried in an Intel XEON machine with 8GB
of RAM and 8 cores running at 3.5GHz, running under Linux Ubuntu 14.04. Both
the exact and the approximation algorithm were implemented in C++ and
evaluated on this same computational environment. A time limit of 1 hour was
imposed for the exact algorithm. The source code for the approximation
algorithm can be found in [10].

The computational results are presented in Tables 1 and 2. Table 1 presents
results for $p\in\\{2,10,18\\}$ while Table 2 presents results for
$p\in\\{26,33\\}$. Under the heading “Instance” we present instance
information: the value of $p$ and a number identifying the instance. Under the
heading “Exact Algorithm” we present results for the exact algorithm: the
lower ($lb$) and upper bound ($ub$) upon the algorithm termination, and the
total computational time in seconds ($t(s)$). Under the heading “Approximation
Algorithm“, we present results for the approximation algorithm: the obtained
upper bound ($ub$), the total computational time ($t(s)$), the approximation
factor (apx) in relation to the lower bound provided the exact algorithm and
the number of cycles ($q$) in the 2-factor computed in step 1 of Algorithm 1.

Instance |  | Exact Algorithm |  | Approximation Algorithm
---|---|---|---|---
$p$ | ID |  | $lb$ | $ub$ | $t(s)$ |  | $ub$ | $t(s)$ | apx | $q$
2 | 1 |  | 782.29 | 782.29 | 665.7 |  | 1018.72 | 2.57 | 1.3 | 16
| 2 |  | 781.52 | 781.52 | 38.7 |  | 920.02 | 2.99 | 1.17 | 11
| 3 |  | 732.24 | 732.24 | 132.95 |  | 850.01 | 2.49 | 1.16 | 9
| 4 |  | 789.62 | 789.62 | 559.4 |  | 873.28 | 2.87 | 1.1 | 9
| 5 |  | 748.19 | 748.19 | 134.2 |  | 962.85 | 2.62 | 1.28 | 16
| 6 |  | 761.12 | 761.12 | 73.12 |  | 815.12 | 2.63 | 1.07 | 7
| 7 |  | 754.79 | 754.79 | 76.56 |  | 922.95 | 2.57 | 1.22 | 14
| 8 |  | 752.55 | 783.93 | 3600 |  | 1067.03 | 2.62 | 1.41 | 22
| 9 |  | 778.12 | 778.12 | 235.31 |  | 1059.02 | 2.61 | 1.36 | 19
| 10 |  | 787.75 | 787.75 | 19.31 |  | 965.22 | 2.45 | 1.22 | 14
| avg. |  | 766.81 | 769.95 | 553.52 |  | 945.42 | 2.64 | 1.22 | 13.7
10 | 1 |  | 758.52 | 758.52 | 5.9 |  | 838.53 | 2.54 | 1.1 | 16
| 2 |  | 770.25 | 770.25 | 3.9 |  | 780.97 | 2.93 | 1.01 | 11
| 3 |  | 714.49 | 714.49 | 2.39 |  | 742.5 | 2.63 | 1.03 | 9
| 4 |  | 764.74 | 764.74 | 2.44 |  | 796.01 | 2.77 | 1.04 | 9
| 5 |  | 724.61 | 724.61 | 15.03 |  | 798.97 | 2.58 | 1.1 | 16
| 6 |  | 748.96 | 748.96 | 50.68 |  | 776.61 | 2.61 | 1.03 | 7
| 7 |  | 737.49 | 737.49 | 7.17 |  | 771.79 | 2.44 | 1.04 | 14
| 8 |  | 721.92 | 721.92 | 95.25 |  | 879.43 | 2.53 | 1.21 | 22
| 9 |  | 751.18 | 751.18 | 18.49 |  | 885.37 | 2.6 | 1.17 | 19
| 10 |  | 767.77 | 767.77 | 1.09 |  | 811.65 | 2.45 | 1.05 | 14
| avg. |  | 745.99 | 745.99 | 20.23 |  | 808.18 | 2.60 | 1.07 | 13.7
18 | 1 |  | 754.15 | 754.15 | 11.04 |  | 779.62 | 2.55 | 1.03 | 16
| 2 |  | 776.21 | 782.54 | 3600 |  | 843.03 | 2.98 | 1.08 | 11
| 3 |  | 720.43 | 735.43 | 3600 |  | 764.55 | 2.64 | 1.06 | 9
| 4 |  | 769.5 | 770.23 | 3600 |  | 883.84 | 2.69 | 1.14 | 9
| 5 |  | 723.34 | 723.34 | 12.19 |  | 773.38 | 2.56 | 1.06 | 16
| 6 |  | 750.09 | 750.09 | 32.62 |  | 871.85 | 2.63 | 1.16 | 7
| 7 |  | 734.91 | 734.91 | 18.61 |  | 817.68 | 2.51 | 1.11 | 14
| 8 |  | 709.13 | 709.13 | 1.63 |  | 740.2 | 2.53 | 1.04 | 22
| 9 |  | 744.04 | 744.04 | 1.83 |  | 754.58 | 2.6 | 1.01 | 19
| 10 |  | 772.45 | 772.72 | 3600 |  | 820.37 | 2.45 | 1.06 | 14
| avg. |  | 745.42 | 747.65 | 1447.79 |  | 804.91 | 2.614 | 1.07 | 13.7
Table 1: Results for instances with $n=100$ and $p\in\\{2,10,18\\}$. Instance |  | Exact Algorithm |  | Approximation Algorithm
---|---|---|---|---
$p$ | ID |  | $lb$ | $ub$ | $t(s)$ |  | $ub$ | $t(s)$ | apx | $q$
26 | 1 |  | 763.22 | 779.39 | 3600 |  | 821.87 | 2.56 | 1.07 | 16
| 2 |  | 780.01 | 838.97 | 3600 |  | 882.28 | 3.1 | 1.13 | 11
| 3 |  | 724.36 | 776.42 | 3600 |  | 852.75 | 2.48 | 1.17 | 9
| 4 |  | 773.17 | 856.18 | 3600 |  | 885.26 | 2.75 | 1.14 | 9
| 5 |  | 730.45 | 752.31 | 3600 |  | 825.69 | 2.56 | 1.13 | 16
| 6 |  | 757.35 | 814.33 | 3600 |  | 917.27 | 2.63 | 1.21 | 7
| 7 |  | 743.99 | 768.43 | 3600 |  | 853.86 | 2.51 | 1.14 | 14
| 8 |  | 713.33 | 714.26 | 3600 |  | 750.86 | 2.52 | 1.05 | 22
| 9 |  | 750.11 | 757.43 | 3600 |  | 784.2 | 2.59 | 1.04 | 19
| 10 |  | 777.39 | 795.51 | 3600 |  | 881.95 | 2.44 | 1.13 | 14
| avg. |  | 751.33 | 785.32 | 3600 |  | 845.59 | 2.61 | 1.12 | 13.7
33 | 1 |  | 769.34 | 1006.93 | 3600 |  | 826.08 | 2.57 | 1.07 | 16
| 2 |  | 783.96 | 1086.46 | 3600 |  | 877.14 | 3.1 | 1.11 | 11
| 3 |  | 729.49 | 962.52 | 3600 |  | 838.51 | 2.59 | 1.14 | 9
| 4 |  | 778.92 | 1092.88 | 3600 |  | 869.3 | 2.74 | 1.11 | 9
| 5 |  | 736.38 | 893.25 | 3600 |  | 825.47 | 2.56 | 1.12 | 16
| 6 |  | 762.55 | 1195.72 | 3600 |  | 930.87 | 2.75 | 1.22 | 7
| 7 |  | 749.7 | 1044.82 | 3600 |  | 858.56 | 2.66 | 1.14 | 14
| 8 |  | 717.85 | 1045.19 | 3600 |  | 766.35 | 2.5 | 1.06 | 22
| 9 |  | 754.22 | 891.91 | 3600 |  | 833.5 | 2.62 | 1.1 | 19
| 10 |  | 783.52 | 1149.15 | 3600 |  | 908.93 | 2.47 | 1.16 | 14
| avg. |  | 756.59 | 1036.88 | 3600 |  | 853.47 | 2.65 | 1.12 | 13.7
Table 2: Results for instances with $n=100$ and $p\in\\{26,33\\}$.

In terms of performance, the approximation algorithm took between 2.4 and 3.1
seconds to solve the instances, with no significant difference in time across
the different values of $p$. The exact algorithm, on the other hand, was not
able to find the optimal solution for large values of $p$ under the time limit
of one hour, and for the smallest values the time taken varied significantly
from instance to instance.

In terms of solution quality, the approximation algorithm achieved practical
approximation ratios between 1.01 and 1.41. The exact algorithm was able to
find the optimal solution for low values of $p$, and obtained relatively small
optimality gaps for instances with mid-range values of $p$. However, under the
time limit of one hour, for the $p$ value of 33, the approximation algorithm
was able to find better solutions for all instances.

On average, the value of $q$ was 13.7, which explains the fact that a better
practical approximation ratio was obtained for instances with $p=10$ and
$p=18$. The quality of the approximation also seems to be better among the
$p>q$ cases, in which the average gap was 1.10 as opposed to 1.16 for the
other case.

These results highlight the efficiency of the the approximation algorithm:
small computational times and a good practical approximation factor, which in
practice was much better than the theoretical factor of 3.

##  4 Conclusion

In this paper, we introduced a 3-approximation algorithm for the special
$p\leq\lceil\frac{n-2\lceil\frac{n}{5}\rceil}{3}\rceil$ case of the H$p$MP.
The first H$p$MP approximation algorithm in the literature to the best of our
knowledge.

We conducted computation experiments to assess the practical approximation
ratio of the proposed algorithm, comparing it to an exact algorithm from the
literature. The practical approximation ratio was 1.1, on average, with
computational times orders of magnitude smaller than the exact algorithm. In
fact, the approximation algorithm proves to be specially helpful for higher
values of $p$, for which the exact algorithm has a hard time finding the
optimal solution.

As future research, it might be interesting to look for new approximation
algorithms, with better approximation ratios and time complexities, and
capable of handling general values of $p$. Another possible line of research
is the combination of the approximation algorithm with local search
procedures.

## References

  * Branco and Coelho [1990] I. M. Branco and J. D. Coelho.  The hamiltonian p-median problem.  _European Journal of Operational Research_ , 47(1):86 – 95, 1990.
  * Cook et al. [1997] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver.  _Combinatorial Optimization_.  Wiley, 1997.
  * Dantzig et al. [1954] G. Dantzig, R. Fulkerson, and S. Johnson.  Solution of a large-scale traveling-salesman problem.  _Journal of the Operations Research Society of America_ , 2(4):393–410, 1954.
  * Edmonds [1965] Jack Edmonds.  Paths, trees and flowers.  _Canadian Journal of Mathematics_ , pages 449–467, 1965.
  * Erdoğan et al. [2016] G. Erdoğan, G. Laporte, and A. M. R. Chía.  Exact and heuristic algorithms for the hamiltonian p-median problem.  _European Journal of Operational Research_ , 253(2):280 – 289, 2016.
  * Glaab and Pott [2000] H. Glaab and A. Pott.  The Hamiltonian $p$-median problem.  _The Electronic Journal of Combinatorics_ , 7(R42):2, 2000.
  * Gollowitzer et al. [2014] S. Gollowitzer, L. Gouveia, G. Laporte, D. L. Pereira, and A. Wojciechowski.  A comparison of several models for the hamiltonian p-median problem.  _Networks_ , 63(4):350–363, 2014.
  * Gollowitzer et al. [2011] Stefan Gollowitzer, Dilson Lucas Pereira, and Adam Wojciechowski.  New models for and numerical tests of the hamiltonian p-median problem.  In _Volume 6701 of Lecture Notes in Computer Science_ , 2011.  Proceedings of the International Network Optimization Conference (INOC) 2011.
  * Hupp and Liers [2013] L. Hupp and F. Liers.  A polyhedral study of the hamiltonian p-median problem.  _Electronic Notes in Discrete Mathematics_ , 41:213 – 220, 2013.
  * [10] Michel Wan Der Maas.  Implementation of the approximation algorithm.  URL https://github.com/michelwandermaas/p_hamiltonian_heuristic.
  * Marzouk et al. [2016] A. M. Marzouk, E. Moreno-Centeno, and H. Üster.  A branch-and-price algorithm for solving the hamiltonian p-median problem.  _Informs Journal on Computing_ , 28(4), 2016.
  * Vazirani [2001] Vijay V. Vazirani.  _Approximation Algorithms_.  Springer-Verlag, Berlin, Heidelberg, 2001.
  * Zohrehbandian [2007] M. Zohrehbandian.  A new formulation of the Hamiltonian $p$-median problem.  _Applied Mathematical Sciences_ , 1(8):355–361, 2007.