Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

New answers tagged

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