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

Author:

Yang, Ruiqi (Yang, Ruiqi.) | Gu, Shuyang (Gu, Shuyang.) | Gao, Chuangen (Gao, Chuangen.) | Wu, Weili (Wu, Weili.) | Wang, Hua (Wang, Hua.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川)

Indexed by:

CPCI-S EI Scopus SCIE

Abstract:

In this paper, we investigate the two-stage submodular maximization problem, where there is a collection F={f1,…,fm} of m submodular functions which are defined on the same element ground set Ω. The goal is to select a subset S⊆Ω of size at most such that [Formula presented] is maximized, where I denotes a specifically-defined independence system. We consider the two-stage submodular maximization with a P-matroid constraint and present a (1/(P+1))(1−1/e(P+1))-approximation algorithm. Furthermore, we extend the algorithm to the two-stage submodular maximization with a more generalized P-exchange system constraint and show the approximation ratio can be maintained with slightly modifications of the algorithm. © 2020 Elsevier B.V.

Keyword:

Computational methods Computer science Approximation algorithms

Author Community:

  • [ 1 ] [Yang, Ruiqi]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
  • [ 2 ] [Gu, Shuyang]Department of Computer Science, University of Texas at Dallas, TX; 75080, United States
  • [ 3 ] [Gao, Chuangen]School of Computer Science and Technology, Shandong University, Jinan; 250101, China
  • [ 4 ] [Wu, Weili]Department of Computer Science, University of Texas at Dallas, TX; 75080, United States
  • [ 5 ] [Wang, Hua]School of Computer Science and Technology, Shandong University, Jinan; 250101, China
  • [ 6 ] [Xu, Dachuan]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China

Reprint Author's Address:

  • 徐大川

    [xu, dachuan]department of operations research and information engineering, beijing university of technology, beijing; 100124, china

Show more details

Related Keywords:

Related Article:

Source :

Theoretical Computer Science

ISSN: 0304-3975

Year: 2021

Volume: 853

Page: 57-64

1 . 1 0 0

JCR@2022

ESI Discipline: COMPUTER SCIENCE;

ESI HC Threshold:87

JCR Journal Grade:4

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count: 11

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 9

Affiliated Colleges:

Online/Total:1135/10634599
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.