2021-09-09

# The Traveling k-Median Problem: Approximating optimal network coverage

## Publication

### Publication

*Presented at the 19th International Workshop on Approximation and Online Algorithms, WAOA 2021 (September 2021), Virtual, Online*

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(ω2n2 k). 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.

Additional Metadata | |
---|---|

, , , | |

doi.org/10.1007/978-3-030-92702-8_6 | |

Lecture Notes in Computer Science | |

19th International Workshop on Approximation and Online Algorithms, WAOA 2021 | |

Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |

Huizing, D, & Schäfer, G. (2021). The Traveling k-Median Problem: Approximating optimal network coverage. In
Proceedings of the 19th International Workshop on Approximation and Online Algorithms (pp. 80–98). doi:10.1007/978-3-030-92702-8_6 |