中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Improved deterministic algorithms for non-monotone submodular maximization

文献类型：期刊论文

作者Sun, Xiaoming2,3; Zhang, Jialin2,3; Zhang, Shuo2,3; Zhang, Zhijie1
刊名THEORETICAL COMPUTER SCIENCE
出版日期2024-02-12
卷号984页码:17
关键词Submodular maximization Deterministic algorithms Derandomization Twin greedy Multiplicative updates
ISSN号0304-3975
DOI10.1016/j.tcs.2023.114293
英文摘要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.
资助项目National Natural Science Foundation of China[62325210] ; National Natural Science Foundation of China[62272441]
WOS研究方向Computer Science
语种英语
WOS记录号WOS:001133492900001
出版者ELSEVIER
源URL[http://119.78.100.204/handle/2XEOYT63/38481]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Zhang, Zhijie
作者单位1.Fuzhou Univ, Ctr Appl Math Fujian Prov, Sch Math & Stat, Fuzhou, Peoples R China
2.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing, Peoples R China
3.Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing, Peoples R China
推荐引用方式
GB/T 7714		 Sun, Xiaoming,Zhang, Jialin,Zhang, Shuo,et al. Improved deterministic algorithms for non-monotone submodular maximization[J]. THEORETICAL COMPUTER SCIENCE,2024,984:17.
APA Sun, Xiaoming,Zhang, Jialin,Zhang, Shuo,&Zhang, Zhijie.(2024).Improved deterministic algorithms for non-monotone submodular maximization.THEORETICAL COMPUTER SCIENCE,984,17.
MLA Sun, Xiaoming,et al."Improved deterministic algorithms for non-monotone submodular maximization".THEORETICAL COMPUTER SCIENCE 984(2024):17.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。