Location problems in partial $k$-trees

The minsum and minmax problems are two classical problems in location theory. We are given a set $S$ of points $\{s_1, s_2, \ldots, s_n\}$ with distance $d(s_i,s_j)$ between $s_i$ and $s_j$. The p-minsum (p-minmax) problem is to find a set $H \subseteq S$, $\vert H\vert=p$ which minimizes $\sum_{i=1}^{n} w_id(s_i,H)$ ( $max\{d(s_i,H), \forall s_i \in S$) where $d(s_i,H)$ is the minimum of $d(s_i,s)$ $\forall s \in H$ and $w_i$ is the weight associated with $s_i$. The p-minsum (p-minmax) problem is also known as the p-median (p-center) problem. The settings in which these problems are formulated are also important. (i) The problems are defined in Euclidean space or in graphs, (ii) The problems are defined on graph networks where the potential set of facility locations are the set of vertices, or the set of edges of the network. (iii) The weight of a client could be positive or negative. The $p$-center and $p$-median problems are known to be NP-hard even on general planar geometric networks. As a matter of fact, almost all variants of the location problem are known to be NP-hard problems (see [4] for a survey).

The research activities on locating facilities in trees are intense (see [4] for some of the latest references). We have achieved significant results for location problems in trees. Some of the important results are listed below:

1. Solved (for the first time) the $p$-median problem (for fixed $p$) in trees in subquadratic time [6].
2. Improved most of the $p$-center problems for cactus networks [12].
3. Solved (for the first time) the weighted $p$-center problem (for fixed $p$) in trees in optimal time [20].
4. Designed optimal algorithms for the path/tree-shaped facility location problems in trees [19].

One of the most important properties of trees, which is useful in designing efficient algorithms, is the existence of a 1-separator between any two disjoint subtrees. A 1-separator between two disjoint subtrees $T_i,T_j$ is a vertex $v$ such that every simple path connecting a vertex in $T_i$ with a vertex in $T_j$ must contain $v$. This property gives a very nice way to decompose a tree network, i.e., a centroid decomposition [45], spine tree decomposition [5].

Partial $k$-trees are a more general class of networks for which similar property is available. Such property is represented by a tree decomposition with treewidth $k$, which can be found in linear time for fixed $k$ [23]. Given a tree decomposition $TD(G)$ of a partial $k$-tree $G$, there is a $k$-separator between any two subnetworks represented by two disjoint subtrees of $TD(G)$. The class of partial k-trees includes trees (k=1), series-parallel graphs (k=2), Halin graphs (k=3), and k-terminal graphs. This tree decomposition provides a way to decompose a partial $k$-tree network. However, not much work has been done to extend the techniques that are used to efficiently solve facility location problems on tree networks, to partial $k$-trees (except dynamic programming).

Recently, in [12] we have developed a two-level tree decomposition data structure over a partial $k$-tree, which can be efficiently built and answer the service cost of a given facility set in a sub-linear time. Also, similar to the succinct representation of the inter-vertex distance matrix of a tree network proposed by Megiddo et al. [45], a sub-quadratic representation of the inter-vertex distance matrix of a partial $k$-tree is built in [12].

Since the late 1980s, parametric search, the optimization technique proposed by Megiddo [44], has become a powerful and ingenious tool for efficiently solving a variety of optimization problems. One approach of applying parametric search technique on the $p$-center problem on a network is to explicitly or implicitly build the candidate set which is guaranteed to contain the optimal value, to find an efficient solution for the corresponding decision problem, and then to binary search the optimal value on the candidate set. In this approach, the first step and the last step have been well studied. However, no more work has been done on the second step since 1988 [52] when the underlying network is not a tree, i.e., partial $k$-trees and general networks.

Recently, we explored the relationship between the feasibility test for the $p$-center problem in a general network and the union of $n$ axis-parallel hypercubes in $p$-dimensional space, which can be solved in a better time complexity. It implies the $p$-center problem in a general network can be improved.