Abstract
In this paper, we present an adaptive algorithm for maximizing a monotone nonsubmodular function with a cardinality constraint. Based on the relationship between OPT and the maximum marginal gain of the elements in the ground set, the algorithm first calculates all possible values of OPT, then computes in parallel a family of sets each of which corresponding to each value of OPT, and lastly selects the set with maximum value as the desired solution. For the first, we divide the value range of OPT into finite parts and take the lower bound of each part as a possible value of OPT. As the main ingredient for the parallel computation, we use the Bernoulli distribution to independently sample elements so as to ensure further parallelism. Provided the generic submodularity ratio \(\gamma \) of the monotone set function, we prove the algorithm deserves an approximation ratio \(1-e^{-\gamma ^2}-\varepsilon \), consumes \(O(log(n/\eta )/\varepsilon ^2)\) adaptive rounds, and needs \(O(nlog(k)/\varepsilon ^3)\) oracle queries in expectation. Moreover, if the set function is submodular (i. e. \(\gamma =1\)), our algorithm can achieve an approximation guarantee \(1-1/e-\varepsilon \) coinciding with the state-of-art result.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bian, A., Levy, K.Y., Krause, A., Buhmann, J.M.: Continuous DR-submodular maximization: structure and algorithms. In: 31st International Proceedings Conference on Neural Information Processing Systems, pp. 486–496. Curran Associates Inc., Red Hook (2017)
Kulesza, A., Taskar, B.: Determinantal point processes for machine learning. Found. Trends Mach. Learn. 5(2–3), 123–286 (2012)
Ito, S., Fujimaki, R.: Large-scale price optimization via network flow. In: 30th International Proceedings on Neural Information Processing Systems, pp. 3862–3870. Curran Associates Inc., Red Hook (2016)
Das, A., Kempe, D.: Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In: 28th International Proceedings on International Conference on Machine Learning, pp. 1057–1064. Omnipress, Madison (2011)
Parotsidis, N., Pitoura, E., Tsaparas, P.: Centrality-aware link recommendations. In: 9th International Proceedings on Web Search and Data Mining, pp. 503–512. Association for Computing Machinery, New York (2016)
Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44(5), 1384–1402 (2015)
Feige, U., Mirrokni, V., Vondrak, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133–1153 (2011)
Balkanski, E., Singer, Y.: The adaptive complexity of maximizing a submodular function. In: 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1138–1151. Association for Computing Machinery, New York (2018)
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)
Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 314–318 (1999)
Balkanski, E., Rubinstein, A., Singer, Y.: An exponential speedup in parallel running time for submodular maximization without loss in approximation. In: 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 283–302. Society for Industrial and Applied Mathematics, USA (2019)
Ene, A., Nguyen, H.L.: Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. In: 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 274–282. Society for Industrial and Applied Mathematics, USA (2019)
Fahrbach, M., Mirrokni, V., Zadimoghaddam, M.: Submodular maximization with nearly optimal approximation, adaptivity and query complexity. In: 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 255–273. Society for Industrial and Applied Mathematics, USA (2019)
Chekuri, C., Quanrud, K.: Submodular function maximization in parallel via the multilinear relaxation. In: 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 303–322. Society for Industrial and Applied Mathematics, USA (2019)
Chekuri, C., Quanrud, K.: Parallelizing greedy for submodular set function maximization in matroids and beyond. In: 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 78–89. Association for Computing Machinery, New York (2019)
Ene, A., Nguyn, H.L., Vladu, A.: Submodular maximization with matroid and packing constraints in parallel. In: 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 90–101. Association for Computing Machinery, New York (2019)
Bian, A.A., Buhmann, J.M., Krause, A., Tschiatschek, S.: Guarantees for greedy maximization of non-submodular functions with applications. In: 34th International Proceedings on International Conference on Machine Learning - Volume 70, pp. 498–507. JMLR.org (2017)
Kuhnle, A., Smith, J., Crawford, V.G., Thai, M.T.: Fast maximization of non-submodular, monotonic functions on the integer lattice. In: Proceedings on International Conference on Machine Learning, pp. 2786–2795 (2018)
Gong, S., Nong, Q., Liu, W., Fang, Q.: Parametric monotone function maximization with matroid constraints. J. Global Optimiz. 75(3), 833–849 (2019). https://doi.org/10.1007/s10898-019-00800-2
Nong, Q., Sun, T., Gong, S., Fang, Q., Du, D., Shao, X.: Maximize a monotone function with a generic submodularity ratio. In: Du, D.-Z., Li, L., Sun, X., Zhang, J. (eds.) AAIM 2019. LNCS, vol. 11640, pp. 249–260. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-27195-4_23
Acknowledgements
The first two authors are supported by National Natural Science Foundation of China (No. 11531014, 11871081). The third author is supported by National Natural Science Foundation of China (No. 61772005) and Natural Science Foundation of Fujian Province (No. 2017J01753). The fourth author is supported by National Natural Science Foundation of China (No. 11701150).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Cui, M., Xu, D., Guo, L., Wu, D. (2020). Approximation Guarantees for Parallelized Maximization of Monotone Non-submodular Function with a Cardinality Constraint. In: Zhang, Z., Li, W., Du, DZ. (eds) Algorithmic Aspects in Information and Management. AAIM 2020. Lecture Notes in Computer Science(), vol 12290. Springer, Cham. https://doi.org/10.1007/978-3-030-57602-8_18
Download citation
DOI: https://doi.org/10.1007/978-3-030-57602-8_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-57601-1
Online ISBN: 978-3-030-57602-8
eBook Packages: Computer ScienceComputer Science (R0)