پیوندهای مفید
آمار
| تعداد نشریات | 9 |
| تعداد شمارهها | 446 |
| تعداد مقالات | 5,719 |
| تعداد مشاهده مقاله | 8,018,455 |
| تعداد دریافت فایل اصل مقاله | 6,527,281 |
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 | ||
| مراجع | ||
|
[1] R. J. Fowler, M. S. Paterson, S. L. Tanimoto, Optimal packing and covering in the plane are NP-complete, Information Processing Letters, 12(3) (1981) 133-137.
[2] D. S. Hochbaum, W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of ACM, 32 (1985) 130-136.
[3] T. F. Gonzalez, Covering a set of points in multidimensional space, Information Processing Letters, 40(4) (1991) 181-188.
[4] H. Bronnimann, M. T. Goodrich, Almost optimal set covers in finite VC-dimension, Discrete and Computational Geometry, 14(4) (1995) 463-479.
[5] M. Franceschetti, M. Cook, J. Bruck, A geometric theorem for approximate disk covering algorithms, Technical report, (2001).
[6] B. Fu, Z. Chen, M. Abdelguerfi, An almost linear time 2.8334-approximation algorithm for the disc covering problem, In Proceedings of the 3rd International Conference on Algorithmic Applications in Management (AAIM’07), (2007) 317-326.
[7] P. Liu, D. Lu, A fast 25/6-approximation for the minimum unit disk cover problem, CoRR, abs/1406.3838, (2014).
[8] A. Biniaz, P. Liu, A. Maheshwari, M. Smid, Approximation algorithms for the unit disk cover problem in 2D and 3D, Computational Geometry: Theory and Applications, 60 (2017) 8-18.
[9] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry: Algorithms and Applications, Springer Berlin Heidelberg, (2008) 95-115. | ||
|
آمار تعداد مشاهده مقاله: 42,202 تعداد دریافت فایل اصل مقاله: 1,723 |
||