An incremental version of the k-center problem on boundary of a convex polygon

This paper studies an incremental version of the k-center problem with centers constrained to lie on boundary of a convex polygon. In the incremental k-center problem we considered, we are given a set of n demand points inside a convex polygon, facilities are constrained to lie on its boundary. Our algorithm produces an incremental sequence of facility sets $$B_{1}\subseteq B_{2}\subseteq \cdots \subseteq B_{n}$$ B 1 ⊆ B 2 ⊆ ⋯ ⊆ B n , where each $$B_{k}$$ B k contains k facilities. Such an algorithm is called $$\alpha $$ α -competitive, if for any k, the maximum of the ratio between the value of solution $$B_{k}$$ B k and the value of an optimal k-center solution is no more than $$\alpha $$ α . We present a polynomial time incremental algorithm with a competitive ratio $$\frac{3\sqrt{3}}{2}$$ 3 3 2 and we also prove a lower bound of 2.