Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously

A typical clustering problem takes as input a set of $n$ objects in a metric space $(V,d)$, and seeks a partition of these objects into $k$ clusters $V_1,\mathrm{\dots },V_k$, so as to optimize some objective function. For example, we might try to place $k$ facilities onto the nodes of an edge-weighted graph with node set $V$, and then assign each remaining node to some facility. To model the cost of serving these nodes from their facility, one can use the cost of a minimum-weight spanning tree $T_i$ on the subgraph induced by them. For $i=1,\mathrm{\dots },k$, let $w(T_i)={\sum }_{e\in E(T_i)}w(e)$ be the weight of tree $T_i$. Historically, these kinds of problems have been studied for two different objectives. On the one hand, in the Min-Sum Tree Cover problem one might want to find $k$ trees $T_1,\mathrm{\dots },T_k$ to cover all nodes in $V$, while minimizing the total length of the service network, i.e., the sum ${\sum }_{i\in [k]}w(T_i)$ of the weights of the spanning trees. On the other hand, it is desirable that each facility does not serve too large of a network, so we can instead minimize the weight ${\max }_{i\in [k]}w(T_i)$ of the heaviest tree, which leads to the Min-Max Tree Cover problem [10, 19].

Many fundamental clustering problems were studied under this min-sum objective and min-max objective. These objectives can equivalently be considered as that of minimizing the 1-norm, or the $\mathrm{\infty }$-norm, of the clustering. Examples include the $k$-median problem and the minimum-load $k$-facility location problem. These two problems are siblings in that they both deal with the assignment of points (or clients) to $k$ centers (or facilities), with the costs of connecting those points to respective centers. Each point $v$ is then assigned to one of these open centers, denoted as $c(v)$. The cost ${\text{cost}}_c$ for each center $c$, which also reflects the cost associated with each facility, is calculated as the sum of distances between the center and all the points allocated to it, i.e, ${\text{cost}}_c={\sum }_{v\in V:c(v)=c}d(v,c)$. In the $k$-median problem [14, 7, 21, 2], the objective is to minimize the ${\mathrm{\ell }}_1$-norm of ${\{{\text{cost}}_c\}}_c$, i.e., ${\sum }_c{\text{cost}}_c$, which represents the total cost of all clusters; whereas the minimum-load $k$-facility location problem [1] seeks to minimize the maximum load of an open facility, symbolised by the ${\mathrm{\ell }}_{\mathrm{\infty }}$-norm function of ${\{{\text{cost}}_c\}}_c$, i.e., ${\max }_c{\text{cost}}_c$.

There is a diverse array of cost functions that could be applicable to a variety of problem domains, and often, efficient algorithms are crafted to suit each specific objective. However, it is crucial to note that an optimal solution for one objective may not perform well for another. For instance, a solution for an instance of the Tree Cover that minimizes the ${\mathrm{\ell }}_1$-norm might be particularly inefficient when it comes to minimizing the ${\mathrm{\ell }}_{\mathrm{\infty }}$-norm, and vice versa (see examples in Figure 1(a) and Figure 1(b)). Therefore, one may wonder what the “generally optimal” solution would be for a given problem. Finding such a generally optimal solution is the task of the following problem:

Our focus in this paper is the all-norm clustering problem where the cost $w(V_i)$ of each cluster is the cost of a minimum-weight spanning tree on $V_i$ with respect to the metric $d$. We call this problem the All-Norm Tree Cover problem in line with the naming convention in the literature, and denote its instances by $(V,d,w,k)$. (Note that, for simplicity, we only consider ${\mathrm{\ell }}_p$-norms here. However, the proofs turn out to work for any norm which is monotone and symmetric, cf. Ibrahimpur and Swamy [16] for a detailed introduction to such norms.) Observe that the number $k$ of clusters is part of the input, i.e., it is not fixed.

The choice of the cost of a minimum-weight spanning tree might appear to be somewhat arbitrary here, but spanning trees are the key connectivity primitive in network design problems. Any constant-factor approximation for All-Norm Tree Cover will, for example, transfer to a constant-factor approximation for the all-norm version of the Multiple Traveling Salesperson Problem [5] where we ask to cover a metric space by $k$ cycles instead of trees. This use of spanning trees as a proxy for the traversal times of the clusters was a key ingredient for by Zheng et al. [24] to partition a floorplan into similar-size areas to be served by different robots.

Let us observe that solving the All-Norm Tree Cover problem is non-trivial, as a solution which is good for one objective (i.e., for one particular norm ${\mathrm{\ell }}_p$) may be bad for another objective (i.e., for another norm ${\mathrm{\ell }}_{p^{\prime }}$), and vice versa. For examples of this phenomenon, see Figure 1.

