We present two (exponentially) faster PTAS's for dominating set problems in unit disk graphs. Given a geometric representation of a unit disk graph, our PTAS's that find $(1+\epsilon)$-approximate solutions to the Minimum Dominating Set (MDS) and the Minimum Connected Dominating Set (MCDS) of the input graph in time $n^{O(1/\epsilon)}$. This can be compared to the best known $n^{O(1/\epsilon \log {1/\epsilon})}$-time PTAS by Nieberg and Hurink [WAOA'05] for MDS that only uses graph structures and an $n^{O(1/\epsilon^2)}$-time PTAS for MCDS by Zhang, Gao, Wu, and Du [J Glob Optim'09]. Our key ingredients are improved dynamic programming algorithms that depend exponentially on more essential 1-dimensional "widths" of the problems.


翻译:我们用两个( expentially) 更快的 PTAS 表示单位磁盘图中设定的问题 。 鉴于单位磁盘图的几何表示, 我们的 PTAS 找到用于 MDS 最小支配数据集( MDS) 的$(1 ⁇ epsilon) 和 最小连接控制数据集( MDDS ) 。 这可以比对最著名的 $O( 1/\ epsilon\ log {1/\ epslon} 美元, 由 Nieberg 和 Hurink [WAOA' 05] 为 MDS 的 时间 PTAS, 它只使用张、 高、 吴 和 Du [J Glob Optim' 09] 的图形结构和$( $O1/\ epslon2) 。 我们的关键成份是指数化的动态编程算算法, 取决于问题的更基本的一维维的“ 维兹 ” 。

0
下载
关闭预览

相关内容

专知会员服务
25+阅读 · 2021年4月2日
专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
已删除
将门创投
11+阅读 · 2019年4月26日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Arxiv
0+阅读 · 2021年10月26日
Arxiv
0+阅读 · 2021年10月26日
Arxiv
0+阅读 · 2021年10月25日
Arxiv
0+阅读 · 2021年10月25日
VIP会员
相关资讯
已删除
将门创投
11+阅读 · 2019年4月26日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Top
微信扫码咨询专知VIP会员