A constant-ratio approximation algorithm for a class of
hub-and-spoke network design problems and metric
labeling problems: star metric case
Yuko Kuroki and Tomomi Matsui
Department of Industrial Engineering and Economics, Tokyo Institute of Technology

arXiv:1803.06114v1 [cs.DM] 16 Mar 2018

kuroki.y.aa@m.titech.ac.jp, matsui.t.af@m.titech.ac.jp
Abstract
Transportation networks frequently employ hub-and-spoke network architectures to route
flows between many origin and destination pairs. In this paper, we deal with a problem, called
the single allocation hub-and-spoke network design problem. In the single allocation hub-andspoke network design problem, the goal is to allocate each non-hub node to exactly one of
given hub nodes so as to minimize the total transportation cost. The problem is essentially
equivalent to another combinatorial optimization problem, called the metric labeling problem.
The metric labeling problem was first introduced by Kleinberg and Tardos [29] in 2002, motivated
by application to segmentation problems in computer vision and energy minimization problems
in related areas.
In this paper, we deal with the case where the set of hubs forms a star, which is called
the star-star hub-and-spoke network design problem, and the star-metric labeling problem. This
model arises especially in telecommunication networks in the case where set-up costs of hub
links are considerably large or full interconnection is not required. We propose a polynomialtime randomized approximation algorithm for these problems, whose approximation ratio is less
than 5.281. Our algorithms solve a linear relaxation problem and apply dependent rounding
procedures.

1

Introduction

Design of efficient networks is desired in transportation systems, such as telecommunications, delivery services, and airline operations, and is one of the extensively studied topics in operations
research field. Transportation networks frequently employ hub-and-spoke network architectures to
route flows between many origin and destination pairs. A transportation network with many origins and destinations requires a huge cost, and hub-and-spoke networks play an important role in
reducing transportation costs and set-up costs. Hub facilities work as switching points for flows in
a large network. Each non-hub node is allocated to exactly one of the hubs instead of assigning
every origin-destination pair directly. Using hub-and-spoke architecture, we can construct large
transportation networks with fewer links, which leads to smart operating systems (see Figure 1).

1

Non-Hub

Hub

Hub-and-Spoke

Point-to-Point

Figure 1: Point-to-Point vs. Hub-and-Spoke

1.1

Single Allocation Hub-and-Spoke Network Desing Problem

In real transportation systems, the location of hub facilities is often fixed because of costs for moving
equipment on hubs. In that case, the decision of allocating non-hubs to hubs is much important for
an efficient transportation. In this study, we discuss the situation where the location of the hubs
is given, and deal with a problem, called a single allocation hub-and-spoke network design problem,
which aims to minimize the total transportation cost.
Formally, the input consists of an h-set H of hubs, an n-set N of non-hubs, non-negative cost per
unit flow c(i, j) = c(j, i) for each pair {i, j} ∈ H 2 , and c(p, i) for each ordered pair (p, i) ∈ N × H.
Additionally, we are given w(p, q) which denotes a non-negative amount of flow from non-hub p to
another non-hub q. The task is to find an assignment f : N → H, that maps non-hubs to hubs
minimizing the total transportation cost Q(f ) defined below. The transportation cost corresponding
to a flow from non-hub p to non-hub q is defined by wpq (c(p, f (p)) + c(f (p), f (q)) + c(f (q), q)). Thus
Q(f ) =

X

w(p, q) (c(p, f (p)) + c(q, f (q)) + c(f (p), f (q))) ,

(p,q)∈N 2

and the goal is to find an assignment that minimizes the total transportation cost.
When the number of hubs is equal to two, there exist polynomial time exact algorithm [25, 39].
Sohn and Park [40] proved NP-completeness of the problem even if the number of hubs is equal
to three. In the case where the given matrix of costs between hubs is a Monge matrix, there
exists a polynomial-time exact algorithm [16]. Iwasa et al. [27] proposed a simple deterministic
3-approximation algorithm and a randomized 2-approximation algorithm under the assumptions
that cij ≤ cpi + cpj (∀(i, j, p) ∈ H 2 × N ) and cij ≤ cik + ckj (∀(i, j, k) ∈ H 3 ). They also proposed a
(5/4)-approximation algorithm for the special case where the number of hubs is three. Ando and
Matsui [2] deal with the case in which all the nodes are embedded in a 2-dimensional plane and the
transportation cost of an edge per unit flow is proportional to the Euclidean distance between the

2

end nodes of the edge. They proposed a randomized (1 + 2/π)-approximation algorithm. In the
previous our work [33], we proposed 2(1 + h1 )-approximation algorithm for the case where the set
of hubs forms a cycle.

1.2

Metric Labeling Problem

In 2002, Kleinberg and Tardos [29] introduced the metric labeling problem, motivated by applications
to segmentation problems in computer vision and energy minimization problems in related areas.
A variety of heuristics that use classical combinatorial optimization techniques have developed in
these fields ([7, 8, 32, 35] for example). A single allocation hub-and-spoke network design problem
includes a class of the metric labeling problem. The metric labeling problem captures a broad
range of classification problems and has connections to Markov random field. In such classification
problems, the goal is to assign labels to some given set of objects minimizing the total cost of
labeling.
Formally, the metric labeling problem takes as input an n-vertex undirected graph G(V, E)
with a nonnegative weight function w on the edges, a set L of labels with metric distance function
d : L × L → R associated with them, and an assignment cost c(v, a) for each vertex v ∈ V and
label a ∈ L. The output is an assignment for every object v ∈ V to a label a ∈ L. Given a solution
f : V → L to the metric labeling, the quality of labeling Q(f ) is based on the contribution of two
sets of terms.
Vertex labeling cost: For each object v ∈ V , this cost is denoted by c(v, f (v)). A vertex labeling
cost c(v, a) express an estimate of its likelihood of having each label a ∈ L. These likelihoods are
observed from some heuristic preprocessing of the data. For example, suppose the observed color
of pixel (i.e., object) v is white; then the cost c(v, black) should be high while c(v, white) should be
low.
Edge separation cost: For each edge e = {u, v} ∈ E, the cost is denoted by w({u, v}) ·
d(f (u), f (v)). The weights of the edges express a prior estimate on relationships among objects; if
u and v are deemed to be related, then we would like them to be assigned close or identical labels.
A distance d(a, b) for a, b ∈ L represents how similar label a and b are. For example, d(white, black)
would be large while d(orange, yellow) would be small. If we assign label a to object u and label b
to object v, then we pay w({u, v})d(a, b) as the edge separation cost.
Thus,
X
X
Q(f ) =
c(u, f (u)) +
w({u, v})d(f (u), f (v)),
u∈V

{u,v}∈E

and the goal is to find a labeling f : V → L minimizing Q(f ). Due to the simple structure and
variety of applications, the metric labeling has received much attention since its introduction by
Kleinberg and Tardos [29].
In case the number of labels is two, the problem can be solved precisely in polynomial-time.
The first approximation algorithm for the metric labeling problem was shown by Kleinberg and Tar3

