Maximizing the Ratio of Monotone DR-Submodular Functions on Integer Lattice

doi:10.1007/s40305-023-00469-1

Journal of the Operations Research Society of China ›› 2025, Vol. 13 ›› Issue (1): 142-160.doi: 10.1007/s40305-023-00469-1

收稿日期:2022-06-03 修回日期:2022-12-15 出版日期:2025-03-30 发布日期:2025-03-20
通讯作者: Wen-Guo Yang,Sheng-Min-Jie Chen,Dong-Lei Du,Sui-Xiang Gao E-mail:yangwg@ucas.edu.cn;chenshengminjie19@mails.ucas.ac.cn;ddu@unb.ca;sxgao@ucas.edu.cn
基金资助:
Sheng-Min-Jie Chen’s research is partially supported by the China Scholarship Council (No.202004910755). Wen-Guo Yang’s research is partially supported by the National Natural Science Foundation of China (Nos. 12071459 and 11991022) and the Fundamental Research Funds for Central Universities (No. E1E40107X2). Dong-Lei Du’s research is partially supported by the Natural Sciences and Engineering Research Council of Canada (No.283106) and the National Natural Science Foundation of China (Nos. 11771386 and 11728104).

Maximizing the Ratio of Monotone DR-Submodular Functions on Integer Lattice

Sheng-Min-Jie Chen¹, Dong-Lei Du², Wen-Guo Yang¹, Sui-Xiang Gao¹

1 School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China;
2 Faculty of Management, University of New Brunswick, Fredericton, NB, Canada

Received:2022-06-03 Revised:2022-12-15 Online:2025-03-30 Published:2025-03-20
Contact: Wen-Guo Yang,Sheng-Min-Jie Chen,Dong-Lei Du,Sui-Xiang Gao E-mail:yangwg@ucas.edu.cn;chenshengminjie19@mails.ucas.ac.cn;ddu@unb.ca;sxgao@ucas.edu.cn

摘要/Abstract

Abstract: In this work, we focus on maximizing the ratio of two monotone DR-submodular functions on the integer lattice. It is neither submodular nor supermodular. We prove that the Threshold Decrease Algorithm is a 1—e^-(1-k_g)—ε approximation ratio algorithm. Additionally, we construct the relationship between maximizing the ratio of two monotone DR-submodular functions and maximizing the difference of two monotone DR-submodular functions on the integer lattice. Based on this relationship, we combine the dichotomy technique and Threshold Decrease Algorithm to solve maximizing the difference of two monotone DR-submodular functions on the integer lattice and prove its approximation ratio is f(x)-g(x) 1—e^-(1-k_g) f (x^*)—g(x^*)—ε. To the best of our knowledge, before us, there was no work to focus on maximizing the ratio of two monotone DR-submodular functions on integer lattice by using the Threshold Decrease Algorithm.

Key words: DR-submodular maximization, Integer lattice, Threshold decrease algorithm

中图分类号:

90C27
68W25

. [J]. Journal of the Operations Research Society of China, 2025, 13(1): 142-160.

Sheng-Min-Jie Chen, Dong-Lei Du, Wen-Guo Yang, Sui-Xiang Gao. Maximizing the Ratio of Monotone DR-Submodular Functions on Integer Lattice[J]. Journal of the Operations Research Society of China, 2025, 13(1): 142-160.

参考文献

[1] 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)
[2] Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.:An analysis of approximations for maximizing submodular set functions-II. Math. Program. 8(1), 73-87(1978)
[3] Lin, H., Bilmes, J.:A class of submodular functions for document summarization. In:Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics:Human Language Technologies-HLT'11, Vol 1, pp. 510-520(2011)
[4] Jegelka, S., Bilmes, J.:Submodularity beyond submodular energies:coupling edges in graph cuts. In: Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition. CVPR'11, pp. 1897-1904(2011)
[5] Kempe, D., Kleinberg, J., Tardos, E.:Maximizing the spread of influence through a social network. In:Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD'03, pp. 137-146(2003)
[6] Golovin, D., Krause, A.:Adaptive submodularity:theory and applications in active learning and stochastic optimization. J. Artif. Intell. Res. 42(1), 427-486(2012)
[7] Krause, A., Singh, A., Guestrin, C.:Near-optimal sensor placements in Gaussian processes:theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9(3), 235-284(2008)
[8] Joseph, K.J., R., V.T., Singh, K., Balasubramanian, V.N.:Submodular batch selection for training deep neural networks. In:Proceedings of the 28th International Joint Conference on Artificial Intelligence. IJCAI'19, pp. 2677-2683(2019)
[9] Iyer, R., Bilmes, J.:Algorithms for approximate minimization of the difference between submodular functions, with applications. In:Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence. UAI'12, pp. 407-417(2012)
[10] Narasimhan, M., Bilmes, J.:A submodular-supermodular procedure with applications to discriminative structure learning. In:Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence. UAI'05, pp. 404-412(2005)
[11] Tang, J., Tang, X., Yuan, J.:Profit maximization for viral marketing in online social networks:algorithms and analysis. IEEE Trans. Knowl. Data Eng. 30(6), 1095-1108(2018)
[12] Yoshinobu, K., Kiyohito, N., Yoshio, O.:Submodular fractional programming for balanced clustering. Pattern Recogn. Lett. 32(2), 235-243(2011)
[13] Bai, W., Iyer, R., Wei, K., Bilmes, J.:Algorithms for optimizing the ratio of submodular functions. In: Proceedings of the 33rd International Conference on International Conference on Machine Learning- ICML'16, Vol. 48, pp. 2751-2759(2016)
[14] Wang, Y.-J., Xu, D.-C., Jiang, Y.-J., Zhang, D.-M.:Minimizing ratio of monotone non-submodular functions. J. Oper. Res. Soc. China 7, 449-459(2019)
[15] Chen, S., Yang, W., Zhang, Y., Gao, S.:Output-input ratio maximization for online social networks: algorithms and analyses. IEEE Trans. Comput. Soc. Syst.(2022). https://doi.org/10.1109/TCSS.2022. 3151496
[16] Alon, N., Gamzu, I., Tennenholtz, M.:Optimizing budget allocation among channels and influencers. In:Proceedings of the 21st International Conference on World Wide Web. WWW'12, pp. 381-388(2012)
[17] Chen, W., Wu, R., Yu, Z.:Scalable lattice influence maximization. IEEE Trans. Comput. Soc. Syst. 7(4), 956-970(2020)
[18] Nakashima, S., Maehara, T.:Subspace selection via DR-submodular maximization on lattices. In: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence. AAAI'19(2019). https://doi.org/10.1609/aaai.v33i01.33014618
[19] Soma, T., Kakimura, N., Inaba, K., Kawarabayashi, K.-I.:Optimal budget allocation:theoretical guarantee and efficient algorithm.In:Proceedings of the 31stInternational Conference onInternational Conference on Machine Learning-Vol. 32. ICML'14, pp. 351-359(2014)
[20] Soma, T., Yoshida, Y.:A generalization of submodular cover via the diminishing return property on the integer lattice. In:Proceedings of the 28th International Conference on Neural Information Processing Systems-NIPS'15, Vol. 1, pp. 847-855(2015)
[21] Bian, A.A., Buhmann, J.M., Krause, A., Tschiatschek, S.:Guarantees for greedy maximization of non-submodular functions with applications. In:Proceedings of the 34th International Conference on Machine Learning-Vol. 70. ICML'17, pp. 498-507(2017)
[22] Gottschalk, C., Peis, B.:Submodular function maximization on the bounded integer lattice. In:International Workshop on Approximation and Online Algorithms, pp. 133-144(2015)
[23] Badanidiyuru, A., Vondrák, J.:Fast algorithms for maximizing submodular functions. In:Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA'14, pp. 1497- 1514(2014)
[24] Kuhnle, A., Smith, J.D., Crawford, V., Thai, M.:Fast maximization of non-submodular, monotonic functions on the integer lattice. In:Proceedings of Machine Learning Research, pp. 2786-2795. PMLR, StockholmsmäSSAN, Stockholm Sweden (2018)
[25] Soma, T., Yoshida, Y.:Non-monotone DR-submodular function maximization. In:Proceedings of the AAAI Conference on Artificial Intelligence, vol. 31(1)(2017). https://doi.org/10.1609/aaai.v31i1. 10653
[26] Soma, T., Yoshida, Y.:Maximizing monotone submodular functions over the integer lattice. Math. Program. 172, 539-563(2018). https://doi.org/10.1007/s10107-018-1324-y
[27] Zhang, Z., Du, D., Jiang, Y., Wu, C.:Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint. J. Global Optim. 80(1), 595-616(2021)
[28] Chen, S., Yang,W., Gao, S., Jin, R.:Novel algorithms formaximum ds decomposition. Theor. Comput. Sci. 857, 87-96(2021)
[29] Chen, H., Loukides, G., Fan, J., Chan, H.:Limiting the influence to vulnerable users in social networks: a ratio perspective. In:Advanced Information Networking and Applications, pp. 1106-1122(2020)
[30] Perrault, P., Healey, J.,Wen, Z., Valko,M.:On the approximation relationship between optimizing ratio of submodular (RS) and difference of submodular (DS) functions. CoRR (2021) arXiv:2101.01631

Maximizing the Ratio of Monotone DR-Submodular Functions on Integer Lattice

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价