Bicriteria Approximation Algorithms for the Unit Disk Coverage Problem
摘要
Given a set T of n targets on the plane, the unit disk coverage problem involves placing the minimum number of unit disks necessary to ensure that each target \(t \in T\) is covered at least once. In practical applications, the number of disks is often limited, and hence, we increase the radius of each disk to meet coverage requirements. In this paper, we consider an \((\alpha ,\beta )\) bicriteria approximation algorithm for the unit disk coverage problem, where \(\beta \) \((\ge 1)\) represents the parameter by which the radius of the unit disk can be enlarged, and the size of the solution is at most \(\alpha \) times the optimum solution size (which does not enlarge the disks). Based on convex hull and semicircle covering techniques, we introduce a bicriteria approximation algorithm. The experimental results validate the effectiveness of our algorithm.