Indexed by:
Abstract:
Utilizing approximation algorithm, there has been a large quantity of work on optimization for submodular functions since the 1970s. As a variant, k-submodular function appears in many fields to match with the developing background, in which the outputted sets changes from one to k. Because of the application of submodularity, some concepts and parameters describing the closeness to submodular function are generated, for example approximately submodular set function and diminishing-return (DR) ratio. In our discussion, the k-dimension set function with matroid constraint we will maximize may not have access to the submodularity. However it is an approximately non-k-submodular set function which contains DR ratio. By the greedy technique, we obtain the approximation algorithms. When the value of the DR ratio is set one, some known results are covered.
Keyword:
Reprint Author's Address:
Email:
Source :
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2022
ISSN: 0302-9743
Year: 2022
Volume: 13571
Page: 11-20
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 6
Affiliated Colleges: