期刊
APPLIED MATHEMATICS AND COMPUTATION
卷 410, 期 -, 页码 -出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.amc.2021.126442
关键词
Greedy algorithm; Submodular function; Submodular cover; Approximation ratio
The extension of Minimum Submodular Cover problem to non-submodular potential functions, along with the investigation of Minimum Non-submodular Cover problem with integer-valued and fraction valued potential functions, yield similar performance results. The paper also addresses several real-world applications that can be formulated as Minimum Nonsubmodular Cover problem.
Minimum Submodular Cover problem often occurs naturally in the context of combinatorial optimization. It is well-known that the greedy algorithm achieves an H(delta)- approximation guarantee for an integer-valued polymatroid potential function f, where delta is the maximum value of f over all singletons and H(delta) is the delta-th harmonic number. In this paper, we extend the setting into the non-submodular potential functions and investigate Minimum Non-submodular Cover problem with integer-valued and fraction valued potential functions respectively, yielding similar performance results. In addition, we address several real-world applications which can be formulated as Minimum Nonsubmodular Cover problem. (C) 2021 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据