Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice. (English) Zbl 07605943
Summary: The study of non-submodular maximization on the integer lattice is an important extension of submodular optimization. In this paper, streaming algorithms for maximizing non-negative monotone non-submodular functions with knapsack constraint on integer lattice are considered. We first design a two-pass StreamingKnapsack algorithm combining with BinarySearch as a subroutine for this problem. By introducing the DR ratio \(\gamma\) and the weak DR ratio \(\gamma_w\) of the non-submodular objective function, we obtain that the approximation ratio is \(\min \{ \gamma^2(1 - \varepsilon) / 2^{\gamma + 1}, 1 - 1 / \gamma_w 2^\gamma - \varepsilon \}\), the total memory complexity is \(O(K \log K / \varepsilon)\), and the total query complexity for each element is \(O(\log K \log(K / \varepsilon^2) / \varepsilon)\). Then, we design a one-pass streaming algorithm by dynamically updating the maximal function value among unit vectors along with the currently arriving element. Finally, in order to decrease the memory complexity, we design an improved StreamingKnapsack algorithm and reduce the memory complexity to \(O(K / \varepsilon^2)\).
References:
| [1] | Agrawal, R.; Gollapudi, S.; Halverson, A.; Ieong, S., Diversifying search results, (Proceedings of WSDM (2009)), 5-14 |
| [2] | Alon, N.; Gamzu, I.; Tennenholtz, M., Optimizing budget allocation among channels and influencers, (Proceedings of WWW (2012)), 381-388 |
| [3] | Badanidiyuru, A.; Mirzasoleiman, B.; Karbasi, A.; Krause, A., Streaming submodular maximization: massive data summarization on the fly, (Proceedings of KDD (2014)), 671-680 |
| [4] | Buchbinder, N.; Feldman, M.; Schwartz, R., Onling submodular maximization with preemption, (Proceedings of SODA (2015)), 1202-1216 · Zbl 1371.68328 |
| [5] | Balkanski, E.; Rubinstein, A.; Singer, Y., An exponential speedup in parallel running time for submodular maximization without loss in approximation, (Proceedings of SODA (2019)), 283-302 · Zbl 1431.68144 |
| [6] | Călinescu, G.; Chekuri, C.; Pál, M.; Vondrák, J., Maximizing a submodular set function subject to a matroid constraint, SIAM J. Comput., 40, 1740-1766 (2011) · Zbl 1234.68459 |
| [7] | Chakrabarti, A.; Kale, S., Submodular maximization meets streaming: matchings, matroids, and more, Math. Program., 154, 225-247 (2015) · Zbl 1342.90212 |
| [8] | Chekuri, C.; Quanrud, K., Submodular function maximization in parallel via the multilinear relaxation, (Proceedings of SODA (2019)), 303-322 · Zbl 1431.68148 |
| [9] | Chekuri, C.; Quanrud, K., Randomize MWU for positive lps, (Proceedings of SODA (2018)), 358-377 · Zbl 1403.68332 |
| [10] | Das, A.; Kempe, D., Algorithms for subset selection in linear regression, (Proceedings of STOC (2008)), 45-54 · Zbl 1231.68283 |
| [11] | Das, A.; Kempe, D., Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection, (Proceedings of ICML (2011)), 1057-1064 |
| [12] | EI-Arini, K.; Guestrin, C., Beyond keyword search: discovering relevant scientific literature, (Proceedings of ICKDDM (2011)), 439-447 |
| [13] | Ene, A.; Nguyen, H. L., Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time, (Proceedings of SODA (2019)), 274-282 · Zbl 1431.68152 |
| [14] | Golovin, D.; Krause, A., Adaptive submodularity: theory and applications in active learning and stochastic optimization, J. Artif. Intell. Res., 42, 427-486 (2011) · Zbl 1230.90141 |
| [15] | Gomez, R. M.; Leskovec, J.; Krause, A., Inferring networks of diffusion and influence, ACM Trans. Knowl. Discov. Data, 8, 36-39 (2018) |
| [16] | Gong, S.; Nong, Q.; Liu, W.; Fang, Q., Parametric monotone function maximization with matroid constraints, J. Glob. Optim., 75, 833-849 (2019) · Zbl 1432.90133 |
| [17] | Huang, C.; Kakimura, N., Improved streaming algorithms for maximising monotone submodular functions under a knapsack constraint, (Proceedings of WADS (2019)), 438-451 · Zbl 1435.68388 |
| [18] | Jiang, Y. J.; Wang, Y. S.; Xu, D. C.; Yang, R. Q.; Zhang, Y., Streaming algorithm for maximizing a monotone non-submodular function under d-knapsack constraint, Optim. Lett., 14, 1235-1248 (2020) · Zbl 1445.90094 |
| [19] | Krause, A.; Leskovec, J.; Guestrin, C.; VanBriesen, J. M.; Faloutsos, C., Efficient sensor placement optimization for securing large water distribution networks, J. Water Resour. Plan. Manag., 134, 516-526 (2008) |
| [20] | Krause, A.; Singh, A.; Guestrin, C., Near-optimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies, J. Mach. Learn. Res., 9, 235-284 (2008) · Zbl 1225.68192 |
| [21] | Kapralov, M.; Post, I.; Vondrák, J., Online submodular welfare maximization: greedy is optimal, (Proceedings of SODA (2012)), 1216-1225 · Zbl 1425.91198 |
| [22] | Kempe, D.; Kleinberg, J.; Tardos, E., Maximizing the spread of influence through a social network, (Proceedings of KDD (2003)), 137-146 |
| [23] | Khanna, R.; Elenberg, E. R.; Dimakis, A. G.; Negahban, S.; Ghosh, J., Scalable greedy feature selection via weak submodularity, (Proceedings of ICAIS (2017)), 1560-1568 |
| [24] | Kuhnle, A.; Smith, J. D.; Crawford, V. G.; Thai, M. T., Fast maximization of non-submodular, monotonic functions on the integer lattice, (Proceedings of ICML (2018)), 2791-2800 |
| [25] | Nemhauser, G. L.; Wolsey, L. A.; Fisher, M. L., An analysis of approximations for maximizing submodular set functions, Math. Program., 14, 265-294 (1978) · Zbl 0374.90045 |
| [26] | Norouzi-Fard, A.; Tarnawski, J.; Mitrovic, S.; Zandieh, A.; Mousavifar, A.; Svensson, O., Beyond 1/2-approximation for submodular maximization on massive data streams, (Proceedings of ICML (2018)), 3829-3838 |
| [27] | Sviridenko, M., A note on maximizing a submodular set function subject to a knapsack constraint, Oper. Res. Lett., 32, 41-43 (2004) · Zbl 1056.90124 |
| [28] | Shioura, A., On the pipage rounding algorithm for submodular function maximization-a view from discrete convex analysis, Discrete Math. Algorithms Appl., 1, 1-23 (2009) · Zbl 1192.90184 |
| [29] | Soma, T.; Kakimura, N.; Inaba, K.; Kawarabayashi, K., Optimal budget allocation: theoretical guarantee and efficient algorithm, (Proceedings of ICML (2014)), 351-359 |
| [30] | Soma, T.; Yoshida, Y., A generalization of submodular cover via the diminishing return property on the integer lattice, (Proceedings of NIPS (2014)), 847-855 |
| [31] | Soma, T.; Yoshida, Y., Maximization monotone submodular functions over the integer lattice, Math. Program., 172, 539-563 (2018) · Zbl 1406.90108 |
| [32] | Vondrǎk, J., Optimal approximation for the submodular welfare problem in the value oracle model, (Proceedings of STOC (2008)), 67-74 · Zbl 1231.91094 |
| [33] | Wolsey, L., Maximising real-valued submodular set function: primal and dual heuristics for location problems, Math. Oper. Res., 7, 410-425 (1982) · Zbl 0498.90024 |
| [34] | Wang, Y. J.; Xu, D. C.; Wang, Y. S.; Zhang, D. M., Non-submodular maximization on massive data streams, J. Glob. Optim., 76, 729-743 (2020) · Zbl 1441.90130 |
| [35] | Yang, R. Q.; Xu, D. C.; Jiang, Y. J.; Wang, Y. S.; Zhang, D. M., Approximation robust parameterized submodular function maximaization in large-scales, Asia-Pac. J. Oper. Res., 36, 195-220 (2019) |
| [36] | Zhang, Z. N.; Du, D. L.; Jiang, Y. J.; Wu, C. C., Maximizing DR-submodular + supermodular function on the integer lattice subject to a cardinality constraint, J. Glob. Optim., 80, 595-616 (2021) · 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.
