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¶
3 citations across 3 artifacts.
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.
Supported in partVerified against the publisher's abstract
The source abstract states the greedy heuristic's solution value is within a factor growing at most logarithmically, supplying the logarithmic ratio for greedy set cover but not the extension to audience, sensor, or materials problems.
“It turns out that the ratio between the two grows at most logarithmically in the largest column sum of A.”
- 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).
Mechanisms¶
- Greedy Set-Cover Heuristic
- Its strength is that it turns an NP-hard covering problem into a fast, transparent pass, and — unusually for a greedy heuristic — carries a provable ceiling on how far from optimal it can fall, roughly a factor of ln n in the number of needs.
This sourceProves a logarithmic harmonic-number approximation bound for the greedy weighted set-cover heuristic.
- Its strength is that it turns an NP-hard covering problem into a fast, transparent pass, and — unusually for a greedy heuristic — carries a provable ceiling on how far from optimal it can fall, roughly a factor of ln n in the number of needs.
- Set-Cover Analysis
- Because exact set cover is computationally hard, the workhorse is a greedy heuristic — repeatedly select the source that covers the most still-uncovered targets — which carries a known approximation guarantee.
This sourceAnalyzes a greedy set-cover heuristic that repeatedly adds a cost-effective set covering uncovered elements and proves a logarithmic approximation guarantee.
- Because exact set cover is computationally hard, the workhorse is a greedy heuristic — repeatedly select the source that covers the most still-uncovered targets — which carries a known approximation guarantee.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 1 of 3 citations: 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:c5bdd11e0149 · see in the full table