• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Sun, Xiaoming (Sun, Xiaoming.) [1] | Zhang, Jialin (Zhang, Jialin.) [2] | Zhang, Shuo (Zhang, Shuo.) [3] | Zhang, Zhijie (Zhang, Zhijie.) [4]

Indexed by:

EI

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−o(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. © 2023 Elsevier B.V.

Keyword:

Approximation algorithms Combinatorial optimization

Community:

  • [ 1 ] [Sun, Xiaoming]State Key Lab of Processors, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China
  • [ 2 ] [Sun, Xiaoming]School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing, China
  • [ 3 ] [Zhang, Jialin]State Key Lab of Processors, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China
  • [ 4 ] [Zhang, Jialin]School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing, China
  • [ 5 ] [Zhang, Shuo]State Key Lab of Processors, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China
  • [ 6 ] [Zhang, Shuo]School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing, China
  • [ 7 ] [Zhang, Zhijie]Center for Applied Mathematics of Fujian Province, School of Mathematics and Statistics, Fuzhou University, Fuzhou, China

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

Theoretical Computer Science

ISSN: 0304-3975

Year: 2024

Volume: 984

0 . 9 0 0

JCR@2023

Cited Count:

WoS CC Cited Count:

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:

Online/Total:69/10134796
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1