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

Approximating k-forest with resource augmentation: A primal-dual approach

THEORETICAL COMPUTER SCIENCE 2019年 788卷 12-20页

作者： Angel, Eric Nguyen Kim Thang Singh, Shikha Univ Evry Val Essonne IBISC Evry France Wellesley Coll Wellesley MA 02181 USA

In this paper, we study the k-forest problem in the model of resource augmentation. In the k-forest problem, given an edge-weighted graph G (V, E), a parameter k, and a set of m demand pairs subset of V x V, the objective is to construct a minimum-cost subgraph that connects at least k demands. The problem is hard to approximate-the best-known approximation ratio is O(min{root vertical bar V vertical bar, root K}). Furthermore, k-forest is as hard to approximate as the notoriously-hard densest k-subgraph problem. While the k-forest problem is hard to approximate in the worst-case, we show that with the use of resource augmentation, we can efficiently approximate it up to a constant factor. First, we restate the problem in terms of the number of demands that are not connected. In particular, the objective of the k-forest problem can be viewed as to remove at most m - k demands and find a minimum-cost subgraph that connects the remaining demands. We use this perspective of the problem to explain the performance of our algorithm (in terms of the augmentation) in a more intuitive way. Specifically, we present a polynomial-time algorithm for the k-forest problem that, for every E > 0, removes at most m - k demands and has cost no more than O(1/epsilon(2)) times the cost of an optimal algorithm that removes at most (1 - epsilon)(m - k) demands. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Primal-dual algorithms Resource augmentation k-forest problem Approximation algorithms lp duality algorithms Optimization problems Prize-collecting generalized Steiner tree problem

来源：评论

学校读者我要写书评

暂无评论

Approximating k-forest with resource augmentation: A primal-dual approach 11th

Approximating k-forest with resource augmentation: A primal-...

引用

11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Angel, Eric Nguyen Kim Thang Singh, Shikha Univ Evry Val Essonne IBISC Evry France Wellesley Coll Wellesley MA 02181 USA

ISBN: (纸本)9783319711461

关键词： Primal-dual algorithms Resource augmentation k-forest problem Approximation algorithms lp duality algorithms Optimization problems Prize-collecting generalized Steiner tree problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：