A 6/5-approximation algorithm for the maximum 3-cover problem

被引:0
作者
Ioannis Caragiannis
Gianpiero Monaco
机构
[1] University of Patras,Research Academic Computer Technology Institute & Department of Computer Engineering and Informatics
[2] University of L’Aquila,Department of Computer Science
来源
Journal of Combinatorial Optimization | 2013年 / 25卷
关键词
Maximum cover; Set packing; Approximation algorithms; Local search;
D O I
暂无
中图分类号
学科分类号
摘要
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.
引用
收藏
页码:60 / 77
页数:17
相关论文
共 22 条
  • [1] Ageev AA(2004)Pipage rounding: a new method of constructing algorithms with proven performance guarantee J Comb Optim 8 307-328
  • [2] Sviridenko M(2009)Analysis of approximation algorithms for Theory Comput Syst 45 555-576
  • [3] Athanassopoulos S(2009)-set cover using factor-revealing linear programs SIAM J Discrete Math 23 959-978
  • [4] Caragiannis I(2006)Wavelength management in WDM rings to maximize the number of connections Theor Comput Sci 354 320-338
  • [5] Kaklamanis C(1977)Complexity of approximating bounded variants of optimization problems Manag Sci 23 789-810
  • [6] Caragiannis I(1998)Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms J ACM 45 634-652
  • [7] Chlebík M(2004)A threshold of ln J Algorithms 53 55-84
  • [8] Chlebíkova J(2006) for approximating set cover Comput Complex 15 20-39
  • [9] Cornuejols G(1989)Approximation algorithms for partial covering problems SIAM J Discrete Math 2 68-72
  • [10] Fisher ML(1991)On the complexity of approximating Inf Process Lett 37 27-35