Indexed by:
Abstract:
In this work, we investigate the problem that maximizes a weakly k-submodular function under the matroid constraint. Different from traditional submodular function maximization, there are k disjoint subsets in k-submodular function optimization, instead of a single set in the submodular maximization. For the weakly k-submodular maximization problem, we provide a greedy algorithm whose approximation ratio is alpha/(1 + alpha), where parameter 0 < alpha <= 1 is the orthant submodularity ratio. Then we extend to cardinality constraint which maintains the same performance ratio.
Keyword:
Reprint Author's Address:
Email:
Source :
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2022
ISSN: 0302-9743
Year: 2022
Volume: 13571
Page: 393-401
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: 11
Affiliated Colleges: