Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs

Andreas Emil Feldmann, David Saulpic

We study clustering problems such as k-Median, k-Means, and Facility Location in graphs of low highway dimension, which is a graph parameter modeling transportation networks. It wa…