The Traveling k-Median Problem: Approximating Optimal Network Coverage

We introduce the Traveling k-Median Problem (TkMP) as a natural extension of the k-Median Problem, where k agents (medians) can move through a graph of n nodes over a discrete time horizon of \(\omega \) steps. The agents start and end at designated nodes, and in each step can hop to an adjacent node to improve coverage. At each time step, we evaluate the coverage cost as the total connection cost of each node to its closest median. Our goal is to minimize the sum of the coverage costs over the entire time horizon.

In this paper, we initiate the study of this problem by focusing on the uniform case, i.e., when all edge costs are uniform and all agents share the same start and end locations. We show that this problem is NP-hard in general and can be solved optimally in time \(\mathcal O(\omega ^2 n^{2k})\). We obtain a 5-approximation algorithm if the number of agents is large (i.e., \(k \ge n/2\)). The more challenging case emerges if the number of agents is small (i.e., \(k < n/2\)). Our main contribution is a novel rounding scheme that allows us to round an (approximate) solution to the ‘continuous movement’ relaxation of the problem to a discrete one (incurring a bounded loss). Using our scheme, we derive constant-factor approximation algorithms on path and cycle graphs. For general graphs, we use a different (more direct) approach and derive an \(\mathcal O(\min \{\sqrt{\omega }, n\})\)-approximation algorithm if \(d(s,t) \le 2\sqrt{\omega }\), and an \(\mathcal O(d(s,t) + \sqrt{\omega })\)-approximation algorithm if \(d(s,t) > 2\sqrt{\omega }\), where \(d(s,t)\) is the distance between the start and end point.

1. 1.

   That is, for every node \(v\), there exists an agent who, through Lemma 1, is always as nearby as possible, so far as the start and end conditions allow. While it may seem nontrivial which nodes this agent could give coverage to on the way to \(v\), in fact those intermediate nodes have agents of their own serving them optimally, and the agent never has to cover anything else but \(v\).

2. 2.

   Note that the modulo operator ensures that 0 and L correspond to the same point.

We thank the three anonymous reviewers for their valuable suggestions.

Authors and Affiliations

1. Centrum Wiskunde and Informatica, Amsterdam, The Netherlands

   Dylan Huizing & Guido Schäfer

2. University of Amsterdam, Amsterdam, The Netherlands

   Guido Schäfer

Corresponding author

Correspondence to Dylan Huizing .

Editors and Affiliations

1. University of Waterloo, Waterloo, ON, Canada

   Jochen Koenemann

2. RWTH Aachen University, Aachen, Germany

   Britta Peis

A Omitted proofs

1.1 A.1 Theorem 1

Proof

U-TkMP is obviously in NP. We will prove that U-TkMP is at least as hard as the Set Cover Problem, which is NP-hard. Let \(I_1\) be the following instance of the decision version of the Set Cover Problem: given universe U and a collection S of subsets of U, can we find k (or less) members of S which have union U? Let \(I_2\) be an instance of the decision version of U-TkMP that we construct as follows. Let the node set be \(V:= V_U \cup V_S \cup \{s\}\), where each element in U is represented by its own node in \(V_U\), and each member in S is represented by its own node in \(V_S\), and \(s\) is some additional node. In the graph \(G=(V,E)\), we have \((u,v) \in E\) for nodes \(u,v \in V\) exactly when either of these two conditions hold: \(u,v \in V_S \cup \{s\}\), or \(u \in V_U\) and \(v \in V_S\) and the element that corresponds to u is contained in the subset that corresponds to v. In \(I_2\), we set \(\omega = 2\), and let all k agents start and end at \(s\), and we ask: can we find a feasible solution with cost at most \(2|S|+4|U|+(n-k)\)? \(I_2\) can be constructed in polynomial time and space with respect to the input of \(I_1\). In any feasible solution, all agents are at \(s\) at times \(\tau =0\) and \(\tau =2\), so we incur a cost of \(|S|+2|U|\). So the answer to \(I_2\) is ‘yes’ if and only if we can find a configuration at \(\tau =1\) with cost \((n-k)\), meaning every node is adjacent to at least one agent position. The agents can only be in \(V_S \cup \{s\}\), which is a clique. Adjacency to all nodes in \(V_U\) is achieved if and only if the chosen positions in \(V_S\) correspond to members of S which have union U. (If agents stay at \(s\), this corresponds to choosing less than k subsets in \(I_1\).) So any ‘yes’-answer to \(I_1\) supplies positions that will give a ‘yes’-answer to \(I_2\), and any ‘yes’-answer to \(I_2\) gives a ‘yes’-answer to \(I_1\) by reading out the positions at \(\tau =1\). So \(I_1\) and \(I_2\) are equivalent, implying U-TkMP is NP-hard.    \(\square \)

