The approximation algorithms for a class of multiple-choice problem.

Given a set of n points, which is a unit set of m colored sets, we study the minimum circle to cover one of each colored set at least. In this paper, we study some problems of optimizing some properties of color-spanning set. Firstly, we show a way to find a color-spanning set for each point and constitute a union of color-spanning sets without FCVD (The Farthest Color Voronoi Diagram). The approach to find each color-spanning set is based on the nearest neighbor points which have different colors. For every color-spanning set, we can find a enclosing circle to cover all points of each color-spanning set, which is a good approximate for MDCS (The Minimum Diameter Color-Spanning Set) problem. We propose an approximation algorithm for the SECSC (The Smallest Color-Spanning Circle) problem with 2-factor approximation result. For | P | = n and | Q | = m , the worst running time of our algorithm is O ( n 2 ) . Although these results are not as good as previous results with FCVD, the performance of our algorithms in R d is much better than others. Moreover, an approximation algorithm can solve problem of minimum perimeter of the color-spanning set faster with time of O ( n 2 + n m log ⁡ n ) and ratio 6 . This result improved the ratio with only a little cost of time complexity. At last, we give an example for the 2-center SECSC problem. A fast computation of 2-center enclosing circle is proposed with time of O ( n 2 ) , but the ratio depends on the gap between the nearest distinct colored distance. [ABSTRACT FROM AUTHOR]