Alexander Prolubnikov

An Estimation of the Greedy Algorithm's Accuracy for a Set Cover Problem Instance

2019 · Matematičeskie struktury i modelirovanie

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 …