---
title: Approximation Algorithms for Combinatorial Problems
authors:
- David S. Johnson
year: 1974
venue: Journal of Computer and System Sciences
arxiv: null
doi: 10.1016/S0022-0000(74)80044-9
source: "https://doi.org/10.1016/S0022-0000(74)80044-9"
topics:
- approximation-algorithms
- complexity
seed_rank: 800
seed_batch: perfects-algorithms-2026-08-13
reviewed: 2026-08-13
pool: maths-foundations
relevance_score: 8
lineage: algorithms-and-complexity
cites:
- title: "Computers and Intractability: A Guide to the Theory of NP-Completeness"
  url: "https://en.wikipedia.org/wiki/Computers_and_Intractability"
  year: 1979
  arxiv: null
  doi: null
see:
- "727-computers-and-intractability-a-guide-to-the-theory-of-np-com"
---

# Approximation Algorithms for Combinatorial Problems

## One-sentence takeaway

Johnson 1974 systematically studies polynomial algorithms that guarantee a bounded ratio to optimal for NP-hard combinatorial problems, with set cover’s $H_n$ greedy bound as the emblematic analysis.

## Why it matters here

This is how GRID COMMAND planners and Anoptic packers cope when exact combinatorial search is NP-hard: measure the worst-case ratio, do not pretend Garey–Johnson vanished.

## Key ideas

- Defines performance guarantee as the worst-case ratio (or difference) between the heuristic’s cost and OPT.
- Analyzes greedy and local-search heuristics for set cover, graph coloring, bin packing, and related problems.
- Shows that “almost always good” is a different claim from “ratio $\le\rho$ on every instance.”
- Opens the approximation-algorithms field that PCP / hardness-of-approximation later maps from the other side.

## Caveats

## Links

- DOI: [10.1016/S0022-0000(74)80044-9](https://doi.org/10.1016/S0022-0000(74)80044-9)
- URL: https://doi.org/10.1016/S0022-0000(74)80044-9