The World's Simplest Interesting Algorithm (2019) | Hacker News Reader

The World's Simplest Interesting Algorithm (2019)

algorithmsoup.wordpress.com

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.

The proof here is not incorrect; it does not make any claims on performance. Usually you’d care that your algorithm is not exponential, but here the claim was that this algorithm provides some approximation that is within a constant factor of the optimal solution in terms of the number of vertices it picks.

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.

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.

If you try to share multiple cakes this way, make sure you have compatible utility functions, because the algorithm doesn’t work if any of the cakes are of negative utility for any of the people (eg due to allergies)

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.

Your set would contain all the vertices, while you can do better by only including some. For example, think of three vertices in a line with the first and second vertex joined by and edge and the second and third. The “optimal cover” picks the second vertex and covers both edges.

You only need one of the vertices of an edge to cover that edge.

So in the simplest case of two vertices connected by an edge, your algorithm would generate a set of size 2 instead of the minimum size 1.

The minimum vertex cover is a minimal set of vertices such that every edge is incident to at least one vertex in the set. For a star graph with 101 nodes and 100 edges, the minimum vertex cover is a set containing 1 vertex. The algorithm in TFA gives a set containing 2 vertices. Your algorithm gives a set containing a bit more than 2 vertices.

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

edge cover is picking edges that touch every vertex

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

If you pick up a leaf, you also pick up the star one level up and thus the entire subtree is now covered (so you don’t look at it again). What is the failure, specifically?

True. Hmm.

Assuming your star is a single center vertex which is a vertex to all edges (like spokes in a wheel), then the optimal cover for all edges is 1, the central vertex. If you follow the algorithm, you will select two vertices and produce a covering, which is within a factor of two of the optimal.

I remember proving this algorithm in class (a while ago). What I found interesting from Wikipedia is that this is the best known approximation, there is a proven lower bound of 1.363.

Your intuition was right in that explanation provided in this proof is incorrect.. https://www.cl.cam.ac.uk/teaching/1415/AdvAlgo/lec8_ann.pdf has a more complete explanation. The algorithm works (and gets a 2x bound), but only because of how it processes the edges sequentially and makes sure to only process edges that aren't already covered.

Reply on news.ycombinator.com