Open Access
Issue
Published:
*28 July 2023*

Cite this article:

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
Download citation

114

Views

18

Downloads

Citations

0

Crossref

0

WoS

0

Scopus

0

CSCD

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

menu

Abstract

Full text

Outline

About this article

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

[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.

[2]

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.

[3]

A. Das and D. Kempe, Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection, in *Proc. 28*^{th} Int. Conf. Int. Conf. Machine Learning, Bellevue, WA, USA, 2011, pp. 1057–1064.

[4]

J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, Cost-effective outbreak detection in networks, in *Proc. 13*^{th} ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, San Jose, CA, USA, 2007, pp. 420–429.

[5]

D. Kempe, J. Kleinberg, and É. Tardos, Maximizing the spread of influence through a social network, in *Proc. 9*^{th} ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Washington, DC, USA, 2003, pp. 137–146.

[6]

V. G. Crawford, A. Kuhnle, and M. T. Thai, Submodular cost submodular cover with an approximate oracle, in *Proc. 36*^{th} Int. Conf. Machine Learning, Long Beach, CA, USA, 2019, pp. 1426–1435.

[7]

L. A. Wolsey, An analysis of the greedy algorithm for the submodular set covering problem, *Combinatorica*, vol. 2, no. 4, pp. 385–393, 1982.

[8]

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.

[9]

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.

[10]

A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek, Guarantees for greedy maximization of non-submodular functions with applications, in *Proc. 34*^{th} Int. Conf. Machine Learning, Sydney, Australia, 2017, pp. 498–507.

[11]

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. 33*^{rd} AAAI Conf. Artificial Intelligence, Honolulu, HI, USA, 2019, p. 281.

[12]

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.

[13]

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. 35*^{th} Int. Conf. Machine Learning, Stockholm, Sweden, 2018, pp. 2791–2800.

[14]

C. Harshaw, M. Feldman, J. Ward, and A. Karbasi, Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications, in *Proc. 36*^{th} Int. Conf. Machine Learning, Long Beach, CA, USA, 2019, pp. 2634–2643.

[15]

C. Qian, Multi-objective evolutionary algorithms are still good: Maximizing monotone approximately submodular minus modular functions, arXiv preprint arXiv: 1910.05492, 2019.

[16]

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. 30*^{th} Int. Conf. on Neural Information Processing Systems, Barcelona, Spain, 2016, pp. 4500–4508.

[17]

B. Lehmann, D. Lehmann, and N. Nisan, Combinatorial auctions with decreasing marginal utilities, *Games Econ. Behav.*, vol. 55, no. 2, pp. 270–296, 2006.

[18]

U. Feige, V. S. Mirrokni, and J. Vondrák, Maximizing non-monotone submodular functions, *SIAM J. Comput.*, vol. 40, no. 4, pp. 1133–1153, 2011.

[19]

V. G. Crawford, Scalable bicriteria algorithms for non-monotone submodular cover, arXiv preprint arXiv: 2112.09985, 2021.

[20]

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.

Publication history

Copyright

Acknowledgements

Rights and permissions

Received: 02 August 2022

Revised: 24 October 2022

Accepted: 28 November 2022

Published:
28 July 2023

Issue date: December 2023

© The author(s) 2023.

This work was supported by the National Natural Science Foundation of China (Nos. 72192804, 72192800, and 12201619) and the China Postdoctoral Science Foundation (No. 2022M723333).

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/).