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 vertical bar P vertical bar = n and vertical bar Q vertical bar = 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 Rd 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) + nm logn) 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. (C) 2016 Published by Elsevier B.V.