Abstract
In the paper, we study the adaptivity of maximizing a monotone nonsubmodular function subject to a cardinality constraint. Adaptive approximation algorithm has been previously developed for the similar constrained maximization problem against submodular function, attaining an approximation ratio of \(\left( 1-1/e-\epsilon \right) \) and \(O\left( \log n/\epsilon ^{2}\right) \) rounds of adaptivity. For more general constraints, Chandra and Kent described parallel algorithms for approximately maximizing the multilinear relaxation of a monotone submodular function subject to either cardinality or packing constraints, achieving a near-optimal \(\left( 1-1/e-\epsilon \right) \)-approximation in \(O\left( \log ^{2}m\log n/\epsilon ^{4}\right) \) rounds. We propose an Expand-Parallel-Greedy algorithm for the multilinear relaxation of a monotone and normalized set function subject to a cardinality constraint based on rounding the multilinear relaxation of the function. The algorithm achieves a ratio of \(\left( 1-e^{-\gamma ^{2}}-\epsilon \right) \), runs in \(O\left( \log n/\epsilon ^{2}\right) \) adaptive rounds and requires \(O\left( \left( n\log n/\epsilon ^{2}\right) \right) \) queries, where \(\gamma \) is the Continuous generic submodularity ratio.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Balkanski E, Rubinstein A, Singer Y. An exponential speedup in parallel running time for submodular maximization without loss in approximation. In: Proceedings of SODA, 2019, pp. 283–302
Balkanski E, Singer Y. The adaptive complexity of maximizing a submodular function. In: Proceedings of STOC, 2018, pp. 1138–1151
Bian A, Buhmann M, Krause A, Tschiatschek, S. Guarantees for greedy maximization of non-submodular functions with applications. In: Proceedings of ICML, 2017, pp. 498–507
Bouhtou, M., Stephane, G., Guillaume, S.: Submodularity and randomized rounding techniques for optimal experimental design. Electronic Notes in Discrete Mathematics 36, 679–686 (2010)
Calinescu, G., Chekuri, C., Pal, M.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing 40, 1740–1766 (2011)
Chekuri C, Jayram T S, Vondr\(\acute{\rm a}\)k J. On multiplicative weight updates for concave and submodular function maximization. In: Proceedings of CITCS, 2015, pp. 201–210
Chekuri C, Quanrud K. Submodular function maximization in parallel via the multilinear relaxation. In: Proceedings of SODA, 2019, pp. 303–322
Chekuri C, Vondr\(\acute{\rm a}\)k J, Zenklusen R. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing, 2014, 43: 1831–1879
Conforti M, Cornu\(\acute{\rm e}\)jols G. Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Applied Mathematics, 1984, 7: 251–274
Das A, Kempe D. Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In: Proceedings of ICML, 2011, pp. 1057–1064
Ene A, Nguy\(\tilde{\hat{\rm e}}\)n H L. Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. In: Proceedings of SODA, 2019, pp. 274–282
Fortuin, C.M., Kasteleyn, P.W., Ginibre, J.: Correlation inequalities on some partially ordered sets. Communications in Mathematical Physics 22, 89–103 (1971)
Gong, Suning, Nong, Qingqin, Liu, Wen**g, Fang, Qizhi: Parametric monotone function maximization with matroid constraints. Journal of Global Optimization 75(3), 833–849 (2019). https://doi.org/10.1007/s10898-019-00800-2
Jegelka S, Bilmes J. Submodularity beyond submodular energies: coupling edges in graph cuts. In: Proceedings of CVPR, 2011, pp. 1897–1904
Liu Y, Wei K, Kirchhoff K. Submodular feature selection for high-dimensional acoustic score spaces. In: Proceedings of ICA, 2013, pp. 7184–7188
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-I. Mathematical Programming 14, 265–294 (1978)
Parotsidis N, Pitoura E, Tsaparas P. Centrality-aware link recommendations. In: Proceedings of WSDM, 2016, pp. 503–512
Vondr\(\acute{\rm a}\)k J. Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of STOC, 2008, pp. 67–74
Vondr\(\acute{\rm a}\)k J. Submodularity and curvature: The optimal algorithm. Annals of Discrete Math, 1978, 2: 65–74
Acknowledgements
The first and second authors are supported by National Natural Science Foundation of China (Nos. 11871081, 11531014). The third author is supported by National Natural Science Foundation of China (No. 61772005).
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
Zhang, H., Xu, D., Guo, L., Tan, J. (2020). Parallelized Maximization of Nonsubmodular Function Subject to a Cardinality Constraint. In: Kim, D., Uma, R., Cai, Z., Lee, D. (eds) Computing and Combinatorics. COCOON 2020. Lecture Notes in Computer Science(), vol 12273. Springer, Cham. https://doi.org/10.1007/978-3-030-58150-3_42
Download citation
DOI: https://doi.org/10.1007/978-3-030-58150-3_42
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-58149-7
Online ISBN: 978-3-030-58150-3
eBook Packages: Computer ScienceComputer Science (R0)