A new approximation algorithm for \(k\)-set cover problem

DOI10.1007/s13369-015-1895-3zbMath1393.68188OpenAlexW1947223152MaRDI QIDQ1639350

Yasser M. Abd El-Latif, Hanaa A. E. Essa, S. Mohamed Ali, Soheir Mohamed 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 algorithmSCPNP-complete optimization problemset-cover problem

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs
• On the ratio of optimal integral and fractional covers
• A modified greedy heuristic for the set covering problem with improved worst case bound
• A threshold of ln n for approximating set cover
• A Greedy Heuristic for the Set-Covering Problem
• A Tight Analysis of the Greedy Algorithm for Set Cover
• Multiobjective Metaheuristics for the Bus Driver Scheduling Problem
• Reducibility among Combinatorial Problems
• 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