×

Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice. (English) Zbl 07852524

Summary: We study the problem of maximizing a monotone non-submodular function under a \(d\)-knapsack constraint on the integer lattice. We propose three streaming algorithms to approach this problem. We first design a two-pass \(\min \{\alpha (1-\varepsilon)/ 2^{\alpha +1}d,\,1-1/ \alpha_w 2^\alpha-\varepsilon\}\)-approximate algorithm with total memory complexity \(O(\log d \beta^{-1}/\beta \varepsilon)\), and total query complexity for each element \(O(\log \|\mathbf{B} \|_\infty\log d \beta^{-1}/\varepsilon)\). The algorithm relies on a binary search technique to determine the amount of the current elements to be added into the output solution. It also requires to have a good estimate of the optimal value, we use the maximum value of the unit standard vector which can be obtained by reading a round of data to construct a guess set of the optimal value. Then, we modify our algorithm to avoid a repetitive reading of data by dynamically update the maximum value of the unit vector along with the coming elements, and obtain a one-pass streaming algorithm with same approximate ratio. Moreover, we design an improved StreamingKnapsack algorithm to reduce the memory complexity to \(O(d/ \varepsilon^2)\).

MSC:

90C27 Combinatorial optimization
Full Text: DOI

References:

[1] Badanidiyuru, A, Mirzasoleiman, B, Karbasi, A and Krause, A (2014). Streaming submodular maximization: Massive data summarization on the fly. In Proc. KDD, pp. 671-680.
[2] Călinescu, G, Chekuri, C, Pál, M and Vondrák, J (2011). Maximizing a submodular set function subject to a matroid constraint. SIAM Journal of Computing, 40, 1740-1766. · Zbl 1234.68459
[3] Chakrabarti, A and Kale, S (2015). Submodular maximization meets streaming: Matchings, matroids, and more. Mathematical Programming, 154, 225-247. · Zbl 1342.90212
[4] Chekuri, C and Quanrud, K (2019). Submodular function maximization in parallel via the multilinear relaxation. In Proc. SODA, pp. 303-322. · Zbl 1431.68148
[5] Das, A and Kempe, D (2011). Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In Proc. ICML, pp. 1057-1064.
[6] El-Arini, K and Guestrin, C (2011). Beyond keyword search: Discovering relevant scientific literature. In Proc. ICKDDM, pp. 439-447.
[7] Ene, A and Nguyen, HL (2019). Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. In Proc. SODA, pp. 274-282. · Zbl 1431.68152
[8] Golovin, D and Krause, A (2011). Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42, 427-486. · Zbl 1230.90141
[9] Gong, S, Nong, Q, Liu, W and Fang, Q (2019). Parametric monotone function maximization with matroid constraints. Journal of Global Optimization, 75, 833-849. · Zbl 1432.90133
[10] Gottschalk, C and Peis, B (2015). Submodular function maximization on the bounded integer lattice. In Proc. WAOA, pp. 133-144. · Zbl 1479.90174
[11] Huang, C and Kakimura, N (2019). Improved streaming algorithms for maximising monotone submodular functions under a knapsack constraint. In Proc. WADS, pp. 438-451. · Zbl 1435.68388
[12] Jiang, YJ, Wang, YS, Xu, DC, Yang, RQ and Zhang, Y (2020). Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint. Optimization Letters, 14, 1235-1248. · Zbl 1445.90094
[13] Krause, A, Leskovec, J, Guestrin, C, VanBriesen, JM and Faloutsos, C (2008). Efficient sensor placement optimization for securing large water distribution networks. Journal of Water Resources Planning and Management, 134, 516-526.
[14] Kapralov, M, Post, I and Vondrák, J (2012). Online submodular welfare maximization: Greedy is optimal. In Proc. SODA, pp. 1216-1225. · Zbl 1425.91198
[15] Kempe, D, Kleinberg, J and Tardos, E (2003). Maximizing the spread of influence through a social network. In Proc. KDD, pp. 137-146. · Zbl 1337.91069
[16] Khanna, R, Elenberg, ER, Dimakis, AG, Negahban, S and Ghosh, J (2017). Scalable greedy feature selection via weak submodularity. In Proc. ICAIS, pp. 1560-1568.
[17] Kuhnle, A, Smith, JD, Crawford, VG and Thai, MT (2018). Fast maximization of non-submodular, monotonic functions on the integer lattice. In Proc. ICML, pp. 2791-2800.
[18] Norouzi-Fard, A, Tarnawski, J, Mitrovic, S, Zandieh, A, Mousavifar, A and Svensson, O (2018). Beyond \(1/2\)-approximation for submodular maximization on massive data streams. In Proc. ICML, pp. 3829-3838.
[19] Nong, Q, Fang, J, Gong, S, Du, D, Feng, Y and Qu, X (2020). A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice. Journal of Combinatorial Optimization, 39, 1208-1220. · Zbl 1442.90130
[20] Shioura, A (2009). On the pipage rounding algorithm for submodular function maximization - a view from discrete convex analysis. Discrete Mathematics, Algorithms and Applications, 1, 1-23. · Zbl 1192.90184
[21] Soma, T, Kakimura, N, Inaba, K and Kawarabayashi, K (2014). Optimal budget allocation: Theoretical guarantee and efficient algorithm. In Proc. ICML, pp. 351-359.
[22] Soma, T and Yoshida, Y (2018). Maximization monotone submodular functions over the integer lattice. Mathematical Programming, 172, 539-563. · Zbl 1406.90108
[23] Vondrǎk, J (2008). Optimal approximation for the submodular welfare problem in the value oracle model. In Proc. STOC, pp. 67-74. · Zbl 1231.91094
[24] Wang, YJ, Xu, DC, Wang, YS and Zhang, DM (2020). Non-submodular maximization on massive data streams. Journal of Global Optimization, 76, 729-743. · Zbl 1441.90130
[25] Yang, RQ, Xu, DC, Jiang, YJ, Wang, YS and Zhang, DM (2019). Approximation robust parameterized submodular function maximization in large-scales. Asia Pacific Journal of Operational Research, 36, 195-220.
[26] Zhang, ZN, Du, DL, Jiang, YJ and Wu, CC (2021). Maximizing DR-submodular + supermodular function on the integer lattice subject to a cardinality constraint. Journal of Global Optimization, 80, 595-616. · Zbl 1479.90182
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.