The 2-Mixed-Center Color Spanning Problem

Inspired by the applications in cloud manufacturing, we introduce a new 2-mixed-center version of the minimum color spanning problem, the first mixed-center model for color spanning problems to the best of our knowledge. Given a set P of n colored points on a plane, with each color chosen from a set C of \(m \le n\) colors, a 2-mixed-center color spanning problem determines the locations and radii of two disks to make the union of two disks contains at least one point of each color. Here, one center is called a discrete center, which is selected from P, while the other center is called a continuous center, which is selected from a plane. The objective is to minimize the maximum of three terms, i.e. the radii of the two disks and the distance between the two centers. We develop an exact algorithm to find the optimal solution in time complexity of \(O(n^7,n^5 m^3\log n)\) . Furthermore, we propose a 2-approximation algorithm that reduces the time complexity to \(O(nm\log n)\) .