Indexed by:
Abstract:
Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization.In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0.283 - ������(1) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1/6 - ������ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints.
Keyword:
Reprint 's Address:
Version:
Source :
THEORETICAL COMPUTER SCIENCE
ISSN: 0304-3975
Year: 2023
Volume: 984
0 . 9
JCR@2023
0 . 9 0 0
JCR@2023
JCR Journal Grade:3
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 1
SCOPUS Cited Count: 3
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: