Network Facility Location Problems

Network facility location problems investigate where to physically locate a set of facilities (i.e., resources, servers) in the underlying network to satisfy some set of demands (i.e., customers, clients). The demand set consists of all points of the network that require services, and the supply set consists of all candidate locations of facilities. The goal is to place these facilities in the supply set such that the quality of service provided is optimized. In general, the quality of service is measured by some objective function, subject to a set of constraints. There are many different objective functions of possible interests, among which the minimization of maximum distance from a demand point to its closest facility is one of the most studied. The corresponding problem is referred to in the literature as the center problem.

The network center location problem has been extensively studied in the literature. In [37], $p$ -center problems in general networks have been shown to be $NP$ -hard (even when the network is a planar network of maximum vertex degree four). However, center problems are no longer $NP$ -hard when either $p$ is constant [37,50], or the underlying network is restricted to be a specialized network, such as a tree [35,37], a cactus [8], or a partial $k$ -tree (fixed $k$ ) [27]. We have achieved significant results for center location problems in general networks as well as specialized networks, such as tree networks, cactus networks, and partial $k$ -tree networks (fixed $k$ ). Our achievements are summarized in Table 2.

Table 2: Results for the network $p$ -center problems

Underlying network	Problem	Previous result	Our result
A tree $T$	Weighted $V(T)/V(T)/p$ (fixed $p$ )	$O(n\log{n})$ [35]	$O(n)$ [7,49]
	Weighted $A(T)/V(T)/p$ (fixed $p$ )	$O(n\log{n})$ [35]	$O(n)$ [7,49]
A cactus $G$	Unweighted $V(G)/A(G)/1$	$-$	$O(n)$ [6]
	Unweighted $A(G)/A(G)/1$	$-$	$O(n)$ [6]
	Weighted $V(G)/V(G)/1$	$-$	$O(n\log{n})$ [8]
	Weighted $A(G)/V(G)/1$	$-$	$O(n\log{n})$ [8]
	Weighted $A(G)/V(G)/2$	$-$	$O(n\log^3n)$ [8]
	Obnoxious $A(G)/V(G)/1$	$-$	$O(n\log^3n)$ [8]
	Unweighted $V(G)/A(G)/p$	$-$	$O(n^2)$ [6]
	Unweighted $A(G)/A(G)/p$	$-$	$O(n^2\log^2n)$ [6]
	Weighted $V(G)/V(G)/p$	$-$	$O(n\log^2{n})$ [6]
	Weighted $A(G)/V(G)/p$	$-$	$O(n^2)$ [6]
A partial $k$ -tree $G$	Weighted $V(G)/V(G)/1$	$-$	$O(n\log{^kn})$ [14]
(fixed $k$ )	Weighted $V(G)/V(G)/p$ (fixed p)	$O(n^{k+2})$ [27]	$O(n^p\log{^{2k}n})$ [14]
	Weighted $A(G)/V(G)/p$	$-$	$O(p^2n^{2k+3}\log{n})$ [14]
A general network $G$	Weighted $A(G)/V(G)/p$	$O(m^pn^p\alpha(n)\log{n})$ $^1$ [50]	$O(m^pn^{p/2}2^{\log^*{n}}\log{n})$ [14]

$1:$ $\alpha(n)$ is the inverse Ackermann function.

In Table 2, we use a 3-position scheme of Handler and Mirchandani [31], that is, $\mathcal{X}(G)/\mathcal{D}(G)/p$ (supply set/demand set/number of facilities), to label different problems. Mainly, four cases of the center problem, where the demand set $\mathcal{D}(G)$ and the supply set $\mathcal{X}(G)$ are either subsets of the vertex set $V(G)$ or subsets of the point set $A(G)$ , are considered. When the demand set is a subset of the vertex set, its weighted version of the problem is also considered where each demand vertex is associated with a non-negative weight.

Moreover, we also have some achievements on variations of the network center location problem in an edge-weighted tree network, including conditional extensive facility location problems (CELP), continuous $p$ -edge-partition problems (CEPP), and conditional covering problems (CCP). Our results are summarized in Table 3.

Table 3: Some variations of network center location problems in a tree network

Problem	Previous result	Our result
CELP	$O(n\log{n})$ [51]	$O(n)$ [13]
Max-Min CEPP	$O(n^2)$ [40]	$O(n\log{^2n})$ [5]
Min-Max CEPP	$O(n^2)$ [40]	$O(nh_T\log{n})$ $^1$ [5]
CCP in a path	$O(n^2)$ [32]	$O(n\log{n})$ [49]
CCP in an extended-star	$O(n^2)$ [32]	$O(n^{1.5}\log{n})$ [49]
CCP in a tree	$O(n^4)$ [33]	$O(n^3\log{n})$ [49]

$1:$ $h_T$ is the height of the underlying tree network.