from Hacker News

The World's Simplest Interesting Algorithm (2019)

by williamkuszmaul on 6/10/20, 1:34 AM with 16 comments

  • by lalaland1125 on 6/10/20, 5:52 AM

    The proof here is incorrect. The issue is that it doesn't establish that the number of edges processed is less than or equal to the size of the optimal vertex cover. This is critical and has to do with the fact that we only process edges that aren't already covered.

    https://www.cl.cam.ac.uk/teaching/1415/AdvAlgo/lec8_ann.pdf contains a more correct proof.

    Note the |C∗| ≥ |A| line on slide 8. That's critical to the correctness of the proof, but missing in this article.

  • by throw149102 on 6/10/20, 6:17 AM

    I find the 7/8-approximate algorithm for 3SAT to be simpler.

    Given a set of clauses C_1 ^ C_2 ^ ... ^ C_n where each clause is an OR of 3 logical variables, find assignments to each variable to maximize the number of clauses satisfied.

    The algorithm is to just assign each variable randomly. For each clause, there are 8 possible assignments, and 7 out of 8 make the clause true. Therefore, randomly assigning them gives you a 7/8-approximation.

    What makes this so fascinating to me is that the difference between a (polynomial) algorithm that gets 7/8 right and one that gets 8/8 right is the difference between a child randomly guessing and solving all of the world's most important problems in a single algorithm. It could be worth trillions of dollars. Of course, it's probably impossible and therefore P != NP.

  • by landtuna on 6/10/20, 11:43 AM

    My favorite simple and interesting algorithm is "one person cuts the cake in halves, and the other person chooses a piece" and its extension to more than two people.

  • by v_g on 6/10/20, 5:21 AM

    If I go through the list of edges one by one and push the two vertices of each edge into a Set, at the end wouldn’t I end up with the minimum number of vertices needed to cover the graph?

    Most likely I’m not understanding the problem, would appreciate if someone could clarify.

  • by saagarjha on 6/10/20, 5:43 AM

    (For those wondering: edge cover, or picking vertices that touch every edge, can be done in polynomial time.)

  • by downshun on 6/10/20, 5:26 AM

    I'm not sure this is right.

    Take a star with many (>3) leaves

    Replace every leaf by a star

    The algorithm fails by picking up leaves