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

Author:

Zhang, Zhenning (Zhang, Zhenning.) | Liu, Bin (Liu, Bin.) | Wang, Yishui (Wang, Yishui.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川) | Zhang, Dongmei (Zhang, Dongmei.)

Indexed by:

EI Scopus SCIE

Abstract:

Submodular optimization has been well studied in combinatorial optimization. However, there are few works considering about non-submodular optimization problems which also have many applications, such as experimental design, some optimization problems in social networks, etc. In this paper, we consider the maximization of non-submodular function under a knapsack constraint, and explore the performance of the greedy algorithm, which is characterized by the submodularity ratio beta and curvature alpha. In particular, we prove that the greedy algorithm enjoys a tight approximation guarantee of (1 - e(-alpha beta))/alpha for the above problem. To our knowledge, it is the first tight constant factor for this problem. We further utilize illustrative examples to demonstrate the performance of our algorithm.

Keyword:

Curvature Non-submodular Knapsack constraint Diminishing-return ratio Submodularity ratio

Author Community:

  • [ 1 ] [Zhang, Zhenning]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 2 ] [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 3 ] [Liu, Bin]Ocean Univ China, Sch Math Sci, Qingdao 266100, Peoples R China
  • [ 4 ] [Wang, Yishui]Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen 518055, Peoples R China
  • [ 5 ] [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China

Reprint Author's Address:

  • [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China

Show more details

Related Keywords:

Related Article:

Source :

JOURNAL OF COMBINATORIAL OPTIMIZATION

ISSN: 1382-6905

Year: 2020

Issue: 5

Volume: 43

Page: 1125-1148

1 . 0 0 0

JCR@2022

ESI Discipline: MATHEMATICS;

ESI HC Threshold:46

Cited Count:

WoS CC Cited Count: 2

SCOPUS Cited Count: 2

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 4

Affiliated Colleges:

Online/Total:677/10645059
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.