dos [29], and its approximation ratio is O(log k log log k), where k denotes the number of labels. This
algorithm uses the probabilistic tree embedding tequnique [5]. Using the improved representation
of metrics as combination of tree metrics by Fakcharoenphol, Rao, and Talwar [24], its approximation ratio was improved to O(log k), which is the best general result to date. Constant-ratio
approximations are known for some special cases [4, 11, 16, 29].

1.3

Contributions

We deal with the a single assignment hub-and-spoke network design problem where the given set of
hubs forms a star, and corresponding problem is called the star-star hub-and-spoke network design
problems and star-metric labeling problems. In this case, each hub is only connected to a unique
depot. When all the transportation cost per unit flow between the depot and each hub are same,
this problem is equivalent to the uniform labeling problem (all distances of labels are equal to 1)
introduced in [29] which is still NP-hard. For star-metric case, using the result of [31] for planer
graphs, there exists O(1)-approximation algorithm [29]. The previous O(1)-approximation ratio
is at least 6. We proposed an 
improved approximation algorithm for star-metric case, and the
2
r−1
|r > 1}(≈ 5.2809 at r ≈ 1.91065). Our results give an
approximation ratio is min{ log r 2 + rr2 +1
−1
important class of the metric labeling problem and hub-and-spoke network design problems, which
has a polynomial time approximation algorithm with a constant approximation ratio. In case where
set-up costs of hub links are considerably large, incomplete networks can be used instead of full
interconnection among hub facilities. The star structures, that we discuss in this paper, frequently
arise in especially telecommunication networks [34].

1.4

Related Work

Approximation Results for Metric Labeling Problems. Gupta and Tardos [26] considered
an important case of the metric labeling problem, in which the metric is the truncated linear metric
where the distance between i and j is given by d(i, j) = min{M, |i−j|}. Chekuri et al. [16] proposed
√
(2 + 2)-approximation algorithm for the truncated linear metric, which is best known result.
In the case where the metric d on a set of labels L is a planar metric, there exists O(log diam G0 )approximation to the problem from the result [31] and [29], where G0 = (L, E, w) denote the
weighted connected graph. Konjevod et al. [31] showed that for any positive integer s, the metric
of G without a Ks,s minor can be probabilistically approximated by a special case of tree metric,
called r-hierarchically well separated tree (r-HST) with distortion O(log diam G). Kleinberg and
Tardos [29] gave a constant ratio approximation algorithm to the metric labeling for the case where
the metric d on a set of labels is the r-HST metric. Then O(log diam G0 )-approximation was
guaranteed by combining these results for this case.
Inapproximability Results. Chuzhoy and Naor [17] showed that there is no polynomial time

4

Table 1: Existing approximation algorithms for metric labeling problems
Metric
general
planar graph
truncked linear
uniform

App. Ratio
O(log k) [24, 29]
0
O(log diam
√ G ) [29, 31]
2 + 2 [16]
2 [29]

approximation algorithm with a constant ratio for the metric labeling problem unless P = NP.
Moreover, they proved that the problem is Ω((log |V |)1/2−δ )-hard to approximate for any constant
δsatisf ying0 < δ < 1/2, unless NP⊆DTIME(npoly(log n) ) (i.e. unless NP has quasi-polynomial time
algorithms).
In 2011, Andrew et al. [3] introduced capacitated metric labeling, in which there are additional
restrictions that each label i receives at most li nodes. They proposed a polynomial-time, O(log |V |)approximation algorithm when the number of labels is fixed and proved that it is impossible to
approximate the value of an instance of capacitated metric labeling to within any finite ratio, unless
P = NP.
Hub Location Problems. Hub location problems (HLPs) consist of locating hubs and designing
hub networks so as to minimize the sum of set-up costs and transportation costs. HLPs are formulated as a quadratic integer programming problem by O’Kelly [36] in 1987. Since O’Kelly proposed
HLPs, hub location has been studied by researchers in different areas such as location science,
geography, operations research, regional science, network optimization, transportation, telecommunications, and computer science. Many researches on HLPs have been done in various applications
and there exists several reviews and surveys (see [1,12,15,18,30,37] for example). In case where the
location of the hubs is given, the remaining subproblem is essentially equal to the single allocation
hub-and-spoke network design problem mentioned in previous subsections.
Fundamental HLPs assume a full interconnection between hubs. Recently, several researches
consider incomplete hub networks which arise especially in telecommunication systems (see [1, 10,
13, 14] for example). These models are useful when set-up costs of hub links are considerably large
or full interconnection is not required. That motivated us to consider a single allocation hub-andspoke network design problem where the given set of hubs forms a star (see Figure 2). There are
researches which assume that hub networks constitute a particular structure such as a line [22], a
cycle [21], tree [19, 20, 23, 28, 38, 41], a star [34, 42, 43].

5

(a)

(b)

(c)

(d)

Figure 2: Structure of (a) line-star, (b) cycle-star, (c) tree-star, and (d) star-star

1.5

Paper Organization

This paper is structured as follows In Section 2, we provide a problem formulation. In Section 3,
we describe an approximation algorithm. In Section 4, we analyze the approximation ratio of our
algorithm.

2

Problem Formulation

Let H = {1, 2, . . . , h} be a h (≥ 3)-set of hub nodes and let N = {p1 , p2 , . . . , pn } be a n-set of
non-hub nodes. This paper deals with a single assignment hub network design problem which
assigns each non-hub node to exactly one hub node. We discuss the case in which the set of hubs
forms a star, and the corresponding problem is called the star-star hub-and-spoke network design
problem and/or star-metric labeling problem. More precisely, we are given a unique depot, denoted
by 0, which lies at the center of hubs. Each hub i ∈ H connects to the depot and doesn’t connect
to other hubs. Let `i be the transportation cost per unit flow between the depot and a hub i. In
our setting, we assume that 0 ≤ `1 ≤ `2 ≤ · · · ≤ `h and `i ∈ Z for all i ∈ H. Then for each
pair of hub nodes (i, j) ∈ H, cij denotes the transportation cost per unit flow between hub i and
hub j and it satisfies that cij = `i + `j . We assume cii = 0 for all i ∈ H. For each ordered pair
(p, i) ∈ N × H, cpi denotes a non-negative cost per unit flow on an undirected edge {p, i}. We
denote a given non-negative amount of flow from a non-hub p to another non-hub q by wpq (≥ 0).
Throughout this paper, we assume that wpp = 0 (∀p ∈ N ). We discuss the problem for finding an
assignment of non-hubs to hubs which minimizes the total transportation cost defined below.
When non-hub p and non-hub q (p 6= q) are assigned to hub i and hub j, respectively, an amount
6

ℓ1
𝑐𝑝1

0

1

0

ℓ3
3

𝑐𝑝1

𝑐𝑞3

𝑤𝑝𝑞
𝑝∈𝑁

1

3

𝑤𝑝𝑞
𝑝∈𝑁

𝑞∈𝑁

𝑐𝑞1
𝑞∈𝑁

Figure 3: Examples of transportation

of flow wpq is sent along a path ((p, i), (i, 0), (0, j), (j, q)). In the rest of this paper, a matrix C = (cij )
defined above is called the cost matrix and/or the star-metric matrix. The transportation cost
corresponding to a flow from the origin p ∈ N to destination q ∈ N is defined by wpq (cpi + cij + cqj ).
In case where h = 3 and `1 = `2 = `3 = 1, the corresponding problem is equivalent to the
problem where a 3-set of hubs forms a complete graph and C satisfies that c12 = c23 = c31 = 2.
Thus the star-star hub network design problem is NP-hard [40].
Now we formulate our problem as 0-1 integer programming. First, we introduce a 0-1 variable
xpi for each pair {p, i} ∈ N × H as follows:
(
xpi =

1 (p ∈ N is assigned to i ∈ H),
0 (otherwise).

P
Since each non-hub is connected to exactly one hub, we have a constraint i∈H xpi = 1 for each
p ∈ N . Then, the star-star hub network design problem (star-metric labeling problem) can be
formulated as follows:

X
X
X
X
SHP: min.
wpq
cpi xpi +
cqj xqj +
`k |xpk − xqk |
(p,q)∈N 2 , p6=q

s. t.

X

i∈H

j∈H

k∈H

(∀p ∈ N ),

xpi = 1

i∈H

xpi ∈ {0, 1}

(∀{p, i} ∈ N × H).

Next we describe a linear relaxation problem. By substituting non-negativity constraints of the
variables xpi (∀{p, i} ∈ N × H) for 0-1 constraints in SHP and replace |xpk − xqk | with Zpqk , we

7

obtain the following a linear relaxation problem denoted by LRP.

LRP:

X

min.

(p,q)∈N 2 ,

s. t.

X

wpq

X

cpi xpi +

i∈H

p6=q

X

cqj xqj +

j∈H

X

`k Zpqk 

k∈H

(∀p ∈ N ),

xpi = 1

i∈H

0 ≤ xpi

(∀{p, i} ∈ N × H),

− Zpqk ≤ xpk − xqk ≤ Zpqk (∀(p, q) ∈ N 2 , ∀k ∈ H).
We can solve LRP in polynomial time by employing an interior point algorithm.

3

Algorithm

We now design an approximation algorithm. The approach is proceeded as follows:
Step 1. Choose λ ∈ [0, 1) uniformly at random and classify the hubs under κmax + 1 classes
according to Definition 1.
Step 2. Solve the linear relaxation problem LRP and obtain an optimal solution x∗ .
Step 3. Find a partition of non-hubs by Algorithm 1.
Step 4. Assign each non-hub to a hub by Algorithm 2.
Now, we describe our algorithm precisely. In Step 1, we classify the set of hubs according to
the distance between each hub and the depot (see Figure 4). We assign each hub to a class. This
classification is based on the following definition.
Definition 1. For any λ ∈ [0, 1), we say that hub i belongs to class κ if and only if `i (≥ 1) satisfies
the inequality rmax{(κ−2)+λ,0} ≤ `i < r(κ−1)+λ and hub i belongs to class 0 if and only if `i = 0,
where κ is a non-negative integer.

0

𝐻2

𝐻1

𝐻0

Class 0

ℓ1

Class 1

𝑟0

𝐻3

Class 2

𝑟𝜆

Class 3

𝑟1+𝜆

𝑟 2+𝜆

Figure 4: Classification of Hubs

Before we describe the details of later steps, we introduce some notations. Let α(λ, i) be the
class of hub i ∈ H. We denote a subset of integers {0, 1, 2, ..., κmax } by [κmax ] where κmax =
8

Algorithm 1: Classify each non-hub into a class
Require: An optimal solution x∗ of LRP and a total order π of the hubs.
Ensure: A partition of non-hubs N0 , N1 , · · · , Nκmax .
1: Set Ni = ∅ (∀i ∈ [0, 1, . . . , κmax ])
2: Generate a random variable U which follows a uniform distribution defined on [0, 1).
3: for p ∈ N do
4:
Insert non-hub p into a subset Nα(λ,π(i)) , where i ∈ {1, 2, . . . , |H|} is the minimum number
that satisfies U < xpπ(1) + xpπ(2) + · · · + xpπ(i) .
5: end for
6: return N0 , N1 , · · · , Nκmax .

maxi∈H α(λ, i). Let Hκ be a subset of hubs that belongs to class k ∈ [κmax ] i.e. Hκ = {i ∈
H | α(λ, i) = κ}. Let β(p) be the class that non-hub p ∈ N belongs to. We denote a subset of
non-hubs that belong to class κ ∈ [κmax ] by Nκ i.e. Nκ = {p ∈ N | β(p) = κ}.
In Step 2, we solve the linear relaxation problem LRP formulated in the previous subsection.
We use an optimal solution x∗ in Algorithm 1 and Algorithm 2.
In Step 3, we assign each non-hubs to a class of hubs defined by Definition 3. For example, if
non-hub p1 belongs to the subset N3 obtained by Algorithm 1, p1 will be assigned to one of hubs
in H3 defined by Definition 3. Given an optimal solution of LRP and a total order of the hubs,
Algorithm 1 outputs a partition of non-hubs, N0 , N1 , · · · , Nκmax .
Here, a total order of hubs depends on labels of classes. For example, the total order of hubs
in Figure 5 is (5, 4, 1, 3, 2). The order of class labels π 0 is (κmax , , . . . , 4, 2, 0, 1, 3, . . . , κmax − 1)
when κmax is an even number, and (κmax − 1, . . . , 4, 2, 0, 1, 3, . . . , κmax ) when κmax is an odd number. The order of class labels in Figure 5 is (2, 0, 1, 3) for example. For each non-hub p, we
place xpi for i ∈ Hκ in the order of class labels. Then, the total order of hubs π is defined as

any order of hubs in Hπ0 (1) , any order of hubs in Hπ0 (2) , . . . , any order of hubs in Hπ0 (κmax +1 ) in our
rounding scheme, where π 0 (i) denotes the i-th element of π 0 .
In Step 4, we decide an assignment from non-hubs to hubs using rounding technique. In Algorithm 2, we perform a rounding procedure for each subset of non-hubs. For a subset Nκ ⊆ N , we
first choose hub i ∈ Hκ and U ∈ [0, 1) uniformly at random. Then, if U ≤ x∗pi , we assign non-hub
p to hub i (see Figure 6). Until all the non-hubs are assigned to one of hubs, we continue this
procedure. Note that in each phase we can set the upper bound of U to the maximum value of xpi
of remained non-hubs.

4

Analysis of Approximation Ratio


r−1
In this subsection, we show that our algorithm obtains a min{ log
r 2+
approximate solution for any instance.

9

r2 +1
r2 −1



|r > 1} ≈ 5.2809-

1

𝑈

𝑥𝑝∗1 2
𝑥𝑝∗1 3
𝑥𝑝∗∗1 1
𝑥𝑝1
𝑥𝑝∗1 4

0

𝑥𝑝∗1 5

Non-hub 𝑝1

𝑝2

𝑝3

・・・

Figure 5: Dependent rounding procedure to classify each non-hub into a class

1

𝑈

𝑥𝑝∗4 4

𝑥𝑝∗1 4
𝑥𝑝∗2 4

𝑥𝑝∗5 4

𝑥𝑝∗3 4

0
Non-hub 𝑝1

𝑝2

𝑝3

𝑝4

𝑝5

Figure 6: Non-hub p1 and p4 are assigned to hub 4 by this phase, where Hκ = {4, 5} and Nκ =
{p1 , p2 , p3 , p4 , p5 }

10

Algorithm 2: Assign each non-hub to a hub
Require: An optimal solution x∗ of LRP and κmax + 1 subsets of non-hubs N0 , . . . , Nκmax .
Ensure: An assignment from non-hubs to hubs X.
1: for κ = 0, 1, . . . , κmax do
2:
Initialize S ← Nκ
3:
while |S| > 0 do
4:
Choose hub i ∈ Hκ uniformly at random.
5:
Choose U ∈ [0, 1) uniformly at random.
6:
for p ∈ S do
7:
if U ≤ x∗pi then Xpi = 1, Xpj = 0 (∀j ∈ Hκ \ {i})
8:
S ← S \ {p}.
9:
end for
10:
end while
11: end for
12: return X.

Notation. We introduce some notations that we use throughout this subsection. Let α(λ, i) be the
class of hub i ∈ H. For any i ∈ H, let define u(λ, i) = r(α(λ,i)−1)+λ if `i ≥ 1, u(λ, i) = 0 if `i = 0,
where r is a real number satisfying r > 1, i.e.,
(
u(λ, i) =

rα(λ,i)+λ−1 (`i ≥ 1),
0
(`i = 0).

Let define a cost ĉij for each pair {i, j} ∈ H 2 as follows:
(
ĉij =

|u(λ, i) − u(λ, j)| (α(λ, i) = α(λ, j) (mod 2)),
u(λ, i) + u(λ, j) (otherwise).

Remark. A metric defined by Ĉ = ĉij becomes a line metric (see Figure 7). Thus the matrix Ĉ is
a Monge matrix.

Class 3
５
４

Class 2

Class 1
１

0

３
２

𝑢(𝜆, 1)
Figure 7: A metric defined by Ĉ

Now we start with the following lemma.
Lemma 1. Let x∗ be an optimal solution of LRP. A vector of random variables X obtained by the
proposed algorithm satisfies that Pr[Xpi = 1] = x∗pi (∀p ∈ N, ∀i ∈ H).
11

Proof.
Pr[Xpi = 1] = Pr[p ∈ N is classified into Nα(λ,i) ] Pr[p ∈ N is assigned to i(∈ H)]


X
x∗pi /|H α(λ,i) |
∗ 

=
= x∗pi .
xpj P
∗
α(λ,i) |
j:α(λ,j)=α(λ,i) xpj /|H
j:α(λ,j)=α(λ,i)

Lemma 2. For any pair of hubs {i, j} ∈ Hκ × Hκ0 , any real number r > 1, and any real number
2 +1
λ ∈ [0, 1), we have the inequality u(λ, i) + u(λ, j) ≤ rr2 −1
ĉij , where κ, κ0 ∈ [κmax ] and κ 6= κ0 .
Proof. (Case i) κ − κ0 ≡ 0 ( mod 2)
In this case, it is obvious that
u(λ, i) + u(λ, j)
u(λ, i) + u(λ, j)
max{u(λ, i), u(λ, j)} − min{u(λ, i), u(λ, j)}
max{u(λ, i), u(λ, j)} − min{u(λ, i), u(λ, j)}
max{u(λ, i), u(λ, j)} + min{u(λ, i), u(λ, j)}
=
ĉij
max{u(λ, i), u(λ, j)} − min{u(λ, i), u(λ, j)}
r2 max{u(λ, i), u(λ, j)} + r2 min{u(λ, i), u(λ, j)}
= 2
ĉij .
r max{u(λ, i), u(λ, j)} − r2 min{u(λ, i), u(λ, j)}

=

Recall that k 6= κ0 and k − κ0 ≡ 0 ( mod 2), and thus it holds that r2 min{u(λ, i), u(λ, j)} ≤
max{u(λ, i), u(λ, j)} for any pair of hubs {i, j} ∈ Hκ × Hκ0 . Then we get
r2 max{u(λ, i), u(λ, j)} + r2 min{u(λ, i), u(λ, j)}
ĉij
r2 max{u(λ, i), u(λ, j)} − r2 min{u(λ, i), u(λ, j)}
r2 max{u(λ, i), u(λ, j)} + max{u(λ, i), u(λ, j)}
r2 + 1
≤ 2
ĉij = 2
ĉij .
r max{u(λ, i), u(λ, j)} − max{u(λ, i), u(λ, j)}
r −1
(Case ii) κ − κ0 ≡ 1 ( mod 2)
From the definition, we have that
u(λ, i) + u(λ, j) = ĉij ≤

r2 + 1
ĉij .
r2 − 1

Lemma 3. Let X be a vector of random variables obtained by the proposed algorithm and let x∗ be
an optimal solution of LRP. For any pair of non-hubs (p, q) ∈ N 2 and any real number λ ∈ [0, 1),

12

we have the following inequality



X

E

X

(`i + `j )Xpi Xqj  ≤ 2

κ∈[κmax ] (i,j)∈Hκ2 :i6=j

X

u(λ, i)|x∗pi − x∗qi |.

i∈H

Proof. First, for any integer κ ∈ [κmax ], we show that



X

E

(`i + `j )Xpi Xqj  ≤ 2

(i,j)∈Hκ2 :i6=j

X

u(λ, i)|x∗pi − x∗qi |.

(4.1)

i∈Hκ

(Case i) κ = 0
hP
i
P
We can see that E
(`
+
`
)X
X
= 0 (∵ ∀(i, j) ∈ H02 , `i = `j = 0) and i∈Hκ u(λ, i)|x∗pi −
2
i
j
pi
qj
(i,j)∈H0 :i6=j
x∗qi | = 0 (∵ ∀i ∈ H 0 , u(λ, i) = 0). Then we obtain the inequality (4.1) for this case.
(Case ii) κ ∈ {1, 2, . . . , κmax }
In this case, it is easy to see that

E


X

(`i + `j )Xpi Xqj  =

(i,j)∈Hκ2 :i6=j

≤

X

X

((`i + `j )Pr[Xpi = Xqj = 1])

(i,j)∈Hκ2 :i6=j

2rκ+λ−1 Pr[Xpi = Xqj = 1] (∵ ∀i ∈ Hκ , `i ≤ 2rκ+λ−1 )

(i,j)∈Hκ2 :i6=j

= 2rκ+λ−1

X

Pr[Xpi = Xqj = 1].

(4.2)

(i,j)∈Hκ2 :i6=j

We say that non-hub p and non-hub q are separated by a single phase in Algorithm 2 if both
p and q are unassigned before the phase and exactly one of p and q is assigned in this phase (See
Figure 8). Note that even if p and q are separated by some phase, they may be assigned to a mutual
hub later.

1

𝑈
∗
𝑥𝑝𝑘

∗
𝑥𝑞𝑘

0

𝑥𝑝∗1 𝑘

𝑥𝑝∗2 𝑘

𝑥𝑝∗3 𝑘

Figure 8: Non-hub p and non-hub q are separated in this phase.

13

P
The probability (i,j)∈Hκ2 :i6=j Pr[Xpi = Xqj = 1] in the right-hand side of inequality (4.2) is the
probability that both non-hub p and q are classified into Nκ by Algorithm 1 and non-hub p and q
are assigned to different hubs by Algorithm 2. This probability can be bounded by the probability
that both non-hub p and q are classified into Nκ by Algorithm 1 and non-hub p or q are separated
by some phase in Algorithm 2. Then for any κ ∈ {1, 2, . . . , κmax }, we have that
X

X

Pr[Xpi = Xqj = 1] =

Pr[β(p) = β(q) = κ]Pr[Xpi = Xqj = 1 β(p) = β(q) = κ]

(i,j)∈Hκ2 :i6=j

(i,j)∈Hκ ,i6=j

≤ Pr[β(p) = β(q) = κ]

X

|x∗pk − x∗qk |/|Hκ |

k∈Hκ

max{x∗pk , x∗qk }/|Hκ |

.

Thus, we obtain that
X

2rκ+λ−1

Pr[Xpi = Xqj = 1]

(i,j)∈Hκ2 :i6=j

P
∗
∗
i∈Hκ |xpi − xqi |/|Hκ |
≤ 2r
Pr[β(p) = β(q) = κ] P
∗
∗
i∈Hκ max{xpi , xqi }/|Hκ |
P
∗
∗
i∈Hκ |xpi − xqi |
P
≤ 2rκ+λ−1 Pr[β(p) = k]
∗
i∈Hκ xpi
X
X
x∗pi )
= 2rκ+λ−1
|x∗pi − x∗qi | (∵ Pr[β(p) = κ] =
κ+λ−1

i∈Hκ

=2

X

i∈Hκ

rκ+λ−1 |x∗pi − x∗qi | = 2

i∈Hκ

X

u(λ, i)|x∗pi − x∗qi |.

i∈Hκ

Then we have inequality (4.1) for this case. From inequality (4.1), we have the desired result:

E


X

X

(`i + `j )Xpi Xqj  ≤ 2

κ∈[κmax ] (i,j)∈Hκ2 :i6=j

X

u(λ, i)|x∗pi − x∗qi |.

i∈H

Next, to show Lemma 6, we first describe Lemma 4 and Theorem 1. Lemma 4 implies that the
probability that non-hub p is classified into Nκ and non-hub q is classified into Nκ0 by Algorithm 1
P
P
N W where y N W is a north-west corner rule solution of the subproblem
is bounded by i∈Hκ j∈H 0 ypiqj
κ
that is equivalent to a Hitchcock transportation problem (HTP). The detail is omitted here (see
Appendix).
Lemma 4. Let X be a vector of random variables obtained by the proposed algorithm, let (x, y) be
a feasible solution of LRP and let y N W be a solution of HTP (defined in Appendix). obtained by
north-west corner rule. For any pair of {κ, κ0 } ∈ [κmax ], κ 6= κ0 and any pair of (p, q) ∈ N 2 (p 6= q),

14

Algorithm 3: Construct y ∗ from x∗
Require: An optimal solution x∗ of LRP.
Ensure: Vectors y ∗
1: for (p, q) ∈ N 2 , p 6= q do
∗
2:
Initialize ypiqj
= 0 (∀(i, j) ∈ H 2 )
∗
3:
Set ypiqj to min{x∗pi , x∗qi } (∀i ∈ H)
4:
for i = 1, 2, 3, . . . , h do
5:
j←1 P
∗
6:
while k∈H ypiqk
< x∗pi do
P
P
∗
∗
∗ }
7:
Set ypiqj
to min{x∗qj − k∈H ypkqj
, x∗pi − k∈H ypiqk
8:
j ←j+1
9:
end while
10:
end for
11: end for
12: return y ∗

we have the following inequality:
X X

E[Xpi Xqj ] ≤

i∈Hκ j∈Hκ0

X X

NW
ypiqj
.

i∈Hκ j∈Hκ0

The proof is omitted here (see Appendix).
Next we describe well-known relation between a north-west corner rule solution of a Hitchcock
transportation problem and the Monge property.
Theorem 1. If a given cost matrix C = (cij ) is a Monge matrix, then the north-west corner rule
solution y N W gives an optimal solution of all the Hitchcock transportation problems.
Proof is omitted here (see for example [6, 9]).
Next we consider that we construct a vector y ∗ from the optimal solution x∗ by Algorithm 3.
A vector y ∗ is optimal to our subproblem HTP. Note that we need Algorithm 3 only for approximation analysis and we don’t use it to obtain an approximate solution. Then we have the following
lemma.
Lemma 5. Let x∗ be an optimal solution of LRP and let y ∗ be a vector obtained by Algorithm 3.
For any pair of (p, q) ∈ N 2 (p 6= q) , we have the following inequality:
X

∗
(`i + `j )ypiqj
=

(i,j)∈H 2 :i6=j

X
i∈H

Proof is omitted here (see Appendix).
Now we are ready to prove the following lemma.

15

`i |x∗pi − x∗qi |.

Lemma 6. Let X be a vector of random variables obtained by the proposed algorithm. Let x∗ be
an optimal solution of LRP, and let y ∗ be vectors obtained from the optimal solution x∗ of LRP by
Algorithm 3. For any distinct pair of non-hubs (p, q) ∈ N 2 (p 6= q), any real number r > 1, and
any real number λ ∈ [0, 1), we have the following inequality :



X

E

X X

(`i + `j )Xpi Xqj  ≤

{κ,κ0 }∈[κmax ]:κ6=κ0 i∈Hκ j∈Hκ0

r2 + 1 X
u(λ, i)|x∗pi − x∗qi |.
r2 − 1
i∈H

Proof. First, we prove the following inequality for any pair of integers {κ, κ0 } ∈ [κmax ] (κ 6= κ0 ) and
any pair of non-hubs (p, q) ∈ N 2 (p 6= q) :

E


X X

(`i + `j )Xpi Xqj  ≤

r2 + 1 X X
∗
(u(λ, i) + u(λ, j))ypiqj
.
r2 − 1
i∈Hκ j∈Hκ0

i∈Hκ j∈Hκ0

(Case i) κ, κ0 ∈ {1, 2, . . . , κmax } (κ 6= κ0 )
In this case, we have the following inequalities from the definition of u(λ, i) (i ∈ H).

E


X X

(`i + `j )Xpi Xqj 

i∈Hκ j∈Hκ0

≤

X X

(u(λ, i) + u(λ, j))E[Xpi Xqj ]

i∈Hκ j∈Hκ0

=

X X

0

(rκ+λ−1 + rκ +λ−1 )E[Xpi Xqj ]

i∈Hκ j∈Hκ0
0

X X

= (rκ+λ−1 + rκ +λ−1 )

i∈Hκ j∈Hκ0

16

E[Xpi Xqj ].

(5.1)

Using Lemma 4, Lemma 2, and Theorem 1, we have the following inequalities.
0

X X

(rκ+λ−1 + rκ +λ−1 )

E[Xpi Xqj ]

(1)

i∈Hκ j∈Hκ0
0

≤ (rκ+λ−1 + rκ +λ−1 )

X X

NW
ypiqj
(∵ Lemma 4)

i∈Hκ j∈Hκ0

=

X X

NW
(u(λ, i) + u(λ, j))ypiqj

i∈Hκ j∈Hκ0

≤

r2 + 1 X X
NW
ĉij ypiqj
(∵ Lemma 2)
r2 − 1
i∈Hκ j∈Hκ0

≤

r2 + 1 X X
∗
ĉij ypiqj
(∵ Ĉ is a Monge matrix and Theorem 1.)
r2 − 1
i∈Hκ j∈Hκ0

≤

r2

+1 X X
∗
(u(λ, i) + u(λ, j))ypiqj
r2 − 1
i∈Hκ j∈Hκ0

Then we obtained inequality (5.1) for this case.
(Case ii) κ = 0 or κ0 = 0
0
We can show inequality (5.1) for this case by substituting rκ+λ−1 + rκ +λ−1 in (Case i) by either
0
rκ+λ−1 or rκ +λ−1 .
Then we obtain that


X
X X
(`i + `j )Xpi Xqj 
E
{κ,κ0 }∈[κmax ]:κ6=κ0 i∈Hκ j∈Hκ0

≤
≤

=

r2 + 1
r2 − 1
r2 + 1
r2 − 1

X

X X

∗
(u(λ, i) + u(λ, j))ypiqj
(∵ inequality (5.1))

{κ,κ0 }∈[κmax ]:κ6=κ0 i∈Hκ j∈Hκ0

X

∗
(u(λ, i) + u(λ, j))ypiqj
.

(i,j)∈H 2 :i6=j

r2 + 1 X
u(λ, i)|x∗pi − x∗qj |. (∵ Lemma 5 for u(λ, i) instead of `i )
r2 − 1
i∈H

