|
|
JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >
このアイテムの引用には次の識別子を使用してください:
http://hdl.handle.net/10119/13802
|
| タイトル: | A 4.31-Approximation for the Geometric Unique Coverage Problem on Unit Disks |
| 著者: | Ito, Takehiro
Nakano, Shin-ichi
Okamoto, Yoshio
Otachi, Yota
Uehara, Ryuhei
Uno, Takeaki
Uno, Yushi |
| キーワード: | approxiamtion algorithm
computational geometry
unique coverage problem
unit disk |
| 発行日: | 2014-08-07 |
| 出版者: | Elsevier |
| 誌名: | Theoretical Computer Science |
| 巻: | 544 |
| 開始ページ: | 14 |
| 終了ページ: | 31 |
| DOI: | 10.1016/j.tcs.2014.04.014 |
| 抄録: | We give an improved approximation algorithm for the unique unit-disk coverage problem: Given a set of points and a set of unit disks, both in the plane, we wish to find a subset of disks that maximizes the number of points contained in exactly one disk in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and gave a polynomial-time 18-approximation algorithm. In this paper, we improve this approximation ratio 18 to 2+4/√3+ε (< 4.3095+ε) for any fixed constant ε > 0. Our algorithm runs in polynomial time which depends exponentially on 1/ε. The algorithm can be generalized to the budgeted unique unit-disk coverage problem in which each point has a profit, each disk has a cost, and we wish to maximize the totalprofit of the uniquely covered points under the condition that the total cost is at most a given bound. |
| Rights: | Copyright (C)2014, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International license (CC BY-NC-ND 4.0). [http://creativecommons.org/licenses/by-nc-nd/4.0/] NOTICE: This is the author's version of a work accepted for publication by Elsevier. Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, and Yushi Uno, Theoretical Computer Science, 544, 2014, 14-31, http://dx.doi.org/10.1016/j.tcs.2014.04.014 |
| URI: | http://hdl.handle.net/10119/13802 |
| 資料タイプ: | author |
| 出現コレクション: | b10-1. 雑誌掲載論文 (Journal Articles)
|
このアイテムのファイル:
| ファイル |
記述 |
サイズ | 形式 |
|---|
| 20293.pdf | | 262Kb | Adobe PDF | 見る/開く |
|
当システムに保管されているアイテムはすべて著作権により保護されています。
|
