文章基本信息

标题：Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs
本地全文：下载
作者：Andreas Emil Feldmann ; David Saulpic
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：46:1-46:22
DOI：10.4230/LIPIcs.ESA.2020.46
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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. SICOMP 2018] or run in FPT time (parameterized by the number of clusters k, the highway dimension, and the approximation factor) [Becker et al. ESA 2018, Braverman et al. 2020]. 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.
关键词：Approximation Scheme; Clustering; Highway Dimension