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

Author:

Zhang, Zhen-Ning (Zhang, Zhen-Ning.) | Du, Dong-Lei (Du, Dong-Lei.) | Ma, Ran (Ma, Ran.) | Wu, Dan (Wu, Dan.)

Indexed by:

EI Scopus

Abstract:

In this paper, we investigate the maximization of the differences between a non-negative monotone diminishing return submodular (DR-submodular) function and a nonnegative linear function on the integer lattice. As it is almost unapproximable for maximizing a submodular function without the condition of nonnegative, we provide weak (bifactor) approximation algorithms for this problem in two online settings, respectively. For the unconstrained online model, we combine the ideas of single-threshold greedy, binary search and function scaling to give an efficient algorithm with a 1/2 weak approximation ratio. For the online streaming model subject to a cardinality constraint, we provide a one-pass (3 - root 5 )/2 weak approximation ratio streaming algorithm. Its memory complexity is (k log k/epsilon), and the update time for per element is (log(2) k/epsilon).

Keyword:

Streaming algorithm Submodular maximization Single-threshold greedy algorithm DR-submodular Integer lattice

Author Community:

  • [ 1 ] [Zhang, Zhen-Ning]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 2 ] [Du, Dong-Lei]Univ New Brunswick, Fac Management, Fredericton, NB E3B 9Y2, Canada
  • [ 3 ] [Ma, Ran]Qingdao Univ Technol, Sch Management Engn, Qingdao 266525, Shandong, Peoples R China
  • [ 4 ] [Wu, Dan]Henan Univ Sci & Technol, Sch Math & Stat, Luoyang 471023, Henan, Peoples R China

Reprint Author's Address:

Show more details

Related Keywords:

Source :

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA

ISSN: 2194-668X

Year: 2022

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count: 1

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 7

Affiliated Colleges:

Online/Total:1039/10620025
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.