The All-Norm Tree Cover problem, alongside the related path cover and cycle cover problems, involves covering a specified set of nodes of a(n edge-weighted) graph with a limited number of subgraphs. These problems have attracted significant attention from the operations research and computer science communities due to their practical relevance in fields like logistics, network design, and data clustering. For instance, these problems are naturally applicable in scenarios such as vehicle routing, where the task involves designing optimal routes to service a set of customers with a finite number of vehicles. Different optimization objectives could be considered depending on the specific requirements. One could aim to minimize the maximum waiting time for any customer, an objective that is equivalent to the ${\mathrm{\ell }}_{\mathrm{\infty }}$-norm of the cost function associated with each vehicle. This ensures fairness, as it attempts to prevent any single customer from waiting excessively long. Alternatively, one could aim to minimize the total travel time or cost, which corresponds to the ${\mathrm{\ell }}_1$-norm of the cost function across all vehicles [6, 4]. This objective seeks overall efficiency, making it beneficial from an operational perspective as it reduces fuel consumption and allows for more customers to be serviced within the same time frame [11, 4, 10, 19]. Understanding these problems in an all-norm setting thus enables the development of routing strategies that are adaptable to different priorities, including customer satisfaction, operational efficiency, or a balance between the two. Given that minimum spanning trees provide constant-factor approximations to traveling salesperson tours [8], we explore the possibility of covering the nodes of a graph with $k$ trees.

In a scenario where each vehicle already has an assigned station, and the task is limited to the assignment of nodes to the vehicles, we are confronted with a variation of the All-Norm Tree Cover problem known as the All-Norm Tree Cover with Depots problem (also commonly referred to as the Rooted All-Norm Tree Cover problem), denoted by $(V,d,w,D)$ where $D\subseteq V$ is a set of depots [10]. These problems under all norms will be formally defined and addressed in the subsequent sections of this paper.

We set up some formal definitions. We will identify metric spaces and metrically edge-weighted graphs to allow for an easier treatment of connectedness, trees, and similar graph-theoretic objects. For any such graph $G$, we always keep in mind the underlying metric space $V$ induced by the shortest-path metric on $G$. We also assume that the metrics used are integral, for ease of presentation. Our results extend to rational metrics by rescaling the metric.

We here concern ourselves with tree covers of graphs, which are to be defined as follows:

Notice in particular that there is no expectation of disjointness for the trees. If disjointness is required, we may assign every node to exactly one of the trees currently containing it and recompute minimum-weight spanning trees for each of the resulting clusters. This increases the cluster weights by at most a factor of $2$ due to the gap between Steiner trees and minimum-weight spanning trees (see Lemma 9). For any connected subgraph $H$ of a graph $G$, we use $w(H)$ to denote the weight of a minimum-weight spanning tree in the subgraph $H$. It is important to note that this weight can differ from the sum of the weight of the edges of $H$. We then use the $p$-norm $(p\ge 1)$ as a measure of the quality of a tree cover. Specifically, the cost of a tree cover $\{T_1,\mathrm{\dots },T_k\}$ is defined as the $p$-norm of the corresponding tree weights, that is, $w_p={\left({\sum }_{i\in [k]}{\left(w(T_i)\right)}^p\right)}^{1/p}$.

There are two natural optimization questions for tree covers (and for tree covers with depots) which have been considered in the literature: The ${\mathrm{\ell }}_1$-Tree Cover problem, where the aim is to minimize the sum of the weights of the $k$ trees, and the ${\mathrm{\ell }}_{\mathrm{\infty }}$-Tree Cover problem in which the objective is to minimize the weight of the heaviest tree within the cover. The ${\mathrm{\ell }}_1$-Tree Cover problem admits a polynomial-time algorithm, regardless of the presence of depots; in contrast, the ${\mathrm{\ell }}_{\mathrm{\infty }}$-Tree Cover problem is $\mathrm{𝖠𝖯𝖷}$-hard, again regardless of whether depots are present or not.

We consider the interpolation between these two problems by allowing arbitrary ${\mathrm{\ell }}_p$ norms:

We will usually omit $k$ if it is clear from context. All of the ${\mathrm{\ell }}_p$-variants (except $p=1$) are $\mathrm{𝖭𝖯}$-hard, as the proof of hardness for the ${\mathrm{\ell }}_{\mathrm{\infty }}$-case works for all values of $p>1$ [23].

