New answers tagged approximation-algorithms
8
Let me first try to summarize what is known about the Greedy Conjecture.
Blum, Jiang, Li, Tromp, Yannakakis prove that the Greedy Algorithm gives a 4-approximation, and Kaplan and Shafrir show that it gives a 3.5-approximation for the Shortest Common Superstring problem.
A version of the greedy algorithm is known to give a 3-approximation (Blum, Jiang, Li, ...
Top 50 recent answers are included
