Abstract
In this paper, we study the bound coverage problem by aligned disks in \(L_1\) metric. Suppose U is a set of users, L is a horizontal line on the plane, and S is a set of points on the line L, where each user has a profit. This problem to select a set of disks in \(L_1\) metric such that the center of each disk is a point in S (but with arbitrary radius) and the total profit of the covered users by the selected disk set is at least B, where B is a given profit bound, the disk in \(L_1\) metric is a region with a rotated square boundary, and the relationship between the cost of a disk with radius r is \(r^{\alpha }\) (\(\alpha \ge 1\)). This objective is to minimize the total cost of the selected disks. We prove that this problem is NP-hard even when \(\alpha = 1\), and present a fully polynomial time approximation scheme based on a rounding-and-scaling technique.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alt, H., et al.: Minimum-cost coverage of point sets by disks. In: Annual Symposium on Computational Geometry, pp. 449–458. Association for Computing Machinery, New York, NY, USA (2006)
Araki, T., Nakano, S.: Max–min dispersion on a line. J. Comb. Optim. 44, 1–7 (2020). https://doi.org/10.1007/s10878-020-00549-5
Bilò, V., Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Geometric clustering to minimize the sum of cluster sizes. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 460–471. Springer, Heidelberg (2005). https://doi.org/10.1007/11561071_42
Dai, H., Deng, B., Li, W., Liu, X.: A note on the minimum power partial cover problem on the plane. J. Comb. Optim. 44, 970–978 (2022). https://doi.org/10.1007/s10878-022-00869-8
Dai, H., Li, W., Liu, X.: An approximation algorithm for the \(h\)-prize-collecting power cover problem. In: International Computing and Combinatorics Conference. Accepted (2022)
Freund, A., Rawitz, D.: Combinatorial interpretations of dual fitting and primal fitting. In: Solis-Oba, R., Jansen, K. (eds.) WAOA 2003. LNCS, vol. 2909, pp. 137–150. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24592-6_11
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H Freeman and Company, USA (1979)
Lev-Tov, N., Peleg, D.: Polynomial time approximation schemes for base station coverage with minimum total radii. Comput. Netw. 47(4), 489–501 (2005)
Li, M., Ran, Y., Zhang, Z.: A primal-dual algorithm for the minimum power partial cover problem. J. Comb. Optim. (2022). https://doi.org/10.1007/s10878-020-00567-3
Li, W., Li, J., Guan, L., Shi, Y.: The prize-collecting call control problem on weighted lines and rings. RAIRO-Oper. Res. 50, 39–46 (2015)
Liang, W., Li, M., Zhang, Z., Huang, X.: Minimum power partial multi-cover on a line. Theoret. Comput. Sci. 864, 118–128 (2021)
Liu, X., Dai, H., Li, S., Li, W.: \(k\)-prize-collecting minimum power cover problem with submodular penalties on a plane (In Chinese). Sci. Sinica Inf. 52(6), 947–959 (2022)
Liu, X., Li, W., Dai, H.: Approximation algorithms for the minimum power cover problem with submodular/linear penalties. Theoret. Comput. Sci. 923, 256–270 (2022)
Liu, X., Li, W., Xie, R.: A primal-dual approximation algorithm for the k-prize-collecting minimum power cover problem. Opt. Lett. 16, 2373–2385 (2022)
Nakano, S.: The coverage problem by aligned disks. In: Chen, C.-Y., Hon, W.-K., Hung, L.-J., Lee, C.-W. (eds.) COCOON 2021. LNCS, vol. 13025, pp. 221–230. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-89543-3_19
Ran, Y., Huang, X., Zhang, Z., Du, D.: Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks. J. Global Optim. 80, 661–677 (2021). https://doi.org/10.1007/s10898-021-01033-y
Sahni, S.K.: Algorithms for scheduling independent tasks. J. ACM 23(1), 116–127 (1976)
Xiao, M., Zhao, S., Li, W., Yang, J.: Online bottleneck semi-matching. In: Du, D.-Z., Du, D., Wu, C., Xu, D. (eds.) COCOA 2021. LNCS, vol. 13135, pp. 445–455. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92681-6_35
Acknowledgements
The work is supported in part by the National Natural Science Foundation of China [No. 12071417] and the Open Project Program of Yunnan Key Laboratory of Intelligent Systems and Computing (No. ISC22Z03).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Liu, X., Liu, Z. (2022). The Bound Coverage Problem by Aligned Disks in \(L_1\) Metric. In: Zhang, Y., Miao, D., Möhring, R. (eds) Computing and Combinatorics. COCOON 2022. Lecture Notes in Computer Science, vol 13595. Springer, Cham. https://doi.org/10.1007/978-3-031-22105-7_27
Download citation
DOI: https://doi.org/10.1007/978-3-031-22105-7_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22104-0
Online ISBN: 978-3-031-22105-7
eBook Packages: Computer ScienceComputer Science (R0)