Maximizing the Differences Between a Monotone DR-Submodular Function and a Linear Function on the Integer Lattice

doi:10.1007/s40305-022-00393-w

Journal of the Operations Research Society of China ›› 2024, Vol. 12 ›› Issue (3): 795-807.doi: 10.1007/s40305-022-00393-w

Previous Articles Next Articles

Maximizing the Differences Between a Monotone DR-Submodular Function and a Linear Function on the Integer Lattice

Zhen-Ning Zhang¹, Dong-Lei Du², Ran Ma³, Dan Wu⁴

1 Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing 100124, China;
2 Faculty of Management, University of New Brunswick, Fredericton NB E3B 9Y2, Canada;
3 School of Management Engineering, Qingdao University of Technology, Qingdao 266525, Shandong, China;
4 School of Mathematics and Statistics, Henan University of Science and Technology, Luoyang 471023, Henan, China

Received:2020-07-16 Revised:2021-11-18 Online:2024-09-30 Published:2024-08-15
Contact: Ran Ma, Zhen-Ning Zhang, Dong-Lei Du, Dan Wu E-mail:sungirlmr@163.com;zhangzhenning@bjut.edu.cn;ddu@unb.ca;lywd2964@126.com
Supported by:
The first author is supported by the National Natural Science Foundation of China (Nos. 12001025 and 12131003). The second author is supported by the Natural Sciences and Engineering Research Council (No. 06446), and the National Natural Science Foundation of China (Nos. 11771386 and 11728104). The third author is supported by the National Natural Science Foundation of China (Nos. 11501171 and 11771251), and the Province Natural Science Foundation of Shandong (No. ZR2020MA028). The fourth author is supported by the National Natural Science Foundation of China (No. 11701150).

Abstract

Abstract: In this paper, we investigate the maximization of the differences between a nonnegative monotone diminishing return submodular (DR-submodular) function and a nonnegative linear function on the integer lattice. As it is almost unapproximable for maximizing a submodular function without the condition of nonnegative, we provide weak (bifactor) approximation algorithms for this problem in two online settings, respectively. For the unconstrained online model, we combine the ideas of single threshold greedy, binary search and function scaling to give an efficient algorithm with a 1/2 weak approximation ratio. For the online streaming model subject to a cardinality constraint, we provide a one-pass ($3-\sqrt{5}$)/2 weak approximation ratio streaming algorithm. Its memory complexity is (klogk/ε), and the update time for per element is (log²k/ε).

Key words: Submodular maximization, DR-submodular, Integer lattice, Single-threshold greedy algorithm, Streaming algorithm

CLC Number:

90C27

Zhen-Ning Zhang, Dong-Lei Du, Ran Ma, Dan Wu. Maximizing the Differences Between a Monotone DR-Submodular Function and a Linear Function on the Integer Lattice[J]. Journal of the Operations Research Society of China, 2024, 12(3): 795-807.

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, 265-294(1978)
[2] Svirdenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Letter 32, 41-43(2004)
[3] Svirdenko, M., Vondrák, J., Ward, J.: Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42, 1197-1218(2017)
[4] Feldman, M.: Guess free maximization of submodular and linear sums, In: Workshop on Algorithms and Data Structures, pp. 380-394(2019)
[5] Harshaw, C., Feldman, M., Ward, J., Karbasi, A.: Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications, In: Proceedings of ICML, pp. 2634-2643(2019)
[6] Ene, A.: A note on maximizing the difference between a monotone submodular function and a linear function. arXiv: 2002.07782v1, (2020)
[7] Ene, A., Nikolakaki, S.M., Terzi, E.: Team formation: Striking a balance between coverage and cost, In: Proceedings of KDD (2021)
[8] Topkis, D.M.: Supermodularity and Complementarity. Princeton University Press, Chichester, West Sussex (1998)
[9] Soma, T., Kakimura, N., Inaba, K., Kawarabayashi, K.: Optimal budget allocation: theoretical guarantee and efficient algorithm, In: Proceedings of ICML, pp. 351-359(2014)
[10] Soma, T., Yoshida, Y.: Maximizing monotone submodular functions over the integer lattice. Math. Program. 172, 539-563(2018)
[11] Soma, T., Yoshida, Y.: A generalization of submodular cover via the diminishing return property on the integer lattice, In: Proceedings of NIPS, pp. 847-855(2015)
[12] Kuhnle, A., Smith, J.D., Crawford, V.G., Thai, M.T.: Fast maximization of non-submodular, monotonic functions on the integer lattice, In: Proceedings of ICML, pp. 2791-2800(2018)
[13] Qian, C., Zhang, Y., Tang, K., Yao, X.: On multiset selection with size constraints, In: Proceedings of AAAI, pp. 1395-1402(2018)
[14] Soma, T., Yoshida, Y.: Non-monotone dr-submodular function maximization, In: Proceedings of AAAI, pp. 898-904(2017)
[15] Wang, Y., Xu, D., Wang, Y., Zhang, D.: Non-submodular maximization on massive data streams. J. Global Optim. 76, 729-743(2020)
[16] Badanidiyuru, A., Mirzasoleiman, B., Karbasi, A., Krause, A.: Streaming submodular maximization: massive data summarization on the fly, In: Proceedings of KDD, pp. 671-680(2014)

Maximizing the Differences Between a Monotone DR-Submodular Function and a Linear Function on the Integer Lattice

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments