Packing-based approximation algorithm for the k-set cover problem

DOI10.1007/978-3-642-25591-5_50MaRDI QIDQ3104644zbMATH OpenOpenAlexFDO

Authors Huiwen Yu, Martin Fürer

Publication date 16 December 2011

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.3418

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Abstract: We present a packing-based approximation algorithm for the $k$-Set Cover problem. We introduce a new local search-based $k$-set packing heuristic, and call it Restricted $k$-Set Packing. We analyze its tight approximation ratio via a complicated combinatorial argument. Equipped with the Restricted $k$-Set Packing algorithm, our $k$-Set Cover algorithm is composed of the $k$-Set Packing heuristic cite{schrijver} for $kgeq7$, Restricted $k$-Set Packing for $k=6,5,4$ and the semi-local $(2,1)$-improvement cite{furer} for 3-Set Cover. We show that our algorithm obtains a tight approximation ratio of $H_k-0.6402+Theta(frac1k)$, where $H_k$ is the $k$-th harmonic number. For small $k$, our results are 1.8667 for $k=6$, 1.7333 for $k=5$ and 1.5208 for $k=4$. Our algorithm improves the currently best approximation ratio for the $k$-Set Cover problem of any $kgeq4$.

Recommendations

• Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs
• Analysis of approximation algorithms for k-set cover using factor-revealing linear programs
• Approximating the k-set packing problem by local improvements
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• A new approximation algorithm for k-set cover problem

Cited in

(17)

• Upper bounds on the average number of iterations for some algorithms of solving the set packing problem
• Approximating k-set cover and complementary graph coloring
• scientific article; zbMATH DE number 4089565 (Why is no real title available?)
• A new approximation algorithm for k-set cover problem
• Learning generalized strong branching for set covering, set packing, and 0-1 knapsack problems
• Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints
• Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs
• Uniform unweighted set cover: the power of non-oblivious local search
• Approximating activation edge-cover and facility location problems
• Analysis of approximation algorithms for k-set cover using factor-revealing linear programs
• A 6/5-approximation algorithm for the maximum 3-cover problem
• Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints
• scientific article; zbMATH DE number 7561664 (Why is no real title available?)
• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
• Tight approximation bounds for combinatorial frugal coverage algorithms
• Approximation Schemes for Covering and Packing
• scientific article; zbMATH DE number 1559541 (Why is no real title available?)

This page was built for publication: Packing-based approximation algorithm for the \(k\)-set cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3104644)