Paper Info
Title
An Approximation Algorithm for the k-Connected Location Set Cover Problem with Color-Spanning Constraint
Abstract
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.
Year
DOI
Venue
2021
10.1007/978-3-030-85906-0_36
ADVANCES IN PRODUCTION MANAGEMENT SYSTEMS: ARTIFICIAL INTELLIGENCE FOR SUSTAINABLE AND RESILIENT PRODUCTION SYSTEMS (APMS 2021), PT III
Keywords
DocType
Volume
Color-spanning set, Approximation algorithm, Maximum coverage problems, Farthest-Color Voronoi Diagram(FCVD), Minimum spanning tree
Conference
632
ISSN
Citations 
PageRank 
1868-4238
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Yin Wang1129.28
Yinfeng Xu21636108.18