检索结果-内蒙古大学图书馆

An approximation algorithm for the K -prize-collecting multicut problem in trees with submodular penalties

MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE 2024年第3期34卷 193-210页

作者： Liu, Xiaofei Li, Weidong Yunnan Univ Sch Informat Sci & Engn Kunming 650500 Peoples R China Yunnan Univ Sch Math & Stat Kunming Peoples R China

Let T=(V,E) be a tree in which each edge is assigned a cost;let P be a set of source-sink pairs of vertices in V in which each source-sink pair produces a profit. Given a lower bound K for the profit, the K-prize-collecting multicut problem in trees with submodular penalties is to determine a partial multicut M subset of E such that the total profit of the disconnected pairs after removing M from T is at least K, and the total cost of edges in M plus the penalty of the set of still-connected pairs is minimized, where the penalty is determined by a nondecreasing submodular function. Based on the primal-dual scheme, we present a combinatorial polynomial-time algorithm by carefully increasing the penalty. In the theoretical analysis, we prove that the approximation factor of the proposed algorithm is ((8)(3)+ K-4(3 )+epsilon) , where K is the total curvature of the submodular function and epsilon is any fixed positive number. Experiments reveal that the objective value of the solutions generated by the proposed algorithm is less than 130% compared with that of the optimal value in most cases.

关键词： multicut problem in trees with submodular penalties K prize collecting approximation algorithm primal-dual scheme

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：