To distinguish the problem versions for a fixed norm $p$ from those for all $p$ simultaneously, we denote by $({\mathrm{\ell }}_p,k)$ (or $({\mathrm{\ell }}_p,D)$ for problems involving depots) the tree cover problem for a specific value of $p$. Meanwhile, we use $({\mathrm{\ell }}_{p\in [1,\mathrm{\infty })},k)$ (or $({\mathrm{\ell }}_{p\in [1,\mathrm{\infty })},D)$ when depots are involved) to represent the All-Norm Tree Cover problem that encompasses all values of $p\in [1,\mathrm{\infty })$. We omit naming the underlying metric space $(V,d)$, unless explicitly stated otherwise.

We will state a result about the relationship between the cost of minimum-weight Steiner trees and minimum-weight spanning trees, as we will harness this argument repeatedly:

First, to provide some some good intuition of the key techniques for the general case, we show in detail that the Tree Cover algorithm of Even et al. [10] gives a constant-factor approximation to the ${\mathrm{\ell }}_p$-tree cover problem without depots provided that it returns $k$ trees. Indeed, we show that the argument will work for all monotone symmetric norms. The original algorithm works as follows, for a given graph $G=(V,d)$:

1. 1.

   Guess an upper bound $R$ on the optimum value of the ${\mathrm{\ell }}_{\mathrm{\infty }}$-norm tree cover problem for instance $G$, where initially $R=1$.

2. 2.

   Remove all edges with weight larger than $R$ from $G$, and compute a minimum-weight spanning tree $T_i$ for each connected component of the resulting graph.

3. 3.

   Check that $\sum \lfloor \frac{w(T_i)+2R}{2R}\rfloor =k$; otherwise, reject $R$ and go to step $1$ with $R:=2R$.

4. 4.

   Call a spanning tree $T_i$ small if .

5. 5.

   Call a spanning tree $T_i$ large if $w(T_i)\ge 2R$. Decompose each such tree into edge-disjoint subtrees ${\tilde{T}}_j$ such that $2R\le w({\tilde{T}}_j)\le 4R$ for all but one residual ${\tilde{T}}_j$ in each component¹¹1 This can be done with a simple greedy procedure, cutting of subtrees of this weight. For the details of this algorithm, we refer to Even et al. [10]..

6. 6.

   Output the family of all small spanning trees, as well as all subtrees ${\tilde{T}}_j$ created in Footnote 1.

Even at al. show that this procedure will output at most $k$ trees if $OP{T}_{\mathrm{\infty }}\le R$, although they relax the condition in Item 3 to $\sum \lfloor \frac{w(T_i)+2R}{2R}\rfloor \le k$. For technical reasons, however, we need the equality in this spot. Since every tree has weight most $4R$, the algorithm evidently gives a $4$-approximation in the ${\mathrm{\ell }}_{\mathrm{\infty }}$-norm if the correct value of $R=OP{T}_{\mathrm{\infty },k}$ is guessed. Otherwise, one can use binary search to find, in polynomial time, the smallest $R$ for which one gets at most $k$ trees.

In general, however, we notice that this algorithm will sometimes compute fewer than $k$ trees, causing it to not return a good approximation for the other ${\mathrm{\ell }}_p$-norms, not even for the ${\mathrm{\ell }}_1$-norm (see Figure 3).

For this reason, we need the strengthened property in Item 3. Then, however, notice that such a value $R$ does not necessarily exist; for example, for the instance in Figure 3 this is the case. We will describe later how to avoid this issue of non-existence; for now, we assume that such a value $R$ exists and can be computed in polynomial time.

So suppose that the algorithm has returned $k$ trees $T_1,\mathrm{\dots },T_k$, where we simply remove some edges should the algorithm return fewer than $k$ trees. This removal only improves the objective value, so we will assume – without loss of generality – that the algorithm already returned $k$ trees. As a warm-up, we will start by considering only the case that $p=1$, i.e., we show that this algorithm computes a solution that is a good approximation for $({\mathrm{\ell }}_1,k)$ tree cover.

The algorithm for the All-Norm Tree Cover problem with depots is considerably more involved, in particular because the simple lower bound for the depot-less algorithm of assuming an even distribution of the total weight can no longer work: it might be necessary to have unbalanced cluster sizes, for instance if some depots are extremely far from all nodes.

Instead our algorithm constructs a $c$-approximately (here, c is a constant) strongly optimal solution by also maintaining some (implicit) evidence that the optimum solution contains large trees if it decides to create a large tree itself. More concretely we do the following:

1. 1.

   First, we partition the node set $V$ into layers $L_i$ such that all nodes in $L_i$ have distance between $2^{i-1}$ and $2^i$ to the depots.

2. 2.

   Then we consider separately the nodes in the odd and even layers; this implies that nodes in different layers have a large distance to each other. Computing separate solutions for these two subinstances loses at most a factor $2$ in the approximation factor due to Lemma 9.

3. 3.

   Next, we partition the nodes in each layer $L_i$ using the non-depot algorithm with $R=2^i$. This yields a collection of subtrees in $L_i$ such that the cost of connecting such a subtree to its nearest depot is in $\mathrm{\Theta }(2^i)$. This allows us to treat them basically identically, loosing only the constant in the $\mathrm{\Theta }$. Indeed, we can show explicitly that this prepartitioning into subtrees can be assumed to be present in an optimal solution, up to a constant factor increase in the weight of each tree. For the full reasoning refer to the full version on arXiv [18].

4. 4.

   To assign these trees to the depots, we iteratively maintain an estimate of the largest tree necessary in any solution as $2^i$. We then collect all trees of weight $\mathrm{\Theta }(2^i)$ and compute a maximum matching between them and the depots at distance $\mathrm{\Theta }(2^i)$ to them. All unmatched trees are then combined to form trees of weight $\mathrm{\Theta }(2^{i+1})$, and we update our estimate to $2^{i+1}$.

To analyse the output of this algorithm, it will suffice to show that the estimate was correct up to a constant factor. That is, if in round $i$ some trees (suppose $k_i$ trees) of weight $2^i$ were assigned, we will be able to prove that any tree-cover solution must also have some family of at most $k_i$ trees with total weight at least $k_i\cdot 2^i$.

From this we are then able to conclude $c$-approximate strong optimality for some value of . This is a rather large upper bound on the approximation factor, however, we conjecture that the actual constant achieved by the algorithm is much smaller. For the purposes of a clean presentation, we did not try to optimize the constant. The complete proof can be found in the full version on arXiv [18].

To complement our algorithmic results, we establish hardness results for all-norm tree cover problems and discuss on what kind of algorithmic improvements (to our algorithms) are potentially possible in light of these complexity results. Specifically, we show:

1. 1.

   For any $p\in (1,\mathrm{\infty }]$, problem ${\mathrm{\ell }}_p$-Tree Cover with Depots is weakly $\mathrm{𝖭𝖯}$-hard, even with only $2$ trees.

2. 2.

   For any $p\in (1,\mathrm{\infty }]$, problem ${\mathrm{\ell }}_p$-Tree Cover with Depots with $k$ trees is (strongly) $𝖶[1]$-hard parameterized by depot size $|D|$.

3. 3.

   For any $p\in (1,\mathrm{\infty }]$ there exists some $\epsilon >0$ such that ${\mathrm{\ell }}_p$-Tree Cover with Depots is $\mathrm{𝖭𝖯}$-hard to approximate within a factor under randomized reductions.

Results 1 and 2 were already essentially presented by Even et al. [10], but we restate them for completeness. Note that, given these complexity results, numerous otherwise desirable algorithmic outcomes become unattainable. For instance, there cannot be polynomial-time approximation schemes for ${\mathrm{\ell }}_p$-Tree Cover with Depots, nor can we expect fixed-parameter algorithms (parameterized by the number of depots) finding optimal solutions, unless established hardness hypotheses ($𝖯$$\ne$$\mathrm{𝖭𝖯}$, $\mathrm{𝖥𝖯𝖳}\ne 𝖶[\mathrm{𝟣}]$) fail. Further, the reduction of Item 1 yields bipartite graphs of tree-depth $3$, so parameterization by the structure of the graph supporting the input metric also appears out of reach.

The result in Item 3 follows by a direct gadget reduction from Max-Sat for $3$-ary linear equations modulo $2$ (MAX-E3LIN2), which was shown to be $\mathrm{𝖠𝖯𝖷}$-hard by Håstad [15]. We show that one can transform such equations into an instance of ${\mathrm{\ell }}_p$-Tree Cover with Depots where every unsatisfied equation will correspond roughly to a tree of above average weight. This allows us to recover approximately the maximum number of simultaneously satisfiable constraints of such systems of equations.

Formally, we reduce from $3R\{2,3\}L2$, a modification of MAX-E3LIN2 where every variable occurs in exactly 3 equations, and for which hardness of approximation was shown by Karpinski et al. [17]. From an instance of 3R{2,3}L2 we construct an instance of ${\mathrm{\ell }}_p$-Tree Cover with Depots by introducing gadgets for the variables and clauses:

• $\mathrm{■}$

  For every variable $x$, introduce three nodes $\widehat{x},x_0,$ and $x_1$, as well as edges $\widehat{x},x_i$ for $i=0,1$ with weight $3$. Add the $x_i$’s as depots.

