Search Hashnode

Search posts, tags, users, and pages

Comment by Mario Cervera on "Greedy strategy can be useful even when it doesn't work" | Hashnode

Mario Cervera

Software craftsman. I write about Software Engineering (clean code, design, testing, ...) and also about Algorithms & Data Structures.

Nov 29, 2020

Nice article Jose!

Another way to describe your greedy solution for vertex cover is by finding a maximal matching in the graph and then taking all of its vertices. It's the same concept, just using another term of graph theory 😊

Another greedy approach for vertex cover that also works pretty well (although a bit less efficient) is repeatedly picking vertices of highest degree.

Jose Jorge Rodriguez

Computer scientist, teacher, researcher and developer

Nov 30, 2020

Nice addition Mario, as always! Actually, I wanted to remove some graph-related examples and to add other examples. I think talking about maximal matching is going too far :)

But you are definitely right! And the other strategy seems good. I just don't know whether it yields a constant-factor approximation. I'd like to think about it and prove it/disprove it.

The other heuristic does not yield a constant-factor approximation. I do not have the proof, but I've read that it can obtain covers that are log n times worse than the optimal.

Mario Cervera

Software craftsman. I write about Software Engineering (clean code, design, testing, ...) and also about Algorithms & Data Structures.

Nov 30, 2020