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 ω 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 O(ω²n^2k). We obtain a 5-approximation algorithm if the number of agents is large (i.e., k ≥ 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 O(min{√ω, n})-approximation algorithm if d(s, t) ≤ 2 √ω, and an O(d(s, t) + √ω)-approximation algorithm if d(s, t) > 2 √ω, where d(s, t) is the distance between the start and end point.