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

Author:

Wang, Yijing (Wang, Yijing.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川) | Wang, Yishui (Wang, Yishui.) | Zhang, Dongmei (Zhang, Dongmei.)

Indexed by:

EI Scopus SCIE

Abstract:

The problem of maximizing a normalized monotone non-submodular set function subject to a cardinality constraint arises in the context of extracting information from massive streaming data. In this paper, we present four streaming algorithms for this problem by utilizing the concept of diminishing-return ratio. We analyze these algorithms to obtain the corresponding approximation ratios, which generalize the previous results for the submodular case. The numerical experiments show that our algorithms have better solution quality and competitive running time when compared to an existing algorithm.

Keyword:

Set function Cardinality constraint Streaming algorithm Non-submodular maximization

Author Community:

  • [ 1 ] [Wang, Yijing]Beijing Univ Technol, Coll Appl Sci, Beijing 100124, Peoples R China
  • [ 2 ] [Xu, Dachuan]Beijing Univ Technol, Coll Appl Sci, Beijing 100124, Peoples R China
  • [ 3 ] [Wang, Yishui]Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen 518055, Peoples R China
  • [ 4 ] [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Shandong, Peoples R China

Reprint Author's Address:

  • [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Shandong, Peoples R China

Show more details

Related Keywords:

Source :

JOURNAL OF GLOBAL OPTIMIZATION

ISSN: 0925-5001

Year: 2019

Issue: 4

Volume: 76

Page: 729-743

1 . 8 0 0

JCR@2022

ESI Discipline: ENGINEERING;

ESI HC Threshold:136

JCR Journal Grade:1

Cited Count:

WoS CC Cited Count: 25

SCOPUS Cited Count: 29

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 5

Affiliated Colleges:

Online/Total:708/10700735
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.