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.


翻译:我们研究的是诸如k-Median、k-Means和设施位置等在低高速公路维度图中的问题,这是运输网络的图形参数模型,以前曾表明存在这些问题的近似计划,这些近似计划要么在半极时运行(假设固定高速公路维度)[Feldmann等人,SICOMP 2018],要么在FPT 时运行(以美元组数、高速公路维度和近似因数为参数)[Becker等人,ESA~2018,Braverman等人,2020]。我们在本文件中表明存在一个多球时近似计划(假设固定高速公路维度),我们还表明,所考虑的问题在高速公路维度图1上是坚硬的。

0
下载
关闭预览

相关内容

专知会员服务
14+阅读 · 2021年5月21日
专知会员服务
50+阅读 · 2020年12月14日
【ICML2020】持续图神经网络,Continuous Graph Neural Networks
专知会员服务
149+阅读 · 2020年6月28日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
论文浅尝 | 用图网络做小样本学习
开放知识图谱
66+阅读 · 2018年6月30日
Linguistically Regularized LSTMs for Sentiment Classification
黑龙江大学自然语言处理实验室
8+阅读 · 2018年5月4日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Highway Networks For Sentence Classification
哈工大SCIR
4+阅读 · 2017年9月30日
Arxiv
0+阅读 · 2021年7月22日
VIP会员
相关资讯
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
论文浅尝 | 用图网络做小样本学习
开放知识图谱
66+阅读 · 2018年6月30日
Linguistically Regularized LSTMs for Sentiment Classification
黑龙江大学自然语言处理实验室
8+阅读 · 2018年5月4日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Highway Networks For Sentence Classification
哈工大SCIR
4+阅读 · 2017年9月30日
Top
微信扫码咨询专知VIP会员