Global Approximation of Local Optimality: Nonsubmodular Optimization

doi:10.1007/s40305-023-00475-3

Abstract

Abstract: In the study of information technology, one of the important efforts is made on dealing with nonsubmodular optimizations since there are many such problems raised in various areas of computer and information science. Usually, nonsubmodular optimization problems are NP-hard. Therefore, design and analysis of approximation algorithms are important tasks in the study of nonsubmodular optimizations. However, the traditional methods do not work well. Therefore, a new method, the global approximation of local optimality, is proposed recently. In this paper, we give an extensive study for this new methodology.

Key words: Global approximation, Local optimality, Nonsubmodular optimization

CLC Number:

68W25

Wei-Li Wu, Zhao Zhang, Ding-Zhu Du. Global Approximation of Local Optimality: Nonsubmodular Optimization[J]. Journal of the Operations Research Society of China, 2025, 13(2): 440-451.

TrendMD

References

[1] Yang, W., Ma, J., Li, Y., Yan, R., Yuan, J., Weili, W., Li, D.: Marginal gains to maximize content spread in social networks. IEEE Trans. Comput. Soc. Syst. 6(3), 479-490 (2019)
[2] Zhang, Y., Guo, J., Yang, W., Weili, W.: Targeted activation probability maximization problem in online social networks. IEEE Trans. Netw. Sci. Eng. 8(1), 294-304 (2021)
[3] Kimura, M., Saito, K., Motoda, H.: Blocking links to minimize contamination spread in a social network. ACM Trans. Knowl. Discov. Data 3(2), 1-23 (2009)
[4] Habiba, H., Yu, Y., Berger-Wolf, T.Y., Saia, J.: Finding spread blockers in dynamic networks. In: Series SNAKDD’08, pp. 55-76 (2010)
[5] Yan, R., Li, Y., Wu, W., Li, D., Wang, Y.: Rumor Blocking through Online Link Deletion on Social Networks. ACM Trans. Knowl. Discov. Data 13(2), 1-26 (2019)
[6] Gai, L., Hongwei, D., Lidong, W., Zhu, J., Yuehua, B.: Blocking rumor by cut. J. Comb. Optim. 36(2), 392-399 (2018)
[7] Tripathy, R.M., Bagchi, A., Mehta, S.: A study of rumor control strategies on social networks. In: Series CIKM’10. ACM (2010)
[8] Nguyen, N.P., Yan, G., Thai, M.T., Eidenbenz, S.: Containment of misinformation spread in online social networks. In: Series WebSci’12, pp. 213-222. ACM (2012)
[9] Tong, G.A., Du, D.-Z., Wu, W.: On misinformation containment in online social networks. In: NeurIPS, pp. 339-349 (2018)
[10] Yan, R., Li, D., Weili, W., Ding-Zhu, D., Wang, Y.: Minimizing influence of rumors by blockers on social networks: algorithms and analysis. IEEE Trans. Netw. Sci. Eng. 7(3), 1067-1078 (2020)
[11] Zhu, J., Ghosh, S., Weili, W.: Robust rumor blocking problem with uncertain rumor sources in social networks. World Wide Web 24(1), 229-247 (2021)
[12] Guo, J., Li, Y., Weili, W.: Targeted protection maximization in social networks. IEEE Trans. Netw. Sci. Eng. 7(3), 1645-1655 (2020)
[13] Guo, J., Chen, T., Weili, W.: A multi-feature diffusion model: rumor blocking in social networks. IEEE/ACM Trans. Netw. 29(1), 386-397 (2021)
[14] Aral, S., Walker, D.: Creating social contagion through viral product design: a randomized trial of peer influence in networks. Manage. Sci. 57(9), 1623-1639 (2011)
[15] Bonchi, F., Castillo, C., Gionis, A., Jaimes, A.: Social network analysis and mining for business applications. ACM Trans. Intell. Syst. Technol. (TIST) 2(3), 22 (2011)
[16] Stibe, A.: Exploring social influence and incremental online persuasion on twitter: a longitudinal study. In: Mobile Web Information Systems, pp. 286-300. Springer International Publishing (2014)
[17] Dong, L., Guo, Q., Weili, W.: Speech corpora subset selection based on time-continuous utterances features. J. Comb. Optim. 37(4), 1237-1248 (2019)
[18] Dong, L., Guo, Q., Weili, W., Satpute, M.N.: A semantic relatedness preserved subset extraction method for language corpora based on pseudo-Boolean optimization. Theor. Comput. Sci. 836, 65-75 (2020)
[19] Guo, J., Weili, W.: A novel scene of viral marketing for complementary products. IEEE Trans. Comput. Soc. Syst. 6(4), 797-808 (2019)
[20] Yang, W., Yuan, J., Weili, W., Ma, J., Ding-Zhu, D.: Maximizing activity profit in social networks. IEEE Trans. Comput. Soc. Syst. 6(1), 117-126 (2019)
[21] Zhu, J., Ghosh, S., Weili, W.: Group influence maximization problem in social networks. IEEE Trans. Comput. Soc. Syst. 6(6), 1156-1164 (2019)
[22] Zhu, J., Zhu, J., Ghosh, S., Weili, W., Yuan, J.: Social influence maximization in hypergraph in social networks. IEEE Trans. Netw. Sci. Eng. 6(4), 801-811 (2019)
[23] Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, 2nd edn. Springer, Berlin (1988)
[24] Orlin, J.B.: A faster strongly polynomial time algorithm for submodular function minimization. Math. Program. 118, 237-251 (2009)
[25] Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strong polynomial time. J. Comb. Theory (B) 80, 346-355 (2000)
[26] Murota, K.: Discrete Convex Analysis. SIAM, Philadelphia (2003)
[27] Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions: I. Math. Program. 14(1), 265-294 (1978)
[28] Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385-393 (1982)
[29] Feige, U., Mirrokni, V., Vondrák, J.: Maximizing nonmonotone submodular functions. In: Proceedings of the IEEE Foundations of Computer Science, pp. 461-471 (2007)
[30] Lee, J., Mirrokni, V., Nagarajan, V., Sviridenko, M.: Nonmonotone submodular maximization under matroid and knapsack constraints. In: Proceedings of the ACM Symposium on Theory of Computing, pp. 323-332 (2009)
[31] Feldman, M., Naor, J., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. IEEE FOCS, pp. 570-579 (2011)
[32] Svitkina, Z., Fleischer, L.: Submodular approximation: sampling-based algorithms and lower bounds. SIAM J. Comput. 40, 1715-1737 (2011)
[33] Feige, U., Izsak, R.: Welfare maximization and the supermodular degree. In: ACM ITCS, pp. 247-256 (2013)
[34] Feldman, M., Izsak, R.: Constrained monotone function maximization and the supermodular degree. In: ACM-SIAM SODA (2014)
[35] Bian, A.A., Buhmann, J.M., Krause, A., Tschiatschek, S.: Guarantees for greedy maximization of non-submodular functions with applications. arXiv:1703.02100 (2017)
[36] Das, A., Kempe, D.: Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. arXiv:1102.3975 (2011)
[37] Sviridenko, W.J., Vondrk, M.J.: Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42(2), 1197-1218 (2017)
[38] Wei, L., Chen, W., Lakshmanan, L.V.S.: From competition to complementarity: comparative influence diffusion and maximization. Proc. VLDB Endow. 9(2), 60-71 (2015)
[39] Chen, W., Lin, T., Tan, Z., Zhao, M., Zhou, X.: Robus influence maximization. In: KDD’16, San Francisco, CA, USA (2016)
[40] Wang, Z., Yang, Y., Pei, J., Chen, E.: Activity maximization by effective information diffusion in social networks. arXiv: 1610.07754v1 (2016)
[41] Narasimhan, M., Bilmes, J.: A submodular-supermodular procedure with applications to discriminative structure learning. In: Proceedings of the UAI (2005)
[42] Iyer, R., Bilmes, J.: Algorithms for approximate minimization of the difference between submodular functions. In: Proceedings of the UAI (2012)
[43] Weili, W., Zhang, Z., Ding-Zhu, D.: Set function optimization. J Oper Res Soc China 7(2), 183-193 (2019)
[44] Gao, C., Shuyang, G., Yang, R., Jiguo, Yu., Weili, W., Dachuan, X.: Interaction-aware influence maximization and iterated sandwich method. Theor. Comput. Sci. 821, 23-33 (2020)
[45] Schäfer, A.A., Yannakakis, M.: Simple local search problems that are hard to solve. SIAM J. Comput. 20, 56-87 (1991)
[46] Du, D.-Z., Pardalos, P.M., WuWuWu, W.: Mathematical Theory of Optimization. Kluwer Academic Publishers, New York (2001)
[47] Ding-Zhu, D., Zhang, X.-S.: A convergence theorem of Rosen’s gradient projection method. Math. Program. 36, 135-144 (1986)
[48] Ding-Zhu, D., Zhang, X.-S.: Global convergence of Rosen’s gradient projection method. Math. Program. 44, 357-366 (1989)
[49] Maehara, T., Marumo, N., Murota, K.: Continuous relaxation for discrete DC programming. In: Proceedings of the 3rd International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences, pp. 181-190 (2015)
[50] Chenchen, W., Wang, Y., Zaixin, L., Pardalos, P.M., Dachuan, X., Zhang, Z., Ding-Zhu, D.: Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming. Math. Program. 169(1), 255-275 (2018)
[51] Maehara, T., Murota, K.: A framework of discrete DC programming by discrete convex analysis. Math. Program. Ser. A 152, 435-466 (2015)
[52] Fujishige, S.: Submodular Functions and Optimization, Annals of Discrete Mathematics, vol. 58. Elsevier Science, Amsterdam (2005)
[53] Du, H., Zhang, Z., Duan, Z., Tian, C., Du, D.-Z.: Full view camera sensor coverage and group set coverage. In: Proceedings of 15th EAI International Wireless Internet Conference, Dallas, USA (2022)
[54] Vavasis, S.A.: Nonlinear Optimization: Complexity Issues. Oxford Science, New York (1991)
[55] Ye, Y.: On the complexity of approximating a KKT point of quadratic programming. Math. Program. 80, 195-211 (1998)