1.2 A.2 Theorem 2

Proof

Let \(G=(V,E)\) be the original graph of our TkMP-instance. We construct a weighted, expanded graph \(G^+=(V^+,E^+)\) as follows. First, make a ‘directed looping version’ of \(G\): take \(V\), and for every \(u,v \in V\), include arc (u, v) if edge \(\{u,v\} \in E\) or \(u=v\). Let this digraph be denoted by \(G'\). Next, let \(\vec {T}\) be the digraph with node set \(T\), and arc set \(\cup _{\tau \in T\setminus \{\omega \}} \{(\tau ,\tau +1)\}\), so \(\vec {T}\) is a path digraph representing the time horizon.

Then, let \(G^+\) be the tensor product \((G')^{k} \times \vec {T}\). So every node \((u_1,u_2,\ldots ,u_k,\tau _1)\) in \(G^+\) represents a position for each agent, and a time-step. There is an arc in \(G^+\) from node \((u_1,u_2,\ldots ,u_k,\tau _1)\) to node \((v_1,v_2,\ldots ,v_k,\tau _2)\) if and only if the arc \((u_a,v_a)\) is in \(G'\) for each agent \(a\), and \(\tau _2 = \tau _1 + 1\).

Finally, let each such arc in \(G^+\) have weight \(D(\sigma _2)\), where \(\sigma _2\) is the visited configuration \((v_1,v_2,\ldots ,v_k)\). This means that, walking through \(G^+\), we incur at each time-step \(\tau = 1, \ldots , \omega \) the cost of the configuration currently visited. The cost made at \(\tau =0\) is a constant that is the same for each feasible solution. Therefore, finding an optimal TkMP-solution is equivalent to finding a cheapest \((s_1,s_2,\ldots ,s_k,0) - (t_1,t_2,\ldots ,t_k,\omega )\)-path. Because \(G^+\) has \(\mathcal O(\omega n^{k})\) nodes, finding this path with Dijkstra’s algorithm has time complexity \(\mathcal O(\omega ^2 n^{2k})\).    \(\square \)

1.3 A.3 Lemma 1

Proof

Suppose first that \(\omega \ge 2n\). Then, certainly, a walk exists from \(s\) to \(v\) and then \(t\). We take a shortest \((s,v)\)-walk and a shortest \((v,t)\)-walk, and spend all remaining time ‘looping’ at \(v\). This is obviously a walk \(\pi \) that minimizes \(\sum _{\tau =0}^{\omega } d(\pi ^{\tau }, v)\), because at every time-step, the agent is as near to \(v\) as the start and end conditions allow.

Suppose now that \(\omega < 2n\). In this case, we construct \(G^+\) exactly as in the proof of Theorem 2, setting \(k=1\). Each arc \(((u,\tau ), (u',\tau +1))\) in \(G^+\) now has weight \(d(u',v)\). Because \(\omega < 2n\), we find our walk in \(\mathcal O(n^4)\) by applying Dijkstra’s algorithm on \(G^+\) from \((s,0)\) to \((t,\omega )\).    \(\square \)

1.4 A.4 Theorem 4

Proof

We construct our solution as follows. First, if \(\sigma ^*\) is an optimal \(k\)-MED-configuration, we use the \(\alpha \)-approximation algorithm to find a good configuration \(\sigma \) with \(D(\sigma ) \le \alpha D(\sigma ^*)\), requiring a running time of \(\mathcal O(kmed(n))\). Next, we assign these medians to agents arbitrarily. Finally, for each of the \(k\le n/2\) agents, we find in \(\mathcal O(n^4)\) time the \((s, t)\)-walk that minimizes the total distance to that agent’s median, using Lemma 1. This adds a running time of \(\mathcal O(n/2 \cdot n^4)\), for a total of \(\mathcal O(kmed(n) + n^5)\).

We now prove that this yields an \((\alpha + 1)\)-approximation. Let \(\mu \) be the found solution, and \(\mu ^*\) an optimal solution. Obviously, \(\mu \) consists of shortest paths from \(s\) to points in \(\sigma \), a lot of waiting in \(\sigma \), then shortest paths to \(t\).

Observe any time-step \(\tau \). If \(n-1 \le \tau \le (\omega +1) - (n-1)\), then clearly all agents have reached their position in \(\sigma \) and have not departed them yet. In each of those time-steps, we have \(D(\mu ^{\tau }) \le \alpha D(\sigma ^*)\). In the other time-steps \(\tau \), we at least know that \(D(\mu ^{\tau }) \le n^2\), because each of the \(n\) nodes has an agent at most \(n\) hops away.

So, recalling Corollary 1, we find

meaning \(\mu \) is an \((\alpha +1)\)-approximation.    \(\square \)

Reprints and permissions

© 2021 Springer Nature Switzerland AG

Policies and ethics