Abstract
This paper introduces an efficient streaming algorithm for a well-known Minimum cost Submodular Cover (\({\textsf{MSC}}\)) problem. Our algorithm makes \(O(\log n)\) passes over the ground set, takes \(O(n \log n)\) query complexity and returns a \((1/\epsilon , 1-\epsilon )\)-bicriteria approximation solution with the ground set of size n and the precise parameter \(\epsilon >0\). Therefore, it is better than the existing streaming algorithms in terms of both solution guarantees and query complexity. Besides the theoretical performance, the experiment results on two applications, Revenue Threshold and Coverage Threshold, further show the superiority of our algorithm with the state-of-the-art ones.
Canh V. Pham is a corresponding author.
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
Amanatidis, G., Fusco, F., Lazos, P., Leonardi, S., Reiffenhäuser, R.: Fast adaptive non-monotone submodular maximization subject to a knapsack constraint. In: Proceedings of Annual Conference on Neural Information Processing Systems (2020)
Buchbinder, N., Feldman, M., Seffi, J., Schwartz, R.: A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44(5), 1384–1402 (2015)
Crawford, V.: Scalable bicriteria algorithms for non-monotone submodular cover. In: Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, pp. 9517–9537. PMLR (2023)
Crawford, V., Kuhnle, A., Thai, M.: Submodular cost submodular cover with an approximate oracle. In: Proceedings of the 36th International Conference on Machine Learning, pp. 1426–1435. PMLR (2019)
Crawford, V.G.: Faster guarantees of evolutionary algorithms for maximization of monotone submodular functions. In: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19–27 August 2021, pp. 1661–1667. ijcai.org (2021)
El-Arini, K., Guestrin, C.: Beyond keyword search: discovering relevant scientific literature. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, 21–24 August 2011, pp. 439–447 (2011)
Goyal, A., Bonchi, F., Lakshmanan, L.V.S., Venkatasubramanian, S.: On minimizing budget and time in influence propagation over social networks. Soc. Netw. Anal. Min. 3(2), 179–192 (2013)
Iwata, S.: Submodular function minimization. Math. Program. 112, 45–64 (2008)
Kuhnle, A.: Quick streaming algorithms for maximization of monotone submodular functions in linear time. In: International Conference on Artificial Intelligence and Statistics, pp. 1360–1368. PMLR (2021)
Kuhnle, A., Crawford, V.G., Thai, M.T.: Scalable and adaptive algorithms for the triangle interdiction problem on billion-scale networks. In: 2017 IEEE International Conference on Data Mining, ICDM 2017, New Orleans, LA, USA, 18–21 November 2017, pp. 237–246 (2017)
Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J.M., Glance, N.S.: Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007, pp. 420–429 (2007)
Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A.: Fast constrained submodular maximization: personalized data summarization. In: International Conference on Machine Learning. JMLR Workshop and Conference Proceedings, vol. 48, pp. 1358–1367 (2016)
Mitrovic, M., Kazemi, E., Zadimoghaddam, M., Karbasi, A.: Data summarization at scale: a two-stage submodular approach. In: Proceedings of the 33nd International Conference on Machine Learning, pp. 3593–3602 (2016)
Norouzi-Fard, A., Bazzi, A., Bogunovic, I., El Halabi, M., Hsieh, Y.P., Cevher, V.: An efficient streaming algorithm for the submodular cover problem. In: Advances in Neural Information Processing Systems, vol. 29 (2016)
Norouzi-Fard, A., Tarnawski, J., Mitrovic, S., Zandieh, A., Mousavifar, A., Svensson, O.: Beyond 1/2-approximation for submodular maximization on massive data streams. In: Proceedings of the 37th International Conference on Machine Learning Conference, vol. 80, pp. 3826–3835 (2018)
Pham, C.V., Pham, D.V., Bui, B.Q., Nguyen, A.V.: Minimum budget for misinformation detection in online social networks with provable guarantees. Optim. Lett. 16, 515–544 (2021)
Ran, Y., Zhang, Z., Tang, S.: Improved parallel algorithm for minimum cost submodular cover problem. In: Loh, P., Raginsky, M. (eds.) Conference on Learning Theory, 2–5 July 2022, London, UK. Proceedings of Machine Learning Research, vol. 178, pp. 3490–3502. PMLR (2022). https://proceedings.mlr.press/v178/ran22a.html
Tschiatschek, S., Iyer, R.K., Wei, H., Bilmes, J.A.: Learning mixtures of submodular functions for image collection summarization. In: Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 8–13 December 2014, Montreal, Quebec, Canada, pp. 1413–1421 (2014)
Wan, P.J., Du, D.Z., Pardalos, P., Wu, W.: Greedy approximations for minimum submodular cover with submodular cost. Comput. Optim. Appl. 45(2), 463–474 (2010)
Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385–393 (1982)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Tran, T.D., Pham, C.V., Trung, D.P., Nguyen, U.T. (2024). Improved Streaming Algorithm for Minimum Cost Submodular Cover Problem. In: Hà, M.H., Zhu, X., Thai, M.T. (eds) Computational Data and Social Networks. CSoNet 2023. Lecture Notes in Computer Science, vol 14479. Springer, Singapore. https://doi.org/10.1007/978-981-97-0669-3_21
Download citation
DOI: https://doi.org/10.1007/978-981-97-0669-3_21
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-0668-6
Online ISBN: 978-981-97-0669-3
eBook Packages: Computer ScienceComputer Science (R0)