On the geometric red-blue set cover problem. (English) Zbl 07405957
Uehara, Ryuhei (ed.) et al., WALCOM: algorithms and computation. 15th international conference and workshops, WALCOM 15, Yangon, Myanmar, February 28 – March 2, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12635, 129-141 (2021).
Summary: We study the variations of the geometric Red-Blue Set Cover (RBSC) problem in the plane using various geometric objects. We show that the RBSC problem with intervals on the real line is polynomial-time solvable. The problem is \(\mathsf{NP} \)-hard for rectangles anchored on two parallel lines and rectangles intersecting a horizontal line. The problem admits a polynomial-time algorithm for axis-parallel lines. However, if the objects are horizontal lines and vertical segments, the problem becomes \(\mathsf{NP} \)-hard. Further, the problem is \(\mathsf{NP} \)-hard for axis-parallel unit segments.
We introduce a variation of the Red-Blue Set Cover problem with the set system, the Special-Red-Blue Set Cover problem, and show that the problem is \(\mathsf{APX} \)-hard. We then show that several geometric variations of the problem with: (i) axis-parallel rectangles containing the origin in the plane, (ii) axis-parallel strips, (iii) axis-parallel rectangles that are intersecting exactly zero or four times, (iv) axis-parallel line segments, and (v) downward shadows of line segments, are \(\mathsf{APX} \)-hard by providing encodings of these problems as the Special-Red-Blue Set Cover problem. This is on the same line of the work by Chan and Grant [6], who provided the \(\mathsf{APX} \)-hardness results of the geometric set cover problem for the above classes of objects.
For the entire collection see [Zbl 1470.68028].
We introduce a variation of the Red-Blue Set Cover problem with the set system, the Special-Red-Blue Set Cover problem, and show that the problem is \(\mathsf{APX} \)-hard. We then show that several geometric variations of the problem with: (i) axis-parallel rectangles containing the origin in the plane, (ii) axis-parallel strips, (iii) axis-parallel rectangles that are intersecting exactly zero or four times, (iv) axis-parallel line segments, and (v) downward shadows of line segments, are \(\mathsf{APX} \)-hard by providing encodings of these problems as the Special-Red-Blue Set Cover problem. This is on the same line of the work by Chan and Grant [6], who provided the \(\mathsf{APX} \)-hardness results of the geometric set cover problem for the above classes of objects.
For the entire collection see [Zbl 1470.68028].
MSC:
| 68Wxx | Algorithms in computer science |
Keywords:
red-blue set cover; special red-blue set cover; anchored rectangles; segments; polynomial time algorithms; \( \mathsf{APX} \)-hard; \( \mathsf{NP} \)-hardReferences:
| [1] | Alimonti, P.; Kann, V., Some APX-completeness results for cubic graphs, Theoret. Comput. Sci., 237, 1, 123-134 (2000) · Zbl 0939.68052 · doi:10.1016/S0304-3975(98)00158-3 |
| [2] | Bereg, S.; Cabello, S.; Díaz-Báñez, JM; Pérez-Lantero, P.; Seara, C.; Ventura, I., The class cover problem with boxes, Comput. Geom., 45, 7, 294-304 (2012) · Zbl 1239.65015 · doi:10.1016/j.comgeo.2012.01.014 |
| [3] | de Berg, M.; Khosravi, A.; Thai, MT; Sahni, S., Optimal binary space partitions in the plane, Computing and Combinatorics, 216-225 (2010), Heidelberg: Springer, Heidelberg · Zbl 1286.68471 · doi:10.1007/978-3-642-14031-0_25 |
| [4] | de Berg, M.; Khosravi, A., Optimal binary space partitions for segments in the plane, Int. J. Comput. Geom. Appl., 22, 3, 187-206 (2012) · Zbl 1267.68268 · doi:10.1142/S0218195912500045 |
| [5] | Carr, R.D., Doddi, S., Konjevod, G., Marathe, M.: On the red-blue set cover problem. In: SODA, pp. 345-353 (2000) · Zbl 0952.90026 |
| [6] | Chan, TM; Grant, E., Exact algorithms and APX-hardness results for geometric packing and covering problems, Comput. Geom., 47, 2, 112-124 (2014) · Zbl 1283.52032 · doi:10.1016/j.comgeo.2012.04.001 |
| [7] | Chan, TM; Hu, N., Geometric red blue set cover for unit squares and related problems, Comput. Geom., 48, 5, 380-385 (2015) · Zbl 1314.65029 · doi:10.1016/j.comgeo.2014.12.005 |
| [8] | Dhar, AK; Madireddy, RR; Pandit, S.; Singh, J., Maximum independent and disjoint coverage, J. Comb. Optim., 39, 4, 1017-1037 (2020) · Zbl 1442.90163 · doi:10.1007/s10878-020-00536-w |
| [9] | Erlebach, T.; van Leeuwen, EJ; Serna, M.; Shaltiel, R.; Jansen, K.; Rolim, J., PTAS for weighted set cover on unit squares, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 166-177 (2010), Heidelberg: Springer, Heidelberg · Zbl 1304.68214 · doi:10.1007/978-3-642-15369-3_13 |
| [10] | Fowler, RJ; Paterson, MS; Tanimoto, SL, Optimal packing and covering in the plane are NP-complete, Inf. Process. Lett., 12, 3, 133-137 (1981) · Zbl 0469.68053 · doi:10.1016/0020-0190(81)90111-3 |
| [11] | Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979) · Zbl 0411.68039 |
| [12] | Har-Peled, S.: Being Fat and Friendly is Not Enough. CoRR abs/0908.2369 (2009) |
| [13] | Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. IRSS, pp. 85-103. Springer, Boston (1972). doi:10.1007/978-1-4684-2001-2_9 · Zbl 1467.68065 |
| [14] | Li, J.; Jin, Y.; Halldórsson, MM; Iwama, K.; Kobayashi, N.; Speckmann, B., A PTAS for the weighted unit disk cover problem, Automata, Languages, and Programming, 898-909 (2015), Heidelberg: Springer, Heidelberg · Zbl 1440.68335 · doi:10.1007/978-3-662-47672-7_73 |
| [15] | Lund, C.; Yannakakis, M., On the hardness of approximating minimization problems, J. ACM, 41, 5, 960-981 (1994) · Zbl 0814.68064 · doi:10.1145/185675.306789 |
| [16] | Madireddy, R.R., Mudgal, A.: A constant-factor approximation algorithm for red-blue set cover with unit disks. In: WAOA (2020, to be appeared) · Zbl 1478.68423 |
| [17] | Mehrabi, S.: Geometric unique set cover on unit disks and unit squares. In: CCCG, pp. 195-200 (2016) |
| [18] | Mustafa, NH; Ray, S., Improved results on geometric hitting set problems, Discrete Comput. Geom., 44, 4, 883-895 (2010) · Zbl 1207.68420 · doi:10.1007/s00454-010-9285-9 |
| [19] | Papadimitriou, CH; Yannakakis, M., Optimization, approximation, and complexity classes, J. Comput. Syst. Sci., 43, 3, 425-440 (1991) · Zbl 0765.68036 · doi:10.1016/0022-0000(91)90023-X |
| [20] | Shanjani, S.H.: Hardness of approximation for red-blue covering. In: CCCG (2020) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
