A new approximation algorithm for k-set cover problem

DOI10.1007/S13369-015-1895-3MaRDI QIDQ1639350zbMATH OpenOpenAlexFDO

Authors Hanaa A. E. Essa, Yasser M. Abd El-Latif, S. Mohamed Ali, Soheir M. Khamis

Publication date 12 June 2018

Published in Arabian Journal for Science and Engineering (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s13369-015-1895-3

zbMATH Keywords

approximation algorithmgreedy algorithmNP-complete optimization problemSCPset-cover problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Packing-based approximation algorithm for the k-set cover problem
• An approximation algorithm for the total covering problem
• New complexity results for the k-covers problem
• Approximation algorithm for the partial set multi-cover problem
• New approximation algorithms for the vertex cover problem
• A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem
• Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems
• scientific article; zbMATH DE number 1559541
• scientific article; zbMATH DE number 784428
• Approximation Algorithms for the k-Clique Covering Problem

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• A modified greedy heuristic for the set covering problem with improved worst case bound
• A threshold of ln n for approximating set cover
• A Tight Analysis of the Greedy Algorithm for Set Cover
• Analysis of approximation algorithms for k-set cover using factor-revealing linear programs
• Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Multiobjective Metaheuristics for the Bus Driver Scheduling Problem
• On the ratio of optimal integral and fractional covers
• Reducibility among combinatorial problems

Cited in

(7)

• A 6/5-approximation algorithm for the maximum 3-cover problem
• Approximation algorithms for the covering-type \(k\)-violation linear program
• Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems
• Packing-based approximation algorithm for the k-set cover problem
• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
• scientific article; zbMATH DE number 784428 (Why is no real title available?)
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search

This page was built for publication: A new approximation algorithm for \(k\)-set cover problem

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