• 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

Abstract:

We consider a two-stage submodular maximization under pmatroid (or p-extendible) constraints. In the model, we are given a collection of submodular functions and some p-matroid (or extendible) system constraints for each of these functions, one need to choose a representative set with a cardinality constraint and simultaneously select a series of subsets that are restricted to the representative set for all functions, the aim is to maximize the average of the summarization of these function values. We extend the two-stage submodular maximization under single matroid to handle p-matroid (or p-extendible) constraints, and derive constant approximation ratio algorithms for the two problems, respectively. In the end, we empirically demonstrate the efficiency of our method on some datasets.

Keyword:

Submodular maximization Approximation algorithms Independence system constraints

Author Community:

  • [ 1 ] [Yang, Ruiqi]Beijing Univ Technol, Dept Operat Res & Sci Comp, Beijing 100124, Peoples R China
  • [ 2 ] [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Sci Comp, Beijing 100124, Peoples R China
  • [ 3 ] [Gu, Shuyang]Univ Texas Dallas, Dept Comp Sci, Richardson, TX 75080 USA
  • [ 4 ] [Wu, Weili]Univ Texas Dallas, Dept Comp Sci, Richardson, TX 75080 USA
  • [ 5 ] [Gao, Chuangen]Shandong Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China
  • [ 6 ] [Wang, Hua]Shandong Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China

Reprint Author's Address:

  • 徐大川

    [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Sci Comp, Beijing 100124, Peoples R China

Show more details

Related Keywords:

Related Article:

Source :

ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, AAIM 2019

ISSN: 0302-9743

Year: 2019

Volume: 11640

Page: 329-340

Language: English

Cited Count:

WoS CC Cited Count: 1

SCOPUS Cited Count: 1

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 4

Affiliated Colleges:

Online/Total:552/10637886
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.