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

author:

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

Indexed by:

EI Scopus

Abstract:

Submodular maximization has been a central topic in theoretical computer science and combinatorial optimization over the last decades. Plenty of well-performed approximation algorithms have been designed for the problem over a variety of constraints. In this paper, we consider the submodular multiple knapsack problem (SMKP). In SMKP, the profits of each subset of elements are specified by a monotone submodular function. The goal is to find a feasible packing of elements over multiple bins (knapsacks) to maximize the profit. Recently, Fairstein et al. [ESA20] proposed a nearly optimal (1 − e−1 − )-approximation algorithm for SMKP. Their algorithm is obtained by combining configuration LP, a grouping technique for bin packing, and the continuous greedy algorithm for submodular maximization. As a result, the algorithm is somewhat sophisticated and inherently randomized. In this paper, we present an arguably simple deterministic combinatorial algorithm for SMKP, which achieves a (1 − e−1 − )-approximation ratio. Our algorithm is based on very different ideas compared with Fairstein et al. [ESA20]. © Xiaoming Sun, Jialin Zhang, and Zhijie Zhang;

Keyword:

Approximation algorithms Combinatorial optimization Profitability

Community:

  • [ 1 ] [Sun, Xiaoming]Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China
  • [ 2 ] [Zhang, Jialin]University of Chinese Academy of Sciences, Beijing, China
  • [ 3 ] [Zhang, Zhijie]Center for Applied Mathematics of Fujian Province, School of Mathematics and Statistics, Fuzhou University, China

Reprint 's Address:

Email:

Show more details

Version:

Related Keywords:

Related Article:

Source :

ISSN: 1868-8969

Year: 2023

Volume: 274

Language: English

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:98/10119121
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