Skip to content
Tutorials Center
My learning

Topics

Lesson 173 of 225 ยท Greedy Algorithms

Greedy Approximation: Set Cover, Bin Packing, k-Center and TSP

Learn how greedy algorithms approximate NP-hard problems: set cover, bin packing, k-center, TSP via MST and shortest superstring, with Python code.

Many problems in computer science are NP-hard: no known algorithm solves every instance exactly in polynomial time (NP-completeness explains why). You still have to ship something. Two practical answers exist: search cleverly and hope the instance is small, or settle for an approximation, a fast algorithm whose answer is provably never worse than a stated factor times the best possible.

Greedy rules are the most common source of such algorithms. They are quick to write, fast to run, and for several famous problems come with a guarantee. This lesson walks through five of them: set cover, bin packing, k-center, the travelling salesman problem (via a spanning tree) and shortest superstring. For each you will see the rule, a Python version, and a comparison against the exact answer on a small input, so you can watch the approximation gap with your own eyes.

An approximation ratio of r means the algorithm's answer is at most r times the optimum (for a minimization problem). A 2-approximation never costs more than twice the best possible.

Set cover

You have a universe of items and a family of sets. Choose the fewest sets whose union is the whole universe. Think of picking the fewest radio stations that together reach every town.

Greedy rule: repeatedly pick the set that covers the most still-uncovered items.

This is an H(n)-approximation, where H(n) = 1 + 1/2 + ... + 1/n is about ln n. Roughly: when k sets suffice, some set always covers at least a 1/k fraction of what remains, so the uncovered part shrinks by a factor (1 - 1/k) per pick, and after about k ln n picks nothing is left. No polynomial algorithm can do much better unless P = NP.

Python Greedy set cover and its worst case

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Greedy grabs X first because it is largest, then needs Y and Z: three sets. The best answer is P and Q: two. The ratio here is 1.5, well within the guarantee, and families of instances exist that approach the ln n bound.

Bin packing

You have items with sizes and bins of capacity C. Pack every item using as few bins as possible. Warehouses, memory allocation and cutting stock all look like this.

First-fit decreasing (FFD): sort the items from largest to smallest, and put each into the first bin where it fits, opening a new bin when none does. Sorting first is the trick: large items are awkward, so place them early while bins are empty.

FFD never uses more than 11/9 * OPT + 6/9 bins, and plain first-fit without sorting only guarantees about 1.7 * OPT. The next TryIt compares them.

Python First fit versus first fit decreasing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The lower bound is ceil(total / capacity), because even perfect packing cannot beat full bins. FFD hits it (3 bins), while unsorted first-fit needs 4. A bound like this is a handy way to show an answer is optimal without computing the optimum.

k-center

Place k facilities (fire stations, servers) among n locations so that the farthest location from its nearest facility is as close as possible. The goal is to minimize that worst distance, called the radius.

Farthest-first traversal: pick any location as the first center. Then, k - 1 times, pick the location that is farthest from all the centers chosen so far.

This is a 2-approximation, and 2 is the best possible unless P = NP. The idea: let r be the greedy radius. Then the k centers plus the farthest point are k + 1 points that are all at least r apart. Any solution with k centers must put two of them in the same cluster, so some center serves points at distance at least r / 2. Hence OPT >= r / 2.

Python Farthest-first traversal for k-center

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Greedy needs O(nk) time. The exact search tries every combination of k centers, which explodes as n grows.

Travelling salesman: the MST 2-approximation

Visit every city exactly once and return to the start with the shortest total distance. This is NP-hard. When distances obey the triangle inequality (a direct road is never longer than a detour, true for ordinary geometry), a minimum spanning tree gives a clean 2-approximation:

  1. Build an MST. Its total weight is at most the best tour (drop one edge from the tour and you have a spanning tree).
  2. Walk around the tree in preorder (visit a node, then its children). A full walk around the tree traverses every edge twice, so it costs at most 2 * MST <= 2 * OPT.
  3. Skip any city already visited. By the triangle inequality, a shortcut never makes the walk longer.
Python TSP 2-approximation from a minimum spanning tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The ratio is well under 2 on this input. A smarter method (Christofides) improves the factor to 1.5, but needs minimum-weight matching, which is beyond this lesson.

The 2-approximation needs the triangle inequality. Without it, no polynomial-time algorithm can guarantee any constant factor for TSP unless P = NP, so "metric" is a real assumption, not a technicality.

Shortest common superstring

Given a set of strings, find the shortest string that contains every one of them as a substring. Genome assembly is the standard motivation: a sequencer returns overlapping fragments and you want the shortest sequence consistent with all of them.

Greedy rule: repeatedly find the pair of strings with the largest overlap (a suffix of one that equals a prefix of the other) and merge them. Stop when one string is left. This is conjectured to be a 2-approximation (proven to be within 3.5), and works very well in practice.

First remove any string that is already a substring of another, since it adds nothing.

Python Greedy shortest superstring

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The greedy version is O(n^3 L) in this simple form, where n is the number of strings and L their length. Faster versions use suffix structures; see suffix structures.

Common mistakes

  • Claiming optimality. An approximation has a ratio, not a proof of the best answer. State the factor, and test against a brute force on small inputs.
  • Forgetting to sort for bin packing. First-fit without sorting is a noticeably weaker guarantee than first-fit decreasing.
  • Applying the TSP shortcut to non-metric distances. Without the triangle inequality the 2-approximation proof collapses.
  • Picking set cover's sets by raw size. Count only items that are still uncovered, or the later picks will be wasteful.
  • Not removing contained strings first. A word that is a substring of another can make the superstring greedy loop on useless merges.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a 2-approximation guarantee for a minimization problem?

    The approximation ratio bounds how far the algorithm's cost can be from the best possible cost.
  2. 2. In greedy set cover, how do you score a candidate set?

    Already covered items add nothing, so only the new coverage counts.
  3. 3. Why does first-fit decreasing beat plain first-fit?

    Large items are hard to fit later, and small ones fill the gaps afterwards. Sorting by size descending captures that.
  4. 4. What does farthest-first traversal choose each round in k-center?

    That point is the one currently served worst, and the argument for the factor 2 relies on these centers being pairwise far apart.
  5. 5. Which assumption does the MST-based TSP 2-approximation need?

    Skipping revisited cities creates shortcuts, which only help if direct paths are never longer than detours.

Summary

  • NP-hard problems are often tackled with greedy approximation algorithms that come with a ratio guarantee.
  • Set cover: pick the set covering the most uncovered items; ratio about ln n.
  • Bin packing: first-fit decreasing; at most 11/9 * OPT + 6/9 bins, and ceil(total / capacity) is a quick lower bound.
  • k-center: farthest-first traversal is a 2-approximation, optimal as a factor unless P = NP.
  • Metric TSP: build an MST, walk it in preorder, skip repeats; at most twice the best tour.
  • Shortest superstring: merge the pair with the largest overlap, after dropping contained strings.
  • Always check an approximation against brute force on tiny inputs and against a lower bound on bigger ones.

Next: Greedy in Operating Systems: Memory Fit, Scheduling and Page Replacement