---
title: "Comment by Mario Cervera on \"Greedy strategy can be useful even when it doesn't work\" | Hashnode"
description: "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 vertic"
url: "https://hashnode.com/posts/greedy-strategy-can-be-useful-even-when-it-doesnt-work/5fc29d1429ee3663480ca20a/comment/5fc3e77f0a072175ef2ce212"
---

[Discussion](https://hashnode.com/posts/greedy-strategy-can-be-useful-even-when-it-doesnt-work/5fc29d1429ee3663480ca20a)

Comment [Greedy strategy can be useful even when it doesn't work](https://hashnode.com/posts/greedy-strategy-can-be-useful-even-when-it-doesnt-work/5fc29d1429ee3663480ca20a)

[Mario Cervera](https://hashnode.com/@macerub)

[Nov 29, 2020](https://hashnode.com/posts/greedy-strategy-can-be-useful-even-when-it-doesnt-work/5fc29d1429ee3663480ca20a/comment/5fc3e77f0a072175ef2ce212)

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](https://hashnode.com/@josejorgers)

[Nov 30, 2020](https://hashnode.com/posts/greedy-strategy-can-be-useful-even-when-it-doesnt-work/5fc29d1429ee3663480ca20a/comment/5fc3e77f0a072175ef2ce212#reply-5fc544e1bc24037614df9b6f)

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.

[Mario Cervera](https://hashnode.com/@macerub)

[Nov 30, 2020](https://hashnode.com/posts/greedy-strategy-can-be-useful-even-when-it-doesnt-work/5fc29d1429ee3663480ca20a/comment/5fc3e77f0a072175ef2ce212#reply-5fc579cdbc24037614df9e06)

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.