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

doi:10.1007/s40305-023-00469-1

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

CLC Number:

90C27
68W25

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.

TrendMD

References

[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