Now, we are ready to show our main theorem.


r2 +1
r−1
2
+
Theorem 2. The proposed algorithm is min{ log
|r > 1}(≈ 5.2809 at r ≈ 1.91065)–
2
r
r −1
approximation algorithm for star-star hub-and-spoke network design problems and star-metric labeling problems.
Proof. Let X be a vector of random variables obtained by the proposed algorithm and let (x∗ , y ∗ )

17

be an optimal solution of LRP. For any real number λ ∈ [0, 1), we have that

E[Z] = E 






X

wpq 

(p,q)∈N 2 :p6=q

X

cpi Xpi +

i∈H

X

cqj Xqj +

=

(p,q)∈N 2 :p6=q

wpq 

(`i + `j )Xpi Xqj 

(i,j)∈H 2 :i6=j

j∈H


X

X




X

cpi x∗pi +

i∈H

X

cqj x∗qj + E 

X

X

(`i + `j )Xpi Xqj 

κ∈[κmax ] (i,j)∈Hκ2 :i6=j

j∈H




X

+E 

X X

(`i + `j )Xpi Xqj  (∵ Lemma 1)

{κ,κ0 }∈[κmax ]:κ6=κ0 i∈Hκ j∈Hκ0

≤

X
(p,q)∈N 2 :p6=q

