Two-stage BP maximization under \(p\)-matroid constraint. (English) Zbl 1535.81058
Summary: 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.
MSC:
| 81P68 | Quantum computation |
| 35B50 | Maximum principles in context of PDEs |
| 14J15 | Moduli, classification: analytic theory; relations with modular forms |
| 62F30 | Parametric inference under constraints |
| 53C21 | Methods of global Riemannian geometry, including PDE methods; curvature restrictions |
| 65D15 | Algorithms for approximation of functions |
Keywords:
two-stage BP maximization; submodular term; supermodular term; \(p\)-matroid constraint; curvatureSoftware:
IMDBReferences:
| [1] | Bai, W.; Bilmes, J. A., Greed is still good: maximizing monotone submodular+supermodular (BP) functions, (ICML, 2018), 304-313 |
| [2] | Balkanski, E.; Krause, A.; Mirzasoleiman, B.; Singer, Y., Learning sparse combinatorial representations via two-stage submodular maximization, (ICML, 2016), 2207-2216 |
| [3] | Conforti, M.; Cornuejols, G., Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem, Discrete Appl. Math., 7, 3, 251-274, 1984 · Zbl 0533.90062 |
| [4] | Fisher, M. L.; Nemhauser, G. L.; Wolsey, L. A., An analysis of approximations for maximizing submodular set functions-ii, Polyhedral Combinator., 73-87, 1978 · Zbl 0408.90085 |
| [5] | Krause, A.; Guestrin, A., Near-optimal nonmyopic value of information in graphical models, (UAI, vol. 5, 2005) |
| [6] | Lee, J.; Mirrokni, V. S.; Nagarajan, V.; Sviridenko, M., Maximizing nonmonotone submodular functions under matroid or knapsack constraints, SIAM J. Discrete Math., 23, 4, 2053-2078, 2010 · Zbl 1207.68445 |
| [7] | Laitila, J.; Moilanen, A., New performance guarantees for the greedy maximization of submodular set functions, Optim. Lett., 11, 655-665, 2017 · Zbl 1368.90124 |
| [8] | Mitrovic, M.; Kazemi, E.; Zadimoghaddam, M.; Karbasi, A., Data summarization at scale: a two-stage submodular approach, (ICML, 2018), 3593-3602 |
| [9] | Mairal, J.; Bach, F.; Ponce, J.; Sapiro, G., Online dictionary learning for sparse coding, (ICML, 2009), 689-696 |
| [10] | Maas, A. L.; Daly, R. E.; Pham, P. T.; Huang, D.; Ng, A. Y.; Potts, C., Learning word vectors for sentiment analysis, (ACL-HLT, vol. 1, 2011), 142-150 |
| [11] | 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 · Zbl 0374.90045 |
| [12] | 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 · Zbl 1284.91034 |
| [13] | Stan, S.; Zadimoghaddam, M.; Krause, A.; Karbasi, A., Probabilistic submodular maximization in sub-linear time, (ICML, 2017), 3241-3250 |
| [14] | 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 · Zbl 1242.68256 |
| [15] | 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 · Zbl 1482.90189 |
| [16] | Zhou, M.; Chen, H.; Ren, L.; Sapiro, G.; Carin, L.; Paisley, J. W., Non-parametric bayesian dictionary learning for sparse image representations, (NIPS, 2009), 2295-2303 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
