No Access

Efficient Parallel Algorithm for Minimum Cost Submodular Cover Problem with Lower Adaptive Complexity

Hue T. Nguyen

https://orcid.org/0009-0001-8438-3314

Graduate University of Science and Technology, Vietnam Academy of Science and Technology (VAST), Hanoi, Vietnam

Faculty of Information Technology, Hanoi Architecture University, Hanoi, Vietnam

E-mail Address: huent@hau.edu.vn

Search for more papers by this author

Dung T. K. Ha

https://orcid.org/0000-0001-8375-7866

Faculty of Information Technology, University of Engineering and Technology, Vietnam National University, Hanoi, 144 Xuan Thuy Street, Cau Giay District, Hanoi 10000, Vietnam

E-mail Address: 20028008@vnu.edu.vn

Search for more papers by this author

, and

Canh V. Pham

https://orcid.org/0000-0002-8118-1768

ORLab, Faculty of Computer Science, Phenikaa University, Yen Nghia Ward, Ha Dong District, Hanoi 12116, Vietnam

E-mail Address: canh.phamvan@phenikaa-uni.edu.vn

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0217595924500052Cited by:0 (Source: Crossref)

Abstract

In this paper, we study the Minimum Cost Submodular Cover ( $ℳ 𝒞 𝒮 𝒞$ ) problem over the ground set of size $n$ , which aims at finding a subset with the minimal cost required so that the utility submodular function exceeds a given threshold. The problem has recently attracted a lot of attention due to its applications in various domains of operations research and artificial intelligence. However, the existing algorithms for this problem may not be easy to parallelize because of their costly adaptive complexity. However, the existing algorithms for this problem may not be effectively parallelized because of their costly adaptive complexity. This paper proposes an efficient parallel algorithm that returns a $(1 - λ, (1 + 𝜖) (1 + log \frac{1}{λ}))$ -bicriteria approximation solution within $O (log n)$ adaptive complexity, where $λ, 𝜖$ are fixed parameters. Our algorithm requires $O (n^{2} {log}^{2} n)$ query complexity, however, it can reduce to $O (n {log}^{3} n)$ instead while retaining a low adaptive complexity of $O ({log}^{2} n)$ . Therefore, our algorithm not only achieves the same approximation guarantees as the state of the art but also significantly improves the best-known low adaptive complexity algorithm for the above problem.

Keywords:

References

Agarwal, A, S Assadi and S Khanna (2019). Stochastic submodular cover with limited adaptivity. In Proc. Thirtieth Annual ACM-SIAM Symp. Discrete Algorithms, TM Chan (Ed.), pp. 323–342. SIAM. Crossref, Google Scholar
Amanatidis, G, F Fusco, P Lazos, S Leonardi, A Marchetti-Spaccamela and R Reiffenhäuser (2021). Submodular maximization subject to a knapsack constraint: Combinatorial algorithms with near-optimal adaptive complexity. In Proc. 38th Int. Conf. Machine Learning, M Meila and T Zhang (Eds.), Proceedings of Machine Learning Research, Vol. 139, pp. 231–242. PMLR, http://proceedings.mlr.press/v139/amanatidis21a.html. Google Scholar
Bach, FR (2013). Learning with submodular functions: A convex optimization perspective. Foundations and Trends in Machine Learning, 6(2–3), 145–373. Crossref, Google Scholar
Badanidiyuru, A and J Vondrák (2014). Fast algorithms for maximizing submodular functions. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, C Chekuri (Ed.), pp. 1497–1514. SIAM, https://doi.org/10.1137/1.9781611973402.110, https://doi.org/10.1137/1.9781611973402.110. Crossref, Google Scholar
Balkanski, E, A Rubinstein and Y Singer (2019). An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. In Proc. 51st Annual ACM SIGACT Symp. Theory of Computing, M Charikar and E Cohen (Eds.), pp. 66–77. ACM. Crossref, Google Scholar
Blelloch, GE, R Peng and K Tangwongsan (2011). Linear-work greedy parallel approximate set cover and variants. In Proc. of the 23rd ACMSPAA, pp. 23–32. ACM. Crossref, Google Scholar
Crawford, VG (2019). An efficient evolutionary algorithm for minimum cost submodular cover. In Proc. Twenty-Eighth Int. Joint Conf. Artificial Intelligence, S Kraus (Ed.), pp. 1227–1233. AAAI. Crossref, Google Scholar
Crawford, VG, A Kuhnle and MT Thai (2019). Submodular cost submodular cover with an approximate oracle. In Proc. 36th Int. Conf. Machine Learning, K Chaudhuri and R Salakhutdinov (Eds.), Proceedings of Machine Learning Research, Vol. 97, pp. 1426–1435. PMLR. Google Scholar
Cui, M, D Xu, L Guo and D Wu (2020). Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint. In Proc. Algorithmic Aspects in Information and Management - 14th Int. Conf., AAIM 2020, Z Zhang, W Li and D Du (Eds.), Lecture Notes in Computer Science, Vol. 12290, pp. 195–203. Springer. Crossref, Google Scholar
Das, A and D Kempe (2018). Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. Journal of Machine Learning Research, 19(3), 1–34. Google Scholar
Fahrbach, M, VS Mirrokni and M Zadimoghaddam (2019a). Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In Proc. 36th Int. Conf. Machine Learning, K Chaudhuri and R Salakhutdinov (Eds.), Proceedings of Machine Learning Research, Vol. 97, pp. 1833–1842. PMLR. Google Scholar
Fahrbach, M, VS Mirrokni and M Zadimoghaddam (2019b). Submodular maximization with nearly optimal approximation, adaptivity and query complexity. In Proc. Thirtieth Annual ACM-SIAM Symp. Discrete Algorithms, TM Chan (Ed.), pp. 255–273. SIAM. Crossref, Google Scholar
Feige, U (1998). A threshold of ln n for approximating set cover. Journal of the ACM, 45(4), 634–652. Crossref, Web of Science, Google Scholar
Goyal, A, F Bonchi, LVS Lakshmanan and S Venkatasubramanian (2013). On minimizing budget and time in influence propagation over social networks. Social Network Analysis and Mining, 3(2), 179–192. Crossref, Google Scholar
Guillory, A and JA Bilmes (2011). Simultaneous learning and covering with adversarial noise. In Proc. 28th Int. Conf. Machine Learning, Omnipress, L Getoor and T Scheffer (Eds.), pp. 369–376. PMLR. Google Scholar
Kempe, D, JM Kleinberg and É Tardos (2003). Maximizing the spread of influence through a social network. In Proc. Ninth ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, pp. 137–146. ACM, https://doi.org/10.1145/956750.956769, http://doi.acm.org/10.1145/956750.956769. Crossref, Google Scholar
Kuhnle, A, T Pan, MA Alim and MT Thai (2017). Scalable bicriteria algorithms for the threshold activation problem in online social networks. In 2017 IEEE Conf. Computer Communications, pp. 1–9. IEEE. Crossref, Google Scholar
Kuhnle, A, JD Smith, VG Crawford and MT Thai (2018). Fast maximization of non-submodular, monotonic functions on the integer lattice. In Proc. 35th Int. Conf. on Machine Learning, JG Dy and A Krause (Eds.), Proceedings of Machine Learning Research, Vol. 80, pp. 2791–2800. PMLR. Google Scholar
Lin, H and JA Bilmes (2011). A class of submodular functions for document summarization. In Proc. Conf. 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, D Lin, Y Matsumoto and R Mihalcea (Eds.), pp. 510–520. ACL. Google Scholar
Mirzasoleiman, B, A Karbasi, A Badanidiyuru and A Krause (2015). Distributed submodular cover: Succinctly summarizing massive data. In Advances in Neural Information Processing Systems 28: Annual Conf. Neural Information Processing Systems 2015, C Cortes, ND Lawrence, DD Lee, M Sugiyama and R Garnett (Eds.), pp. 2881–2889. Curran Associates, Inc. Google Scholar
Mirzasoleiman, B, M Zadimoghaddam and A Karbasi (2016). Fast distributed submodular cover: Public-private data summarization. In Advances in Neural Information Processing Systems 29: Annual Conf. Neural Information Processing Systems 2016, DD Lee, M Sugiyama, U von Luxburg, I Guyon and R Garnett (Eds.), pp. 3594–3602. Curran Associates, Inc. Google Scholar
Norouzi-Fard, A, A Bazzi, I Bogunovic, ME Halabi, Y Hsieh and V Cevher (2016). An efficient streaming algorithm for the submodular cover problem. In Advances in Neural Information Processing Systems 29: Annual Conf. Neural Information Processing Systems 2016, DD. Lee, M Sugiyama, U von Luxburg, I Guyon and R Garnett (Eds.), pp. 4493–4501. Curran Associates, Inc. Google Scholar
Parambath, SAP, N Vijayakumar and S Chawla (2018). SAGA: A submodular greedy algorithm for group recommendation. In Proc. Thirty-Second AAAI Conf. Artificial Intelligence, (AAAI-18), the 30th Innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symp. Educational Advances in Artificial Intelligence (EAAI-18), SA McIlraith and KQ Weinberger (Eds.), pp. 3900–3908. AAAI Press. Crossref, Google Scholar
Pham, CV, QV Phu and HX Hoang (2018). Targeted misinformation blocking on online social networks. In Proc. Intelligent Information and Database Systems - 10th Asian Conf., Part I, NT Nguyen, DH Hoang, T Hong, H Pham and B Trawinski (Eds.), Lecture Notes in Computer Science, Vol. 10751, pp. 107–116. Springer. Crossref, Google Scholar
Pham, CV, QV Phu, HX Hoang, J Pei and MT Thai (2019). Minimum budget for misinformation blocking in online social networks. Journal of Combinatorial Optimization, 38(4), 1101–1127. Crossref, Web of Science, Google Scholar
Ran, Y, Z Zhang and S Tang (2022). Improved parallel algorithm for minimum cost submodular cover problem. In Proc. of the Learning Theory, 2022, Proceedings of MLS, Vol. 178, pp. 3490–3502. PMLR. Google Scholar
Soma, T and Y Yoshida (2015). A generalization of submodular cover via the diminishing return property on the integer lattice. In Advances in Neural Information Processing Systems 28: Annual Conf. Neural Information Processing Systems 2015, C Cortes, ND Lawrence, DD Lee, M Sugiyama and R Garnett (Eds.), pp. 847–855. Curran Associates, Inc. Google Scholar
Vondrák, J (2008). Optimal approximation for the submodular welfare problem in the value oracle model. In Proc. 40th Annual ACM Symp. Theory of Computing, C Dwork (Ed.), pp. 67–74. ACM. Crossref, Google Scholar
Wan, P, D Du, PM Pardalos and W Wu (2010). Greedy approximations for minimum submodular cover with submodular cost. Computational Optimization and Applications, 45(2), 463–474. Crossref, Web of Science, Google Scholar
Wolsey, LA (1982). An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4), 385–393. Crossref, Web of Science, Google Scholar
Zhang, H, D Xu, L Guo and J Tan (2020). Parallelized maximization of nonsubmodular function subject to a cardinality constraint. In Proc. Computing and Combinatorics - 26th Int. Conf., D Kim, RN Uma, Z Cai and DH Lee (Eds.), Lecture Notes in Computer Science, Vol. 12273, pp. 520–531. Springer. Crossref, Google Scholar