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}\), where each \(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}\) 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}\) and we also prove a lower bound of 2.
k-center incremental algorithm competitive ratio facility location