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

New answers tagged


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