Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Constrained k-Center Problem on a Convex Polygon
verfasst von : Manjanna Basappa, Ramesh K. Jallu, Gautam K. Das
Erschienen in: Computational Science and Its Applications -- ICCSA 2015
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we consider a restricted covering problem, in which a convex polygon
$${\mathcal{P}}$$
with
n
vertices and an integer
k
are given, the objective is to cover the entire region of
$${\mathcal{P}}$$
using
k
congruent disks of minimum radius
$$r_{opt}$$
, centered on the boundary of
$${\mathcal{P}}$$
. For
$${k\ge 7}$$
and any
$${\epsilon >0}$$
, we propose a
$${(1+\frac{7}{k}+\frac{7\epsilon }{k}+\epsilon )}$$
-factor approximation algorithm, which runs in
$${O(n(n+k)(|{\log r_{opt}}|+\log \lceil \frac{1}{\epsilon }\rceil ))}$$
time. The previous best known approximation factor in the literature for the same problem is 1.8841 [H. Du and Y. Xu: An approximation algorithm for
k
-center problem on a convex polygon, J. Comb. Optim. (2014), 27(3), 504-518].