Polynomial time approximation schemes for clustering in low highway dimension graphs

Abstract

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.

Keywords

• Polynomial time approximation schemes
• clustering
• highway dimension