An Approximation Algorithm for the k-Connected Location Set Cover Problem with Color-Spanning Constraint

Motivated by the need for a more sensitive server assignment strategy in supply-chain network management, our total cost comprises coverage area (i.e., disk) sizes and "moving" service modes that facilitate multiple and flexible demand ful-fillment. Selection of k color-spanning centers to achieve cost minimization is the aim of our k-Connected Location Set Cover Problem with Color-spanning Constraint (k-CLSCPCC). The cost reflects the sum of the radii of the color-spanning disks plus the cost of connecting to disk regions. The farthest-color Voronoi diagram(FCVD) helps to assign an individual radius to each selected color-spanning center with aims to minimal cost. The main idea behind our greedy algorithm, which integrates the ideas of the classical minimum-power coverage problem and k-maximum coverage problem, is to minimize the measurable gap between the cost of connecting all nodes and the reduced cost of coverage with k disks. Our proposed algorithm can approximate a 3.368-factor solution within O(n(2)m log m) running time, equal to time cost of generating FCVD, where n is the number of input nodes and m is the number of demand types.