Submodular optimization is widely used in large datasets. In order to speed up the problems solving, it is essential to design low-adaptive algorithms to achieve acceleration in parallel. In general, the function values are given by a value oracle, but in practice, the oracle queries may consume a lot of time. Hence, how to strike a balance between optimizing them is important. In this paper, we focus on maximizing a normalized and strictly monotone set function with the diminishing-return ratio γ under a cardinality constraint, and propose two algorithms to deal with it. We apply the adaptive sequencing technique to devise the first algorithm, whose approximation ratio is arbitrarily close to 1 - e-γ in O(log n · log(log k/γ)) adaptive rounds, and requires O(n2 ·log(log k/γ)) queries. Then by adding preprocessing and parameter estimation steps to the first algorithm, we get the second one. The second algorithm trades a small sacrifice in adaptive complexity for a significant improvement in query complexity. With the same approximation and adaptive complexity, the query complexity is improved to O(n ·log(log k/γ)). To the best of our knowledge, this is the first paper of designing adaptive algorithms for maximizing a monotone function using the diminishing-return ratio.
Bin Liu, Hui Su, Shu-Fang Gong, Qi-Zhi Fang
. Adaptive Algorithms on Maximizing Monotone Nonsubmodular Functions[J]. Journal of the Operations Research Society of China, 2024
, 12(2)
: 428
-445
.
DOI: 10.1007/s40305-022-00407-7
[1] Goemans, M.X., Williamson, D.P.:Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115-1145(1995)
[2] Feige, U.:A threshold of ln n for approximating set cover. J. ACM 45(4), 634-652(1998)
[3] Ageev, A.A., Sviridenko, M.I.:An 0.828-approximation algorithm for the uncapacitated facility location problem. Discrete Appl. Math. 3, 149-156(1999)
[4] Cornnejols, G., Fisher, M., Nemhauser, G.:Location of bank accounts of optimize float:an analytic study of exact and approximate algorithm. Manag. Sci. 23, 789-810(1977)
[5] Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.:An analysis of approximations for maximizing submodular set functions. Math. Program. 14(1), 265-294(1978)
[6] Balkanski, E., Singer, Y.:The adaptive complexity of maximizing a submodular function. In:STOC, pp. 1138-1151(2018)
[7] Balkanski, E., Rubinstein, A., Singer, Y.:An exponential speedup in parallel running time for submodular maximization without loss in approximation. In:SODA, pp. 283-302(2019)
[8] Fahrbach, M., Mirrokni, V., Zadimoghaddam, M.:Submodular maximization with nearly optimal approximation, adaptivity and query complexity. In:SODA, pp. 255-273(2019)
[9] Ene, A., Nguyen, H.L.:Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. In:SODA, pp. 274-282(2019)
[10] Breuer, A., Balkanski, E., Singer, Y.:The FAST algorithm for submodular maximization. In:ICML, pp. 1134-1143(2020)
[11] Balkanski, E., Rubinstein, A., Singer, Y.:An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. In:STOC, pp. 66-77(2019)
[12] Fahrbach, M., Mirrokni, V., Zadimoghaddam, M.:Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In:ICML, pp. 1833-1842(2019)
[13] Kuhnle, A.:Nearly linear-time, parallelizable algorithms for non-monotone submodular maximization. In:AAAI, pp. 8200-8208(2021)
[14] Krause, A., Singh, A., Guestrin, C.:Near-optimal sensor placements in Gaussian processes:theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235-284(2008)
[15] Lin, Y., Chen, W., Lui, J.C.S.:Boosting information spread:an algorithmic approach. In:ICDE, pp. 883-894(2017)
[16] Das, A., Kempe, D.:Submodular meets spectral:Greedy algorithms for subset selection, sparse approximation and dictionary selection. In:ICML, pp. 1057-1064(2011)
[17] Kuhnle, A., Smith, J.D., Crawford, V.G., Thai, M.T.:Fast maximization of nonsubmodular, monotonic functions on the integer lattice. In:ICML, pp. 2791-2800(2018)
[18] Nong, Q., Sun, T., Gong, S., Fang, Q., Du D., Shao X.:Maximize a monotone function with a generic submodularity ratio. In:AAIM, pp. 249-260(2019)
[19] Badanidiyuru, A., Vondrák, J.:Fast algorithm for maximization submodular functions. In:SODA, pp. 1497-1514(2014)
[20] Hassidim, A., Singer, Y.:Robust guarantees of stochastic greedy algorithms. In:ICML, pp. 1424-1432(2017)
