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

Efficient approximation algorithms for maximum coverage with group budget constraints

THEORETICAL COMPUTER SCIENCE 2019年 788卷 53-65页

作者： Guo, Longkun Li, Min Xu, Dachuan Fuzhou Univ Coll Math & Comp Sci Fuzhou 350116 Fujian Peoples R China Shandong Normal Univ Sch Math & Stat Jinan 250014 Shandong Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China

Given a ground set U with a non -negative weight wi for each i E U, a positive integer k and a collection of sets 8, which is partitioned into a family of disjoint groups g. the goal of the Maximum Coverage problem with Group budget constraints (MCG) is to select k sets from S, such that the total weight of the union of the k sets is maximized and at most one set is selected from each group Q E We first present an approximation algorithm with a factor 1 a and an exponential time via randomized linear programming rounding technique. Then we improve the time complexity of the algorithm to 0((m + n)3.5L + k3.5q7L) for ISM = m, IU I = n, and L being the length of the input, by the key idea of modeling the selection of groups as computing a constrained flow in a corresponding auxiliary graph. The algorithm is later shown can be extended to solve two generalizations of MCG. Last but not the least, we present another algorithm with a time complexity 0 ((m +n)3.5L +1(81.5L) and a slightly increased approximation ratio 1 ei-1 mainly based on the idea of partition, where iS > 2 is a parameter tuning which can balance the time complexity and the ratio. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Maximum coverage problem with group budget constraints Approximation algorithm Auxiliary graph Network flow randomized linear programming rounding

来源：评论

学校读者我要写书评

暂无评论

Approximation Algorithms for Maximum Coverage with Group Budget Constraints 11th

Approximation Algorithms for Maximum Coverage with Group Bud...

引用

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

作者： Guo, Longkun Li, Min Xu, Dachuan Fuzhou Univ Coll Math & Comp Sci Fuzhou 350116 Peoples R China Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China Beijing Univ Technol Coll Appl Sci Beijing 100124 Peoples R China

ISBN: (纸本)9783319711478;9783319711461

In this paper, we study the maximum coverage problem with group budget constraints (MCG) that generalizes the maximum coverage problem. Given a ground set U in which i E U has a non-negative weight w,, a positive integer k and a collection of sets S, the maximum coverage problem is to pick k sets of S to maximize the total weight of their union. In MCG, S is partitioned into groups g1,, c and the goal is to pick k sets from S to maximize the total weight of their union, with at most ni E Z sets being picked from group ci. For MCG with n,/ = 1, Vi, we first present a factor 1 eapproximation algorithm which runs in exponential time. Then we improve the runtime of the algorithm to 0 ( (m n q)3.5 L k3.5 q7 L) where 1,51 = m, =12, q is the number of groups, and L is the length of the input. The key idea of the improvement is to model selecting groups for MCG as computing a constrained flow in a corresponding auxiliary graph. It is also shown that the algorithm can be extended to solve MCG with general ni. Later, based on the main idea of partition we further improve the runtime of the algorithm to 0((m n q)3.5 L k(51.5 L), while compromise the approximation ratio to 1 e+-5-1, where (5 > 2 is any fixed integer. Consequently, we can balance approximation ratio and runtime of the algorithm by setting the value of S. This improves the previous best ratio of 0.5 on MCG due to Chekuri and Kumar [4].

关键词： Maximum coverage problem with group budget constraints Approximation algorithm Auxiliary graph Network flow randomized linear programming rounding Partition

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：