Number of the records: 1
Constrained k-Center Problem on a Convex Polygon
- 1.
SYSNO ASEP 0534826 Document Type J - Journal Article R&D Document Type The record was not marked in the RIV Subsidiary J Článek ve WOS Title Constrained k-Center Problem on a Convex Polygon Author(s) Basappa, M. (IN)
Jallu, Ramesh Kumar (UIVT-O) RID, ORCID, SAI
Das, G. K. (IN)Number of authors 3 Source Title International Journal of Foundations of Computer Science - ISSN 0129-0541
Roč. 31, č. 2 (2020), s. 275-291Language eng - English Country SG - Singapore Keywords base-station placement ; efficient algorithms ; boundary ; Approximation algorithm ; convex polygon cover ; geometric disk cover UT WOS 000519710200007 EID SCOPUS 85081565683 DOI 10.1142/S0129054120500070 Annotation 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]. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2021
Number of the records: 1