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

Author:

Sun, Xin (Sun, Xin.) | Xu, Dachuan (Xu, Dachuan.) | Zhang, Dongmei (Zhang, Dongmei.) | Zhou, Yang (Zhou, Yang.)

Indexed by:

EI Scopus

Abstract:

In this paper, we consider the problem of maximizing a non-submodular set function subject to a matroid constraint with the continuous generic submodularity ratio γ. It quantifies how close a monotone function is to being submodular. As our main contribution, we propose a (1-e-γ2-O(Ε)) -approximation algorithm when the submodularity ratio is sufficiently large. Our work also can be seen as the first extension of the adaptive sequencing technique in non-submodular case. © 2020, Springer Nature Switzerland AG.

Keyword:

Combinatorial optimization Approximation algorithms Adaptive algorithms

Author Community:

  • [ 1 ] [Sun, Xin]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
  • [ 2 ] [Xu, Dachuan]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
  • [ 3 ] [Zhang, Dongmei]School of Computer Science and Technology, Shandong Jianzhu University, Jinan; 250101, China
  • [ 4 ] [Zhou, Yang]School of Mathematics and Statistics, Shandong Normal University, Jinan; 250014, China

Reprint Author's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

ISSN: 0302-9743

Year: 2020

Volume: 12575 LNCS

Page: 3-13

Language: English

Cited Count:

WoS CC Cited Count: 0

SCOPUS Cited Count: 1

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 3

Affiliated Colleges:

Online/Total:681/10645394
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.