# matroids

Published articles for matroids.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## When Greedy Algorithms are Perfect: the Matroid

DevFeed: [When Greedy Algorithms are Perfect: the Matroid](<https://devfeed.tech/articles/when-greedy-algorithms-are-perfect-the-matroid-40364.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/08/26/when-greedy-algorithms-are-perfect-the-matroid/>)

Published: 2014-08-26T09:00:02Z

Content type: article

Language: en

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

Topics: [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [graph theory](<https://devfeed.tech/topics/graph-theory.md>), [Graphs](<https://devfeed.tech/topics/graphs.md>), [math](<https://devfeed.tech/topics/math.md>)

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [graph-theory](<https://devfeed.tech/tags/graph-theory.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [greedy](<https://devfeed.tech/tags/greedy.md>), [greedy-algorithm](<https://devfeed.tech/tags/greedy-algorithm.md>), [kruskal-s-algorithm](<https://devfeed.tech/tags/kruskal-s-algorithm.md>), [linear-independence](<https://devfeed.tech/tags/linear-independence.md>), [matroids](<https://devfeed.tech/tags/matroids.md>), [minimum-spanning-trees](<https://devfeed.tech/tags/minimum-spanning-trees.md>), [trees](<https://devfeed.tech/tags/trees.md>), [vertex](<https://devfeed.tech/tags/vertex.md>)

### AI overview

This article explains when greedy algorithms are guaranteed to produce optimal solutions. It introduces matroids as the framework characterizing that guarantee and uses the minimum spanning tree problem as an example, with background on matroid history and connections to linear algebra and graph theory.

### Source excerpt

Greedy algorithms are by far one of the easiest and most well-understood algorithmic techniques. There is a wealth of variations, but at its core the greedy algorithm optimizes something using the natural rule, "pick what looks best" at any step. So a greedy routing algorithm would say to a routing problem: "You want to visit all these locations with minimum travel time? Let's start by going to the closest one. And from there to the next closest one.

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