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 , where each contains k facilities. Such an algorithm is called -competitive, if for any k, the maximum of the ratio between the value of solution and the value of an optimal k-center solution is no more than . We present a polynomial time incremental algorithm with a competitive ratio and we also prove a lower bound of 2.