A Greedy Heuristic for the Set-Covering Problem.¶
Chvatal, V. (1979). A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research, 4(3), 233-235.
Cited by¶
1 citation across 1 artifact.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Greedy Algorithm
- The approximation ratio is the second handle: greedy set cover achieves a logarithmic factor, and that bound holds across substrates with the same structure (advertising audience selection, sensor placement, material coverage).
This sourceProves greedy set cover achieves a logarithmic (H(n)) approximation ratio — not exact — a bound that ports to audience/sensor/material coverage problems with the same structure.
- The approximation ratio is the second handle: greedy set cover achieves a logarithmic factor, and that bound holds across substrates with the same structure (advertising audience selection, sensor placement, material coverage).
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:c5bdd11e0149 · see in the full table