Utilizing approximation algorithm, there has been a large quantity of work on optimization for submodularfunctions since the 1970s. As a variant, k-submodularfunction appears in many fields to match with the develop...
详细信息
ISBN:
(纸本)9783031203497;9783031203503
Utilizing approximation algorithm, there has been a large quantity of work on optimization for submodularfunctions since the 1970s. As a variant, k-submodularfunction 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 submodularfunction are generated, for example approximately submodularsetfunction and diminishing-return (DR) ratio. In our discussion, the k-dimension setfunction 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.
暂无评论