=

X
(p,q)∈N 2 :p6=q


X
X
X
wpq 
cpi x∗pi +
cqj x∗qj + 2
u(λ, i)|x∗pi − x∗qi |
i∈h

j∈H

i∈H

!
r2 + 1 X
+ 2
u(λ, k)|x∗pk − x∗qk | (∵ Lemma 3 and Lemma 6)
r −1
k∈H



X
2+1
X
X
r
wpq 
cpi x∗pi +
cqj x∗qj + 2 + 2
u(λ, k)|x∗pk − x∗qk |
r −1
i∈H

j∈H

(6.1)

k∈H

where Z denotes the objective value of a solution obtained by the proposed algorithm. Let Λ ∈ [0, 1)
be a uniform random variable. The expected value of u(Λ, k) for all k ∈ H and for all r > 1 is
R1
r−1
E[u(Λ, k)] = 0 rΛ `k dΛ = log
r `k .
Thus, from the above discussion and inequality (6.1) which holds for any Λ ∈ [0, 1), we have
that



X
2
X
X
X
r +1
E[Z] ≤
wpq 
cpi x∗pi +
cqj x∗qj + 2 + 2
E[u(Λ, k)]|x∗pk − x∗qk |.
r
−
1
j∈H
i∈h
k∈H
(p,q)∈N 2 :p6=q



X
2+1
X
X
X
r
−
1
r
=
wpq 
cpi x∗pi +
cqj x∗qj +
2+ 2
`k |x∗pk − x∗qk |.
log
r
r
−
1
j∈H
i∈h
k∈H
(p,q)∈N 2 :p6=q




2
r−1
r +1
= min
2+ 2
|r > 1 (optimal value of LRP)
log r
r −1




r−1
r2 + 1
≤ min
2+ 2
|r > 1 (optimal value of the original problem SHP).
log r
r −1


r−1
r2 +1
Note that when r > 1, f (r) = log
2
+
is minimized at r∗ ≈ 1.91065 and we get f (r∗ ) ≈
2
r
r −1
5.2809. Then we obtain the desired result.

18

5

Conclusion

In this paper, we have studied hub-and-spoke network design problems, motivated by the application
to achieve efficient transportation systems. we considered the case where the set of hubs forms a
star, and introduced a star-star hub-and-spoke network design problem and star-metric labeling
problem. The star-metric labeling
includesothe uniform labeling problem which is still
n
problem

r−1
r2 +1
NP-hard. We proposed min log r 2 + r2 −1 |r > 1 (≈ 5.2809 at r ≈ 1.91065)–approximation
algorithm for star-star hub-and-spoke network design problems and star-metric labeling problems.
Our algorithms solve a linear relaxation problem and apply dependent rounding procedures.

Appendix
Hitchcock Transportation Problems and North-West Corner Rule
A Hitchcock transportation problem is defined on a complete bipartite graph consists of a set of
supply points A = {1, 2, . . . , I} and a set of demand points B = {1, 2, . . . , J}. Given a pair of nonP
P
negative vectors (a, b) ∈ RI × RJ satisfying Ii=1 ai = Jj=1 bj and an I × J cost matrix C = (cij ),
a Hitchcock transportation problem is formulated as follows:

HTP(a, b, C) :

min.

I X
J
X

cij yij

i=1 j=1

s. t.

J
X

yij = ai

(i ∈ {1, 2, . . . , I}),

yij = bj

(j ∈ {1, 2, . . . , J}),

j=1
I
X
i=1

yij ≥ 0

(∀(i, j) ∈ {1, 2, . . . , I} × {1, 2, . . . , J}),

where yij denotes the amount of flow from a supply point i ∈ A to a demand point j ∈ B.
We describe north-west corner rule in Algorithm NWCR, which finds a feasible solution of
Hitchcock transportation problem HTP(a, b, C). It is easy to see that the north-west corner rule
solution Y = (yij ) satisfies the equalities that
0

0

j
i X
X
i=1 j=1

yij = min


i0
X


i=1


j0

X
ai ,
bj
(∀(i0 , j 0 ) ∈ {1, 2, . . . , I} × {1, 2, . . . , J}).

j=1

Since the coefficient matrix of the above equality system is nonsingular, the north-west corner rule
solution is a unique solution of the above equality system. Thus, the above system of equalities has
a unique solution which is feasible to HTP(a, b, C).
19

1

Algorithm NWCR
Step 1: Set all the elements of matrix Y to 0 and set the target element yij to y11 (top-left
corner).
Step 2: Allocate a maximum possible amount of transshipment to the target element
without making the row or column total of the matrix Y exceed the supply or demand
respectively.
Step 3: If the target element is yIJ (the south-east corner element), then stop.
Step 4: Denote the target element by yij . If the sum total of jth column of Y is equal to bj , set
the target element to yij+1 . Else (the sum total of Y of ith row is equal to ai ),
set the target element to yi+1j . Go to Step 2.

Next we show that the subproblem of our original problem can be written as a Hitchcock
transportation problem. Let (x, y) be a feasible solution of linear relaxation problem. For any
p ∈ N , xp denotes a subvector of x defined by (xp1 , xp2 , . . . , xph ). When we fix variables x in LRP
to x and given a pair of (p, q) ∈ N 2 (p 6= q), we can decompose the obtained problem into Hitchcock
transportation problems {HTP(xp , xq , Ĉ(= ĉij )) : (p, q) ∈ N 2 } where
HTP(xp , xq , Ĉ):

min.

XX

ĉij ypiqj

i∈H j∈H

s. t.

X

ypiqj = xpi

(∀i ∈ H),

ypiqj = xqj

(∀j ∈ H),

j∈H

X
i∈H

ypiqj ≥ 0

(∀(i, j) ∈ H 2 ).

Monge Property
We give the definition of a Monge matrix. A comprehensive research on the Monge property
appears in a recent survey [9]. Matrices with this property arise quite often in practical applications,
especially in geometric settings.
Definition 2. An m × n matrix C is a Monge matrix if and only if C satisfies the so-called Monge
property
cij + ci0 j 0 ≤ cij 0 + ci0 j
for all 1 ≤ i < i0 ≤ m, 1 ≤ j < j 0 ≤ n.
Note that the north-west corner rule produces an optimal solution of Hitchcock transportation problems if the cost matrix is a Monge matrix, so we can obtain an optimal solution of HTP(xp , xq , Ĉ)
by north-west corner rule [6].
20

Proof of Lemma 4
Let X be a vector of random variables obtained by the proposed algorithm, and let (x, y) be a
feasible solution of LRP. For any pair of {κ, κ0 } ∈ [κmax ] (κ 6= κ0 ) and any pair of (p, q) ∈ N 2 (p 6= q),
then we have

!
X X
X
X
E[Xpi Xqj ] ≤
xpi 
xqj 
i∈Hκ k∈Hκ0

i∈Hκ

X

= max{

xpi ,

i∈Hκ

≤ min{

X

X

˙
xpj }min{

j∈Hκ0

X

xpi ,

i∈Hκ

j∈Hκ0

X

xpi ,

i∈Hκ

xpj }(∵

X

X

xpj }

j∈Hκ0

xpi = 1).

(6.21)

i∈H

j∈Hκ0

For any pair of {κ, κ0 } ∈ [κmax ] (κ 6= κ0 ) and any pair of (p, q) ∈ N 2 (p 6= q), we have the following
Hitchcock transportation problems :

HTP(xp , xq , Ĉ):

X X

min.

ĉij ypiqj

i∈Hκ j∈Hκ0

X

s. t.

ypiqj = xpi

(∀i ∈ Hκ ),

j∈Hκ0

X

ypiqj = xqj

(∀j ∈ Hκ0 ),

i∈Hκ

ypiqj ≥ 0

(∀(i, j) ∈ Hκ × Hκ0 ).

N W ) satisfies the equalities that
We see that the north-west corner rule solution y N W = (ypiqj

X X

NW
= min
ypiqj


X


i∈Hκ j∈Hκ0

i∈Hκ

xpi ,

X
j∈Hκ0

xqj




(∀{κ, κ0 } ∈ [κmax ], κ 6= κ0 ).



From the equalities and inequality (6.21), we have
X X

E[Xpi Xqj ] ≤

i∈Hκ k∈Hκ0

X X
i∈Hκ j∈Hκ0

Thus, we have the desired result.

21

NW
ypiqj
.

Proof of Lemma 5
Let y ∗ be the vector obtained from an optimal solution of LRP x∗ by Algorithm 3. Given any
distinct pair of non-hubs (p, q) ∈ N 2 (p 6= q), we can see that
X

∗
ypiqj
= x∗pi (∀i ∈ H),

j∈H

X

∗
ypiqj
= x∗qj (∀j ∈ H),

i∈H

X

ypiqj = min{0, xpi − xqi } (∀i ∈ H),

j∈H:j6=i

X

ypiqj = min{0, xqj − xpj } (∀j ∈ H).

i∈H:i6=j

Thus we have
X
(i,j)∈H 2 :i6=j

=
=

X

`i

X

∗
(`i + `j )ypiqj
=

(i,j)∈H 2 :i6=j

X

∗
ypiqj
+

i∈H

j∈H:j6=i

X

`i min{0, x∗pi

X

`j

j∈H

−

x∗qi }

−

x∗qi }

+

i∈H

=

X

=

X

X

∗
`j ypiqj

(i,j)∈H 2 :i6=j
∗
ypiqj

i∈H:j6=i

X

`j min{0, x∗qj − x∗pj }

j∈H

`i min{0, x∗pi

i∈H

X

∗
`i ypiqj
+

+

X

`i min{0, x∗qi − x∗pi }

i∈H

`i |x∗pi

−

x∗qi |.

i∈H

Then we have the desired result.

References
[1] S. A. Alumur and B. Y. Kara. “Network hub location problems: The state of the art”. European
Journal of Operational Research, 190:1–21, 2008.
[2] R. Ando and T. Matsui. “Algorithm for single allocation problem on hub-and-spoke networks
in 2-dimensional plane”. Lecture Notes in Computer Science, 7074:474–483, 2011.

22

𝒙∗𝑞

𝒙∗𝑝

0.2 1 0.2 1 0.3
0.1
0.3
0.3
0.3
2
2
𝑝

0.4 3
0.1 4

0.1
0.3
0.1
0

