Polynomial time approximation schemes for clustering in low highway dimension graphs

Abstrakt

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.

Klíčová slova

• Polynomial time approximation schemes
• clustering
• highway dimension