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

Author:

Sun, Xin (Sun, Xin.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川) | Zhang, Dongmei (Zhang, Dongmei.) | Zhou, Yang (Zhou, Yang.)

Indexed by:

EI Scopus SCIE

Abstract:

In the paper, we design an adaptive algorithm for non-submodular set function maximization over a single matroid constraint. We measure the deviation of the set function from fully submodular with the help of the generic submodularity ratio gamma. The adaptivity quantifies the information theoretic complexity of oracle optimization for parallel computations. We propose a new approximation algorithm based on the continuous greedy approach and prove that the algorithm could obtain a fractional solution with approximation ratio (1 - e(-gamma 2) - O(epsilon)) in O(log n log(k/gamma epsilon)/epsilon(-2) log n log(1/gamma) - epsilon(-1) log(1-epsilon)) then use the contention resolution schemes to convert the fractional solution to a discrete one with gamma (1 - e(-1))(1 - e(-gamma 2) - O(epsilon))-approximation.

Keyword:

generic submodularity ratio Approximation algorithm matroid constraints non-submodular adaptivity

Author Community:

  • [ 1 ] [Sun, Xin]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 2 ] [Xu, Dachuan]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 3 ] [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China
  • [ 4 ] [Zhou, Yang]Shandong Normal Univ, Sch Math & Stat, Jinan 250014, Peoples R China

Reprint Author's Address:

  • [Zhou, Yang]Shandong Normal Univ, Sch Math & Stat, Jinan 250014, Peoples R China;;

Show more details

Related Keywords:

Related Article:

Source :

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION

ISSN: 1547-5816

Year: 2022

Issue: 3

Volume: 19

Page: 2050-2070

1 . 3

JCR@2022

1 . 3 0 0

JCR@2022

ESI Discipline: ENGINEERING;

ESI HC Threshold:49

JCR Journal Grade:4

CAS Journal Grade:4

Cited Count:

WoS CC Cited Count: 1

SCOPUS Cited Count: 1

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 12

Affiliated Colleges:

Online/Total:148/10662722
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.