3 0.1

𝑞

4 0.3

0.2

Figure 9: Hitchcock transportation problems with a depot 0

[3] M. Andrews, M. T. Hajiaghayi, H. Karloff, and A. Moitra. “Capacitated metric labeling”.
In Proceedings of the Twenty-Second Annual ACM-SIAM symposium on Discrete Algorithms,
976–995, 2011.
[4] A. Archer, J. charoenphol, C. Harrelson, R. Krauthgamer, K. Talwar, and É. Tardos. “Approximate classification via earthmover metrics”. In Proceedings of the Fifteenth Annual ACM-SIAM
symposium on Discrete algorithms, 1079–1087, 2004.
[5] Y. Bartal. “On approximating arbitrary metrices by tree metrics”. In Proceedings of the
Thirtieth Annual ACM Symposium on Theory of Computing, 161–168, 1998.
[6] W. Bein, P. Brucker, K. Park, and K. Pathak. “A Monge property for the d-dimensional
transportation problem”. Discrete Applied Mathematics, 58:97–109, 1995.
[7] Y. Boykov, O. Veksler, and R. Zabih. “Markov random fields with efficient approximations”.
In Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 648–655, 1998.
[8] Y. Boykov, O. Veksler, and R. Zabih. “Fast approximate energy minimization via graph cuts”.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 23:1222–1239, 2001.
[9] R. E. Burkard, B. Klinz, and R. Rudolf. “Perspectives of Monge properties in optimization”.
Discrete Applied Mathematics, 70:95–161, 1996.

23

[10] H. Calik, S. A. Alumur, B. Y. Kara, and O. E. Karasan. “A tabu-search based heuristic for
the hub covering problem over incomplete hubnetworks”. Computers and Operations Research,
36:3088–3096, 2009.
[11] G. Călinescu, H. Karloff, and Y. Rabani. “Approximation algorithms for the 0-extension
problem”. SIAM Journal on Computing, 34:358–372, 2005.
[12] J. F. Campbell. “A survey of network hub location”. Studies in Locational Analysis, 6:31–47,
1994.
[13] J. F. Campbell, A. T. Ernst, and M. Krishnamoorthy. “Hub arc location problems: Part I:
Introduction and results”. Management Science, 51:1540–1555, 2005.
[14] J. F. Campbell, A. T. Ernst, and M. Krishnamoorthy. “Hub arc location problems: Part II:
Formulations and optimal algorithms”. Management Science, 51:1556–1571, 2005.
[15] J. F. Campbell and M. E. O’Kelly. “Twenty-five years of hub location research”. Transportation
Science, 46:153–169, 2012.
[16] C. Chekuri, S. Khanna, J. Naor, and L. Zosin. “A linear programming formulation and approximation algorithms for the metric labeling problem”. SIAM Journal on Discrete Mathematics,
18:608–625, 2004.
[17] J. Chuzhoy and J. Naor. “The hardness of metric labeling”. SIAM Journal on Computing,
36:1376–1386, 2007.
[18] I. Contreras. “Hub location problems”. In G. Laporte, S. Nickel, and F. S. da Gama, (eds),
Location Science, 311–344. Springer, Cham, 2015.
[19] I. Contreras, E. Fernández, and A. Marı́n. “Tight bounds from a path based formulation for
the tree of hub location problem”. Computers and Operations Research, 36:3117–3127, 2009.
[20] I. Contreras, E. Fernández, and A. Marı́n. “The tree of hubs location problem”. European
Journal of Operational Research, 202:390–400, 2010.
[21] T. Contreras, M. Tanash, and N. Vidyarthi. “Exact and heuristic approaches for the cycle hub
location problem”. Annals of Operations Research, 258:655–677, 2017.

24

[22] E. M. de Sá, I. Contreras, J. F. Cordeau, R.S. de Camargo, and G. de Miranda. “The hub line
location problem”. Transportation Science, 49:500–518, 2015.
[23] E. M. de Sá, R. S. de Camargo, and G. de Miranda. “An improved Benders decomposition
algorithm for the tree of hubs location problem”. European Journal of Operational Research,
226:185–202, 2013.
[24] J. Fakcharoenphol, S. Rao, and K. Talwar. “A tight bound on approximating arbitrary metrics
by tree metrics”. Journal of Computer and System Sciences, 60:485–497, 2004.
[25] D. M. Greigand, B. T. Porteous, and A. H. Seheult. “Exact maximum a posteriori estimation
for binary images”. Journal of the Royal Statistical Society. Series B, 51:271–279, 1989.
[26] A. Gupta and É. Tardos. “A constant factor approximation algorithm for a class of classification problems”. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of
Computing, 652–658, 2000.
[27] M. Iwasa, H. Saito, and T. Matsui. “Approximation algorithms for the single allocation problem
in hub-and-spoke networks and related metric labeling problems”. Discrete Applied Mathematics, 157:2078–2088, 2009.
[28] J. G. Kim and D. W. Tcha. “Optimal design of a two-level hierarchical network with tree-star
configuration”. Computers and Industrial Engineering, 22:273–281, 1992.
[29] J. Kleinberg and E. Tardos. “Approximation algorithms for classification problems with pairwise relationships”. Journal of ACM, 49:616–639, 2002.
[30] J. G. Klincewicz. “Hub location in backbone/tributary network design: a review”. Location
Science, 6:307–335, 1998.
[31] G. Konjevod, R. Ravi, and F. S. Salman. “On approximating planar metrics by tree metrics”.
Information Processing Letters, 80:213–219, 2001.
[32] M. P. Kumar. “Rounding-based moves for metric labeling”. In Advances in Neural Information
Processing Systems, 109–117, 2014.
[33] Y. Kuroki and T. Matsui. “Approximation algorithm for cycle-star hub network design problems and cycle-metric labeling problems”. In Proceedings of the 11th International Conference
and Workshops on Algorithms and Computation, 397–408, 2017.
25

[34] M. Labbé and H. Yaman. “Solving the hub location problem in a star-star network”. Networks,
51:19–33, 2008.
[35] M. Li, A. Shekhovtsov, and D. Huber. “Complexity of discrete energy minimization problems”.
In Proceedings of Computer Vision – ECCV 2016, 834–852, 2016.
[36] M. E. O’Kelly. “A quadratic integer program for the location of interacting hub facilities”.
European Journal of Operational Research, 32:393–404, 1987.
[37] M. E. O’Kelly and H. J. Miller. “The hub network design problem: A review and synthesis”.
Journal of Transport Geography, 2:31–40, 1994.
[38] S. Sedehzadeh, R. Tavakkoli-Moghaddam, A. Baboli, and M. Mohammadi. “Optimization of
a multi-modal tree hub location network with transportation energy consumption: A fuzzy
approach”. Journal of Intelligent & Fuzzy Systems, 30:43–60, 2016.
[39] J. Sohn and S. Park. “A linear program for the two-hub location problem”. European Journal
of Operational Research, 100:617–622, 1997.
[40] J. Sohn and S. Park. “The single allocation problem in the interacting three-hub network”.
Networks, 35:17–25, 2000.
[41] R. Tavakkoli-Moghaddam and S. Sedehzadeh. “A multi-objective imperialist competitive algorithm to solve a new multi-modal tree hub location problem”. In Proceedings of Sixth World
Congress on Nature and Biologically Inspired Computing, 202–207, 2014.
[42] H. Yaman. “Star p-hub median problem with modular arc capacities”. Computers and Operations Research, 35:3009–3019, 2008.
[43] H. Yaman and S. Elloumi. “Star p-hub center problem and star p-hub median problem with
bounded path lengths”. Computers and Operations Research, 39:2725–2732, 2012.

26

