An estimation of the greedy algorithm's accuracy for a set cover problem instance

2018/11/05 by Prolubnikov, Alexander
#90C27 #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1811.04037

Abstract

Considering the set cover problem, by modifying the approach that gives a logarithmic approximation guarantee for the greedy algorithm, we obtain an estimation of the greedy algorithm's accuracy for a particular input. We compare the presented estimation to another estimations of this type. We give such examples of the set cover problem instances that the presented estimation sagnificantly improves over linear programming relaxation based estimation.

Related

• Improved Greedy Algorithm for Set Covering Problem
• A Tighter Analysis of Setcover Greedy Algorithm for Test Set
• A Note on: `Algorithms for Connected Set Cover Problem and Fault-Tolerant Connected Set Cover Problem'
• Tighter inapproximability for set cover
• New Greedy Heuristics For Set Cover and Set Packing