期刊
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS
卷 2, 期 1, 页码 77-87出版社
WORLD SCIENTIFIC PUBL CO PTE LTD
DOI: 10.1142/S1793830910000486
关键词
Discrete unit disk cover; approximation algorithm; disk stabbing
资金
- Natural Sciences and Engineering Research Council of Canada (NSERC)
- UNB Faculty of Computer Science
Given a set D of m unit disks and a set P of n points in the plane, the discrete unit disk cover problem is to select a minimum cardinality subset D' subset of D to cover P. This problem is NP-hard [14] and the best previous practical solution is a 38-approximation algorithm by Carmi et al. [5]. We first consider the line-separable discrete unit disk cover problem (the set of disk centers can be separated from the set of points by a line) for which we present an O(n( log n + m))-time algorithm that finds an exact solution. Combining our line-separable algorithm with techniques from the algorithm of Carmi et al. [5] results in an O(m(2)n(4)) time 22-approximate solution to the discrete unit disk cover problem.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据