"Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover up to lower order terms (see Inapproximability results below), under plausible complexity assumptions."
My current hot take is that we can say, "We implement a greedy algorithm that gives us a good approximation", and cite the 1979 paper, because the algorithm we use is that one; the other references merely explore and/or tighten the bounds on the approximation.
per https://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm
"Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover up to lower order terms (see Inapproximability results below), under plausible complexity assumptions."
what should we cite here, and how should we explain it? The original reference is A Greedy Heuristic for the Set-Covering Problem , and then the inapproximability results extend that - https://en.wikipedia.org/wiki/Set_cover_problem#Inapproximability_results
My current hot take is that we can say, "We implement a greedy algorithm that gives us a good approximation", and cite the 1979 paper, because the algorithm we use is that one; the other references merely explore and/or tighten the bounds on the approximation.