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

Author:

Tan, Jingjing (Tan, Jingjing.) | Wang, Fengmin (Wang, Fengmin.) | Zhang, Xiaoqing (Zhang, Xiaoqing.) | Zhou, Yang (Zhou, Yang.)

Indexed by:

CPCI-S EI Scopus

Abstract:

The problem of submodular maximization on the integer lattice has attracted more and more attention due to its deeply applications in many areas. In this paper, we consider maximizing a non-negative monotone non-submodular function with knapsack constraint on massive data. We combine two proposed algorithms called StreamingKnapsack and BinarySearch for this problem by introducing the DR ratio gamma(d) and the weak DR ratio gamma(w) of the non-submodular objective function. Finally, we obtain the performance guarantee of the StreamingKnapsack supplemented by a simple one-pass algorithm, with the approximation ratio of the better output of them as min{gamma(2)(d)(1 - epsilon)/2(gamma d+1), 1 - 1/gamma(w)2(gamma d) - epsilon}. Meanwhile, both the time complexity and space complexity are dependent on the size of knapsack capacity K and epsilon is an element of (0, 1).

Keyword:

Streaming algorithm Knapsack constraint Non-submodular Integer lattice

Author Community:

  • [ 1 ] [Tan, Jingjing]Weifang Univ, Sch Math & Informat Sci, Weifang 261061, Peoples R China
  • [ 2 ] [Wang, Fengmin]Beijing Jinghang Res Inst Comp & Commun, Beijing 100074, Peoples R China
  • [ 3 ] [Zhang, Xiaoqing]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 4 ] [Zhou, Yang]Shandong Normal Univ, Sch Math & Stat, Jinan 250014, Peoples R China

Reprint Author's Address:

Show more details

Related Keywords:

Source :

COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2021

ISSN: 0302-9743

Year: 2021

Volume: 13135

Page: 364-373

Cited Count:

WoS CC Cited Count: 0

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 7

Affiliated Colleges:

Online/Total:692/10700075
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.