A simple greedy approximation algorithm for the unit disk cover problem | ||
| AUT Journal of Mathematics and Computing | ||
| مقاله 5، دوره 1، شماره 1، اردیبهشت 2020، صفحه 47-55 اصل مقاله (526.18 K) | ||
| نوع مقاله: Original Article | ||
| شناسه دیجیتال (DOI): 10.22060/ajmc.2018.3044 | ||
| نویسندگان | ||
| Mahdi Imanparast؛ Seyed Naser Hashemi* | ||
| Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran | ||
| چکیده | ||
| Given a set $\mathcal P$ of $n$ points in the plane, the unit disk cover problem, which is known as an NP-hard problem, seeks to find the minimum number of unit disks that can cover all points of $\mathcal P$. We present a new $4$-approximation algorithm with running time $O(n \log n)$ for this problem. Our proposed algorithm uses a simple approach and is easy to understand and implement. | ||
| کلیدواژهها | ||
| Computational geometry؛ Approximation algorithms؛ Unit disk cover problem؛ Facility location | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 45,813 تعداد دریافت فایل اصل مقاله: 1,788 |
||
| تعداد نشریات | 9 |
| تعداد شمارهها | 455 |
| تعداد مقالات | 5,771 |
| تعداد مشاهده مقاله | 8,375,223 |
| تعداد دریافت فایل اصل مقاله | 6,933,601 |