首页 | 本学科首页   官方微博 | 高级检索  
     


A 6/5-approximation algorithm for the maximum 3-cover problem
Authors:Ioannis Caragiannis  Gianpiero Monaco
Affiliation:1. Research Academic Computer Technology Institute & Department of Computer Engineering and Informatics, University of Patras, 26500, Rio, Greece
2. Department of Computer Science, University of L’Aquila, Via Vetoio, Coppito, 67100, L’Aquila, Italy
Abstract:
In the maximum cover problem, we are given a collection of sets over a ground set of elements and a positive integer w, and we are asked to compute a collection of at most w sets whose union contains the maximum number of elements from the ground set. This is a fundamental combinatorial optimization problem with applications to resource allocation. We study the simplest APX-hard variant of the problem where all sets are of size at most 3 and we present a 6/5-approximation algorithm, improving the previously best known approximation guarantee. Our algorithm is based on the idea of first computing a large packing of disjoint sets of size 3 and then augmenting it by performing simple local improvements.
Keywords:
本文献已被 SpringerLink 等数据库收录!
正在获取相似文献,请稍候...
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号