Abstract
The BP problem maximizes the sum of a suBmodular function and a suPermodular function(BP) subject to some constraints, where both functions are nonnegative and monotonic. This problem has been widely studied under the single-stage setting. In this paper, we consider a variant of the BP maximization problem. The problem is a two-stage BP maximization problem subject to a p-matroid constraint, for which we propose an approximation algorithm with constant approximation ratio parameterized by the curvatures of the two functions involved.
Supported by NSFC (Nos.11871280,12101314), NSERC grant 06446, Qinglan Project, Natural Science Foundation of Jiangsu Province (No. BK20200723), and Jiangsu Province Higher Education Foundation (No. 20KJB110022).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bai, W., Bilmes, J.A.: Greed is still good: maximizing monotone submodular+supermodular (BP) functions. In: ICML, pp. 304–313 (2018)
Balkanski, E., Krause, A., Mirzasoleiman, B., Singer, Y.: Learning sparse combinatorial representations via two-stage submodular maximization. In: ICML, pp. 2207–2216 (2016)
Conforti, M., Cornuejols, G.: Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discret. Appl. Math. 7(3), 251–274 (1984)
Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions-ii. In: Balinski, M.L., Hoffman, A.J. (eds.) Polyhedral Combinatorics, vol. 8, pp. 73–87. Springer, Cham (1978). https://doi.org/10.1007/BFb0121195
Krause, A., Guestrin, A.: Near-optimal nonmyopic value of information in graphical models. In: UAI, vol. 5 (2005)
Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM J. Discret. Math. 23(4), 2053–2078 (2010)
Laitila, J., Moilanen, A.: New performance guarantees for the greedy maximization of submodular set functions. Optim. Lett. 11, 655–665 (2017). https://doi.org/10.1007/s11590-016-1039-z
Mitrovic, M., Kazemi, E., Zadimoghaddam, M., Karbasi, A.: Data summarization at scale: a two-stage submodular approach. In: ICML, pp. 3593–3602 (2018)
Mairal, J., Bach, F., Ponce, J., Sapiro, G.: Online dictionary learning for sparse coding. In: ICML, pp. 689–696 (2009)
Maas, A.L., Daly, R.E., Pham, P.T., Huang, D., Ng, A.Y., Potts, C.: Learning word vectors for sentiment analysis. In: ACL-HLT, vol. 1, pp. 142–150 (2011)
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-i. Math. Programm. 14(1), 265–294 (1978). https://doi.org/10.1007/BF01588971
Schulz, A.S., Uhan, N.A.: Approximating the least core value and least core of cooperative games with supermodular costs. Discrete Optim. 10(2), 163–180 (2013)
Stan, S., Zadimoghaddam, M., Krause, A., Karbasi, A.: Probabilistic submodular maximization in sub-linear time. In: ICML, pp. 3241–3250 (2017)
Vincent, P., Larochelle, H., Lajoie, I., Bengio, Y., Manzagol, P.: Stacked denoising autoencoders: learning useful representations in a deep network with a local denoising criterion. J. Mach. Learn. Res. 11, 3371–3408 (2010)
Wei, K., Iyer, R., Bilmes, J.: Submodularity in data subset selection and active learning. In: Proceedings of ICML, pp. 1954–1963 (2015)
Yang, R., Gu, S., Gao, C., Wu, W., Wang, H., Xu, D.: A constrained two-stage submodular maximization. Theor. Comput. Sci. 853, 57–64 (2021)
Zhou, M., Chen, H., Ren, L., Sapiro, G., Carin, L., Paisley, J.W.: Non-parametric Bayesian dictionary learning for sparse image representations. In: NIPS, pp. 2295–2303 (2009)
Acknowledgements
The research is supported by NSFC(Nos. 11871280, 12101314, 12271259, 11971349), NSERC(No. 06446), Qinglan Project, Natural Science Foundation of Jiangsu Province (No. BK20200723), and Jiangsu Province Higher Education Foundation (No.20KJB110022).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Chang, H., Liu, Z., Du, D., Zhang, X. (2022). Two-Stage BP Maximization Under p-matroid Constraint. In: Zhang, Y., Miao, D., Möhring, R. (eds) Computing and Combinatorics. COCOON 2022. Lecture Notes in Computer Science, vol 13595. Springer, Cham. https://doi.org/10.1007/978-3-031-22105-7_40
Download citation
DOI: https://doi.org/10.1007/978-3-031-22105-7_40
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22104-0
Online ISBN: 978-3-031-22105-7
eBook Packages: Computer ScienceComputer Science (R0)