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

Author:

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

Indexed by:

EI Scopus SCIE

Abstract:

The study of non-submodular maximization on the integer lattice is an important extension of submodular optimization. In this paper, streaming algorithms for maximizing non -negative monotone non-submodular functions with knapsack constraint on integer lattice are considered. We first design a two-pass StreamingKnapsack algorithm combining with BinarySearch as a subroutine for this problem. By introducing the DR ratio gamma and the weak DR ratio gamma w of the non-submodular objective function, we obtain that the approximation ratio is min{gamma 2(1 - epsilon)/2 gamma +1, 1 - 1/gamma w2 gamma - epsilon}, the total memory complexity is O (K log K /epsilon), and the total query complexity for each element is O (log K log(K/epsilon 2)/epsilon). Then, we design a one-pass streaming algorithm by dynamically updating the maximal function value among unit vectors along with the currently arriving element. Finally, in order to decrease the memory complexity, we design an improved StreamingKnapsack algorithm and reduce the memory complexity to O (K /epsilon 2).(c) 2022 Elsevier B.V. All rights reserved.

Keyword:

Knapsack constraint Non-submodular Integer lattice Streaming algorithms

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 ] [Ye, Weina]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 4 ] [Zhang, Xiaoqing]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 5 ] [Zhou, Yang]Shandong Normal Univ, Sch Math & Stat, Jinan 250014, Peoples R China

Reprint Author's Address:

Show more details

Related Keywords:

Source :

THEORETICAL COMPUTER SCIENCE

ISSN: 0304-3975

Year: 2022

Volume: 937

Page: 39-49

1 . 1

JCR@2022

1 . 1 0 0

JCR@2022

ESI Discipline: COMPUTER SCIENCE;

ESI HC Threshold:46

JCR Journal Grade:4

CAS Journal Grade:4

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: 2

Affiliated Colleges:

Online/Total:651/10700012
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.