• $\mathrm{■}$

  For every ternary clause $C$, introduce nodes $\widehat{C},C_{000},C_{110},C_{101},$ and $C_{011}$ with edges $\{\widehat{C},C_i\}$ of weight $3$. Add the $C_i$’s as depots.

• $\mathrm{■}$

  For every binary clause $C=x\oplus y=0$, introduce nodes $\widehat{C},C_{00},$ and $C_{11}$ with edges $\{\widehat{C},C_i\}$ of weight $2$. Add the $C_i$’s as depots. Further add nodes $\widehat{C_{00}}$ and $\widehat{C_{11}}$ where $\widehat{C_i}$ is connected only to $C_i$ by an edge of weight $1$.

• $\mathrm{■}$

  For every binary clause $C=x\oplus y=1$, introduce nodes $\widehat{C},C_{01},$ and $C_{10}$ with edges $\{\widehat{C},C_i\}$ of weight $2$. Add the $C_i$’s as depots. Further add nodes $\widehat{C_{01}}$ and $\widehat{C_{10}}$ where $\widehat{C_i}$ is connected only to $C_i$ by an edge of weight $1$.

We connect the gadgets as follows:

• $\mathrm{■}$

  For every clause $C=x\oplus y\oplus z=0$ we connect $C_{b_1{b}_2{b}_3}$ to $x_{b_1},y_{b_2},$ and $z_{b_3}$ with a path of length $2$ where both edges have weight $1$.

• $\mathrm{■}$

  For every clause $C=x\oplus y=b$ we connect $C_{b_1{b}_2}$ to $x_{b_1},y_{b_2}$ with a path of length $2$ where both edges have weight $1$.

Intuitively, there is a depot for every way a clause could be satisfied, and the depots for a clause have a joint neighbour that is expensive to connect. The depot absorbing this neighbour should correspond to the way in which the clause is satisfied. Similarly there are two depots for each variable representing the two possible assignments to the variable. In this case the depot that does not get assigned the joint neighbour corresponds to the chosen assignment.

There are then additional vertices between the clause and vertex depots which can be assigned to the clause depots, unless the adjacent clause depot corresponds to the satisfying assignment of that clause. In that case they need to be assigned to an adjacent variable depot, which is to say the variables of the clause will have to be assigned in such a way that the clause is satisfied.

One can quickly check that a satisfying assignment to the clauses will allow us to compute a tree cover where every tree has size $3$. Meanwhile every non-satisfied clause will push at least one unit of excess weight to a tree of size at least $3$. Quantifying this relationship then permits us to compute approximately the maximum number of satisfiable clauses in such a system of equations.

To illustrate the practical performance achievable by our clustering algorithms, we implemented the algorithm from Section 3 for the setting without depots in C++ and tested it on instances proposed by Zheng et al. [24]. Those instances model real-world terrain, which is to be partitioned evenly so that a fixed number robots can jointly traverse it. They consist of a grid where either random cells are set to be obstacles, i.e., inaccessible, or a grid-like arrangement of rooms is superimposed with doors closed at random. A metric is induced on the accessible cells of the grid by setting the distance of neighbouring cells to be $1$.

For all instances on grids of size $200$ by $200$ (ca. 40,000 nodes), our implementation was able to compute a clustering in less than $200$ms on an Intel i5-10600K under Windows with $48$GB of available memory (although actual memory usage was negligible). The resulting partitions are illustrated in Figure 5. Note that we make two small heuristic changes to the original algorithm, which are, however, not amenable to be analyzed formally:

First, we adapt the partitioning of the large trees in Footnote 1 to try to cut the trees into subtrees of weight at least $2R$ rather than $4R$. Note that the choice of $4R$ captures a worst-case scenario where the instance contains edges of size almost $R$ that are to be included in a solution. If the heaviest edges are considerably smaller than $R$, the necessary cutoff approaches $2R$ rather than $4R$. Thus, we run the partitioning algorithm with $2R$ rather than $4R$, and resort to the higher cutoff only in the case that this fails. Yet, for the considered instances this was not necessary.

Second, we post-process the computed solution to ensure that it has exactly $k$ components. It is in principle possible that the algorithm computes a solution with fewer than $k$ trees; in this case, we iteratively select the largest tree and split it into two parts of as similar a size as possible until we obtain exactly $k$ components.

The clusterings obtained in this way in Figure 5 are all at least $3$-approximately strongly optimal when compared to a hypothetical solution that distributes the total weight perfectly evenly on the $k$ clusters.