Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China
School of Mathematics and Statistics, Ningbo University, Ningbo 315211, China
Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, China
Show Author Information
Hide Author Information
Abstract
In this paper, we mainly investigate the optimization model that minimizes the cost function such that the cover function exceeds a required threshold in the set cover problem, where the cost function is additive linear, and the cover function is non-monotone approximately submodular. We study the problem under streaming model and propose three bicriteria approximation algorithms. Firstly, we provide an intuitive streaming algorithm under the assumption of known optimal objective value. The intuitive streaming algorithm returns a solution such that its cover function value is no less than times threshold, and the cost function is no more than , where is a value that we suppose for the optimal solution and is the approximation ratio of an algorithm for unconstrained maximization problem that we can call directly. Next we present a bicriteria streaming algorithm scanning the ground set multi-pass to weak the assumption that we guess the optimal objective value in advance, and maintain the same bicriteria approximation ratio. Finally we modify the multi-pass streaming algorithm to a single-pass one without compromising the performance ratio. Additionally, we also propose some numerical experiments to test our algorithm’s performance comparing with some existing methods.
No abstract is available for this article. Click the button above to view the PDF directly.
References
[1]
E. J. Barezi, I. D. Wood, P. Fung, and H. R. Rabiee, A submodular feature-aware framework for label subset selection in extreme classification problems, in Proc. 2019 Conf. North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Minneapolis, MN, USA, 2019, pp. 1009–1018.
J. Xu, L. Mukherjee, Y. Li, J. Warner, J. M. Rehg, and V. Singh, Gaze-enabled egocentric video summarization via constrained submodular maximization, in Proc. 2015 IEEE Conf. Computer Vision and Pattern Recognition, Boston, MA, USA, 2015, pp. 2235–2244.
A. Das and D. Kempe, Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection, in Proc. 28th Int. Conf. Int. Conf. Machine Learning, Bellevue, WA, USA, 2011, pp. 1057–1064.
J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, Cost-effective outbreak detection in networks, in Proc. 13th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, San Jose, CA, USA, 2007, pp. 420–429.
D. Kempe, J. Kleinberg, and É. Tardos, Maximizing the spread of influence through a social network, in Proc. 9th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Washington, DC, USA, 2003, pp. 137–146.
V. G. Crawford, A. Kuhnle, and M. T. Thai, Submodular cost submodular cover with an approximate oracle, in Proc. 36th Int. Conf. Machine Learning, Long Beach, CA, USA, 2019, pp. 1426–1435.
P. J. Wan, D. Z. Du, P. Pardalos, and W. Wu, Greedy approximations for minimum submodular cover with submodular cost, Comput. Optim. Appl., vol. 45, no. 2, pp. 463–474, 2010.
R. Iyer and J. Bilmes, Submodular optimization with submodular cover and submodular knapsack constraints, in Proc. of the 26th International Conference on Neural Information Processing Systems, Lake Tahoe, UV, USA, pp. 2436–2444, 2013.
A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek, Guarantees for greedy maximization of non-submodular functions with applications, in Proc. 34th Int. Conf. Machine Learning, Sydney, Australia, 2017, pp. 498–507.
T. Friedrich, A. Göbel, F. Neumann, F. Quinzan, and R. Rothenberger, Greedy maximization of functions with bounded curvature under partition matroid constraints, in Proc. 33rd AAAI Conf. Artificial Intelligence, Honolulu, HI, USA, 2019, p. 281.
S. Gong, Q. Nong, W. Liu, and Q. Fang, Parametric monotone function maximization with matroid constraints, J. Glob. Optim., vol. 75, no. 3, pp. 833–849, 2019.
A. Kuhnle, J. D. Smith, V. G. Crawford, and M. T. Thai, Fast maximization of non-submodular, monotonic functions on the integer lattice, in Proc. 35th Int. Conf. Machine Learning, Stockholm, Sweden, 2018, pp. 2791–2800.
C. Harshaw, M. Feldman, J. Ward, and A. Karbasi, Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications, in Proc. 36th Int. Conf. Machine Learning, Long Beach, CA, USA, 2019, pp. 2634–2643.
C. Qian, Multi-objective evolutionary algorithms are still good: Maximizing monotone approximately submodular minus modular functions, arXiv preprint arXiv: 1910.05492, 2019.
A. Norouzi-Fard, A. Bazzi, M. El Halabi, I. Bogunovic, Y. P. Hsieh, and V. Cevher, An efficient streaming algorithm for the submodular cover problem, in Proc. 30th Int. Conf. on Neural Information Processing Systems, Barcelona, Spain, 2016, pp. 4500–4508.
B. Lehmann, D. Lehmann, and N. Nisan, Combinatorial auctions with decreasing marginal utilities, Games Econ. Behav., vol. 55, no. 2, pp. 270–296, 2006.
Y. Wang, D. Du, D, Y. Jiang, and X. Zhang, Non-submodular maximization with matroid and knapsack constraints, Asia-Pacific Journal of Operational Research, vol. 38, no, 5, p. 2140001, 2021.
Wang Y, Yang X, Zhang H, et al. Bicriteria Algorithms for Approximately Submodular Cover Under Streaming Model. Tsinghua Science and Technology, 2023, 28(6): 1030-1040. https://doi.org/10.26599/TST.2022.9010061
The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
