Nearly time-optimal kernelization algorithms for the line-cover problem with big data. (English) Zbl 07896130
Summary: Based on well-known complexity theory conjectures, any polynomial-time kernelization algorithm for the NP-hard Line-Cover problem produces a kernel of size \(\Omega (k^2)\), where \(k\) is the size of the sought line cover. Motivated by the current research in massive data processing, we study the existence of kernelization algorithms with limited space and time complexity for Line-Cover. We prove that every kernelization algorithm for Line-Cover takes time \(\Omega (n \log k + k^2 \log k)\), and present a randomized kernelization algorithm for Line-Cover that produces a kernel of size bounded by \(k^2\), and runs in time \({\mathcal{O}}(n \log k + k^2 (\log k \log \log k)^2)\) and space \({\mathcal{O}}(k^2\log^2 k)\). Our techniques are also useful for developing deterministic kernelization algorithms for Line-Cover with limited space and improved running time, and for developing streaming kernelization algorithms for Line-Cover with near-optimal update-time.
Keywords:
line cover; kernelization algorithm; NP-complete geometric problem; parameterized computationReferences:
| [1] | Afshani, P., Berglin, E., van Duijn, I., Nielsen, J.: Applications of incidence bounds in point covering problems. In Proc. 32nd International Symposium on Computational Geometry (SoCG 2016). 60, 1-60:15, (2016) · Zbl 1387.68225 |
| [2] | Alman, J., Yu, H.: Faster update time for turnstile streaming algorithms. In Proc. 31st Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA 20). pp. 1803-1813, (2020) · Zbl 07304133 |
| [3] | Alman, J., Mnich, M., Williams, V.V.: Dynamic parameteried problems and algorithms. In Proc. 44th International Colloquium on Automata, Languages and Programming (ICALP 2017). 41, 41:1-41:16 (2017) · Zbl 1441.68103 |
| [4] | Ben-Or, M.: Lower bounds for algebraic computation trees. In Proc. 15th ACM Symposium on Theory of Computing (STOC 1983), pp. 80-86, (1983) |
| [5] | Chan, T.; Nekrich, Y., Towards an optimal method for dynamic planar point location, SIAM J. Comput., 47, 2337-2361, 2018 · Zbl 1408.68040 · doi:10.1137/16M1066506 |
| [6] | Chazelle, B., Cutting hyperplanes for divide-and-conquer, Discrete Comput. Geom., 9, 145-158, 1993 · Zbl 0784.52018 · doi:10.1007/BF02189314 |
| [7] | Chen, J., Algorithmic graph embeddings, Theoret. Comput. Sci., 181, 2, 247-266, 1997 · Zbl 0901.68149 · doi:10.1016/S0304-3975(96)00273-3 |
| [8] | Chen, J., Chu, Z., Guo, Y., Yang, W.: Space limited linear-time graph algorithms on big data. Theoret. Comput. Sci. 993, 114468 (2024) · Zbl 07819261 |
| [9] | Chen, J.; Guo, Y.; Huang, Q., Linear-time parameterized algorithms with limited local resources, Inf. Comput., 289, 2022 · Zbl 07629144 · doi:10.1016/j.ic.2022.104951 |
| [10] | Chen, J., Huang, H., Kanj, I., Li, Q., Xia, G.: Streaming algorithms for graph \(k\)-matching with optimal or near-optimal update time. Proc. 32nd International Symposium on Algorithms and Computation (ISAAC 2021). 48, 48:1-48:17, (2021) · Zbl 07788621 |
| [11] | Chen, J.; Huang, H.; Kanj, I.; Xia, G., Near-optimal algorithms for point-line fitting problems, J. Comput. Geom., 13, 1, 226-243, 2022 · Zbl 07692358 |
| [12] | Chitnis, R., Cormode, G.: Towards a theory of parameterized streaming algorithms. Proc. 14nd International Symposium on Parameterized and Exact Computation (IPEC 2019). 7, 7:1-7:15, (2019) · Zbl 07650215 |
| [13] | Chitnis, R., Cormode, G., Esfandiari,H., Hajiaghayi, M., Monemizadeh, M.: New streaming algorithms for parameterized maximal matching and beyong. In Proc. 27th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA 2015), pp. 56-58, (2015) |
| [14] | Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, (2015) · Zbl 1334.90001 |
| [15] | de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications. Springer-Verlag, (1997) · Zbl 0877.68001 |
| [16] | Fafianie, S., Kratsch, S.: Streaming kernelization. In Proc. 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014). Lecture Notes in Computer Science 8635, pp. 265-286, (2014) · Zbl 1426.68120 |
| [17] | Freedman, D.A.: Statistical Model: Theory and Practice. Cambridge University Press, (2009) · Zbl 1167.62001 |
| [18] | Grantson, M., Levcopoulos, C.: Covering a set of points with a minimum number of lines. In Proc. 6th Italian Conference on Algorithms and Complexity (CIAC 2006). Lecture Notes in Computer Science 3998, pp. 6-17, (2006) · Zbl 1183.68660 |
| [19] | Grujic, I., Bogdanovic-Dinc, S., Stoimenov, L.: Collecting and analyzing data from e-government Facebook pages. In ICT Innovations, (2014) |
| [20] | Guibas, LJ; Overmars, MH; Robert, J-M, The exact fitting problem in higher dimensions, Comput. Geom., 20, 29-42, 1991 |
| [21] | Hassin, R.; Megiddo, N., Approximation algorithms for hitting objects with straight lines, Descrete Appl. Math., 6, 4, 215-230, 1996 |
| [22] | Kratsch, S.; Philip, G.; Ray, S., Point line cover: the easy kernel is essentially tight, ACM Transact. Algor., 12, 3, 40, 2016 · Zbl 1423.68547 |
| [23] | Kremer, I.; Nisan, N.; Ron, D., On randomized one-round communication complexity, Comput. Complex., 8, 1, 21-49, 1999 · Zbl 0942.68059 · doi:10.1007/s000370050018 |
| [24] | Larsen, K, Nelson, J., Hguyen, H.: Time lower bounds for nonadaptive turnstile streaming algorithms. In Proc. 47th ACM Symposium on Theory of Computing (STOC 15), pp. 803-812, (2015) · Zbl 1321.68286 |
| [25] | McGregor, A., Graph stream algorithms: a survey, ACM SIGMOD Rec., 43, 1, 9-20, 2014 · doi:10.1145/2627692.2627694 |
| [26] | Megiddo, N.; Tamir, A., On the complexity of locating linear facilities in the plane, Oper. Res. Lett., 1, 5, 194-197, 1982 · Zbl 0507.90025 · doi:10.1016/0167-6377(82)90039-6 |
| [27] | Mnich, M., Big data algorithms beyong machine learning, Künstliche Intelligencz, 32, 9-17, 2018 · doi:10.1007/s13218-017-0517-5 |
| [28] | Muthukrishnan, S., Data streamings: algorithms and applications, Found. Trends Theor. Comput. Sci., 1, 2, 117-236, 2005 · doi:10.1561/0400000002 |
| [29] | Nekrich, Y.: Dynamic planar point location in optimal time. In Proc. 53th ACM Symposium on Theory of Computing (STOC 2021), pp. 1003-1014, (2021) · Zbl 07765227 |
| [30] | Papadimitriou, C.: Computational Complexity, Addison-Wesley, (1994) · Zbl 0833.68049 |
| [31] | Rudin, W.: Principles of Mathematical Analysis, 3rd ed., McGraw-Hill, (1976) · Zbl 0346.26002 |
| [32] | Snoeyink, J.: Chapter 38: Point Location. In Handbook of Discrete and Computational Geometry, J. Goodman, J. O’Rourke, and C. Tóth (eds.), 3rd edition, CRC Press, (2017) |
| [33] | Thorup, M.; Zhang, Y., Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation, SIAM J. Comput., 41, 2, 293-331, 2012 · Zbl 1246.68107 · doi:10.1137/100800774 |
| [34] | Wang, J.; Li, W.; Chen, J., A parameterized algorithm for the hyperplane-cover problem, Theoret. Comput. Sci., 411, 4005-4009, 2010 · Zbl 1234.68447 · doi:10.1016/j.tcs.2010.08.012 |
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.
