Skip to Main content Skip to Navigation
Journal articles

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. It was previously shown that approximation schemes for these problems exist, which either run in quasi-polynomial time (assuming constant highway dimension) (Feldmann et al., 2018) [8] or run in FPT time (parameterized by the number of clusters k, the highway dimension, and the approximation factor) (Becker et al., 2018; Braverman et al., 2021) [9], [10]. In this paper we show that a polynomial-time approximation scheme (PTAS) exists (assuming constant highway dimension). We also show that the considered problems are NP-hard on graphs of highway dimension 1.
Document type :
Journal articles
Complete list of metadata

https://hal.sorbonne-universite.fr/hal-03419063
Contributor : David Saulpic Connect in order to contact the contributor
Submitted on : Monday, November 8, 2021 - 11:47:03 AM
Last modification on : Tuesday, January 4, 2022 - 5:50:50 AM

Links full text

Identifiers

Citation

Andreas Emil Feldmann, David Saulpic. Polynomial time approximation schemes for clustering in low highway dimension graphs. Journal of Computer and System Sciences, Elsevier, 2021, 122, pp.72-93. ⟨10.1016/j.jcss.2021.06.002⟩. ⟨hal-03419063⟩

Share

Metrics

Les métriques sont temporairement indisponibles