Constrained k-Center Problem on a Convex Polygon

0534826 - ÚI 2021 SG eng J - Journal Article
Basappa, M. - Jallu, Ramesh Kumar - Das, G. K.
Constrained k-Center Problem on a Convex Polygon.
International Journal of Foundations of Computer Science. Roč. 31, č. 2 (2020), s. 275-291. ISSN 0129-0541. E-ISSN 1793-6373
Keywords : base-station placement * efficient algorithms * boundary * Approximation algorithm * convex polygon cover * geometric disk cover
Impact factor: 0.416, year: 2020

In this paper, we consider a restricted covering problem, in which a convex polygon P with n vertices and an integer k are given, the objective is to cover the entire region of P using k congruent disks of minimum radius r(opt), centered on the boundary of P. For k >= 7 and any epsilon > 0, we propose an (1 + 7/k + 7 epsilon/k + epsilon)-factor approximation algorithm for this problem, which runs in O((n + k)(vertical bar log r(opt)vertical bar + log inverted right perpendicular 1/epsilon inverted left perpendicular)) time. The best known approximation factor of the algorithm for the problem in the literature is 1.8841 [H. Du and Y. Xu: An approximation algorithm for k-center problem on a convex polygon, J. Comb. Optim. 27(3) (2014) 504-518].
Permanent Link: http://hdl.handle.net/11104/0312990