TY - GEN
T1 - An Approximation Algorithm for the k-Connected Location Set Cover Problem with Color-Spanning Constraint
AU - Wang, Yin
AU - Xu, Yinfeng
N1 - Publisher Copyright:
© 2021, IFIP International Federation for Information Processing.
PY - 2021
Y1 - 2021
N2 - 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 fulfillment. 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(n2mlog 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.
AB - 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 fulfillment. 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(n2mlog 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.
KW - Approximation algorithm
KW - Color-spanning set
KW - Farthest-Color Voronoi Diagram(FCVD)
KW - Maximum coverage problems
KW - Minimum spanning tree
UR - https://www.scopus.com/pages/publications/85115335549
U2 - 10.1007/978-3-030-85906-0_36
DO - 10.1007/978-3-030-85906-0_36
M3 - 会议稿件
AN - SCOPUS:85115335549
SN - 9783030859053
T3 - IFIP Advances in Information and Communication Technology
SP - 317
EP - 325
BT - Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems - IFIP WG 5.7 International Conference, APMS 2021, Proceedings
A2 - Dolgui, Alexandre
A2 - Bernard, Alain
A2 - Lemoine, David
A2 - von Cieminski, Gregor
A2 - Romero, David
PB - Springer Science and Business Media Deutschland GmbH
T2 - IFIP WG 5.7 International Conference on Advances in Production Management Systems, APMS 2021
Y2 - 5 September 2021 through 9 September 2021
ER -