---
title: "Discussion on \"Greedy strategy can be useful even when it doesn't work\" | Hashnode"
description: "Discussion on \"Greedy strategy can be useful even when it doesn't work\". Greedy algorithms try to find the optimal solution by taking the best available choice at every step.  For example, you can greedily approach your life. You can always take the path that maximizes your happiness today. But that doesn't mean you'll be..."
url: "https://hashnode.com/posts/greedy-strategy-can-be-useful-even-when-it-doesnt-work/5fc29d1429ee3663480ca20a"
---

[Feed](https://hashnode.com/feed) /

Discussion

# [Greedy strategy can be useful even when it doesn't work](https://blog.jayjaydev.com/greedy-strategy-can-be-useful-even-when-it-doesnt-work?utm_source=hashnode&utm_medium=feed)

Greedy algorithms try to find the optimal solution by taking the best available choice at every step. For example, you can greedily approach your life. You can always take the path that maximizes your happiness today. But that doesn't mean you'll be...

Nov 28, 2020 · 12 min read · blog.jayjaydev.com  
Updated Jan 5, 2021  
Read the article

-   [#algorithms](https://hashnode.com/tag/algorithms)
-   [#optimization](https://hashnode.com/tag/optimization)

## Written by

[Jose Jorge Rodriguez](https://hashnode.com/@josejorgers)

@josejorgers · Havana, Cuba

  
[View profile](https://hashnode.com/@josejorgers)

Computer scientist, teacher, researcher and developer

Computer Scientist. Researching on Artificial Intelligence and working as a Software Engineer. Cuban based in Spain.

## Responses 1

Markdown supported · ⌘↵ to post

[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.