# When Greedy Algorithms are Good Enough: Submodularity and the (1--1/e)-Approximation

DevFeed: [When Greedy Algorithms are Good Enough: Submodularity and the (1--1/e)-Approximation](<https://devfeed.tech/articles/when-greedy-algorithms-are-good-enough-submodularity-and-the-1-1-e-approximation-40361.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/07/07/when-greedy-algorithms-are-good-enough-submodularity-and-the-1-1e-approximation/>)

Published: 2014-07-07T10:00:01Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Computer science](<https://devfeed.tech/topics/computer-science.md>), [Mathematics](<https://devfeed.tech/topics/mathematics.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [computer-science](<https://devfeed.tech/tags/computer-science.md>), [coverage](<https://devfeed.tech/tags/coverage.md>), [greedy](<https://devfeed.tech/tags/greedy.md>), [greedy-algorithm](<https://devfeed.tech/tags/greedy-algorithm.md>), [matroids](<https://devfeed.tech/tags/matroids.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [submodularity](<https://devfeed.tech/tags/submodularity.md>), [theory](<https://devfeed.tech/tags/theory.md>)

## AI overview

This article explains when greedy algorithms can produce optimal or near-optimal solutions. It introduces submodularity as a diminishing-returns property and discusses how it can provide a reasonably good approximation to the optimal solution.

## Source excerpt

Greedy algorithms are among the simplest and most intuitive algorithms known to humans. Their name essentially gives their description: do the thing that looks best right now, and repeat until nothing looks good anymore or you're forced to stop. Some of the best situations in computer science are also when greedy algorithms are optimal or near-optimal. There is a beautiful theory of this situation, known as the theory of matroids. We haven't covered matroids on this blog (edit: we did), but in this post we will focus on the next best thing: when the greedy algorithm guarantees a reasonably good approximation to the optimal solution.