Indexed by:
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:
Reprint Author's Address:
Email:
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: