TY - GEN
T1 - A Novel Approximation Algorithm for Max-Covering Circle Problem
AU - Zhang, Kaiqi
AU - Zhang, Siyuan
AU - Gao, Jirun
AU - Wang, Hongzhi
AU - Gao, Hong
AU - Li, Jianzhong
N1 - Publisher Copyright:
© 2024, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2024
Y1 - 2024
N2 - We study the efficient approximation algorithm for max-covering circle problem. Given a set of weighted points in the plane and a circle with specified size, max-covering circle problem is to find the proper place where the center of the circle is located so that the total weight of the points covered by the circle is maximized. Our core approach is to approximate the circle with a symmetrical rectilinear polygon (SRP). We first present a method to construct the circumscribed SRP of a given circle and disclose their area relationship. Then, we convert max-covering SRP problem to SRP intersection problem, which can be efficiently solved with simple partition and modification based on the existing method. Finally, the optimal solution returned from max-covering SRP problem can be used to produce an approximate answer to max-covering circle problem. We prove that for most of the inputs, our algorithm can give a (1 - ε) approximation to the optimal solution, which only needs O(nε-1logn+nε-1log(1ε)) time for unit points and o(nε-2logn) time for weighted points.
AB - We study the efficient approximation algorithm for max-covering circle problem. Given a set of weighted points in the plane and a circle with specified size, max-covering circle problem is to find the proper place where the center of the circle is located so that the total weight of the points covered by the circle is maximized. Our core approach is to approximate the circle with a symmetrical rectilinear polygon (SRP). We first present a method to construct the circumscribed SRP of a given circle and disclose their area relationship. Then, we convert max-covering SRP problem to SRP intersection problem, which can be efficiently solved with simple partition and modification based on the existing method. Finally, the optimal solution returned from max-covering SRP problem can be used to produce an approximate answer to max-covering circle problem. We prove that for most of the inputs, our algorithm can give a (1 - ε) approximation to the optimal solution, which only needs O(nε-1logn+nε-1log(1ε)) time for unit points and o(nε-2logn) time for weighted points.
KW - (1 - ε) approximation
KW - Max-covering problem
KW - Symmetrical rectilinear polygon
UR - https://www.scopus.com/pages/publications/85180543445
U2 - 10.1007/978-3-031-49611-0_16
DO - 10.1007/978-3-031-49611-0_16
M3 - 会议稿件
AN - SCOPUS:85180543445
SN - 9783031496103
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 226
EP - 238
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 -