TY - GEN
T1 - The 2-Mixed-Center Color Spanning Problem
AU - Wang, Yin
AU - Xu, Yi
AU - Xu, Yinfeng
AU - Zhang, Huili
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
PY - 2024
Y1 - 2024
N2 - 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≤ 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(n7, n5m3log n). Furthermore, we propose a 2-approximation algorithm that reduces the time complexity to O(nmlog n).
AB - 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≤ 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(n7, n5m3log n). Furthermore, we propose a 2-approximation algorithm that reduces the time complexity to O(nmlog n).
KW - Approximation algorithm
KW - Color-spanning
KW - Mixed center problem
KW - Voronoi diagram
UR - https://www.scopus.com/pages/publications/85180632871
U2 - 10.1007/978-3-031-49614-1_16
DO - 10.1007/978-3-031-49614-1_16
M3 - 会议稿件
AN - SCOPUS:85180632871
SN - 9783031496134
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 215
EP - 226
BT - Combinatorial Optimization and Applications - 16th International Conference, COCOA 2023, Proceedings
A2 - Wu, Weili
A2 - Guo, Jianxiong
PB - Springer Science and Business Media Deutschland GmbH
T2 - 16th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2023
Y2 - 15 December 2023 through 17 December 2023
ER -