• 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] (Scholars:张智杰)

Indexed by:

EI Scopus SCIE

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:

Derandomization Deterministic algorithms Multiplicative updates Submodular maximization Twin greedy

Community:

  • [ 1 ] [Sun, Xiaoming]Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing, Peoples R China
  • [ 2 ] [Zhang, Jialin]Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing, Peoples R China
  • [ 3 ] [Zhang, Shuo]Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing, Peoples R China
  • [ 4 ] [Sun, Xiaoming]Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing, Peoples R China
  • [ 5 ] [Zhang, Jialin]Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing, Peoples R China
  • [ 6 ] [Zhang, Shuo]Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing, Peoples R China
  • [ 7 ] [Zhang, Zhijie]Fuzhou Univ, Ctr Appl Math Fujian Prov, Sch Math & Stat, Fuzhou, Peoples R China

Reprint 's Address:

  • [Zhang, Zhijie]Fuzhou Univ, Ctr Appl Math Fujian Prov, Sch Math & Stat, Fuzhou, Peoples R China;;

Show more details

Related Keywords:

Related Article:

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

Online/Total:108/10131314
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