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

Author:

Cui, Min (Cui, Min.) | Du, Donglei (Du, Donglei.) | Gai, Ling (Gai, Ling.) | Yang, Ruiqi (Yang, Ruiqi.)

Indexed by:

CPCI-S EI Scopus

Abstract:

Nowadays, massive amounts of data are growing at a rapid rate every moment. If data can be processed and analyzed promptly as they arrive, they can bring huge added values to the society. In this paper, we consider the problem of maximizing a monotone non-submodular function subject to a cardinality constraint under the streaming setting and present a linear-time single-pass deterministic algorithm for this problem. We analyze the algorithm using the parameter of the generic submodularity ratio gamma to achieve an approximation ratio of [gamma(4)/c(1+gamma+gamma(2)+gamma(3)) - epsilon] for any epsilon >= 0 with the query complexity [n/c] + c, and the memory complexity is O(ck log(k) log(1/epsilon)), where c is a positive integer. When gamma = 1, the algorithm achieves the same ratio for the submodular version of the problem with the matching query complexity and memory complexity.

Keyword:

Cardinality-constrained Non-submodular Linear-time Streaming

Author Community:

  • [ 1 ] [Cui, Min]Beijing Univ Technol, Dept Operat Res & Informat Engn, 100 Pingleyuan, Beijing 100124, Peoples R China
  • [ 2 ] [Du, Donglei]Univ New Brunswick, Fac Management, Fredericton, NB E3B 5A3, Canada
  • [ 3 ] [Gai, Ling]Donghua Univ, Glorious Sun Sch Business & Management, Shanghai 200051, Peoples R China
  • [ 4 ] [Yang, Ruiqi]Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, 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: 96-110

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

Affiliated Colleges:

Online/Total:1255/10692763
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.