Definition · Set cover, and the greedy ruleGiven a family of sets whose union is a universe, find as few of them as possible whose union is still the whole universe. The greedy rule repeatedly takes a set covering the largest number of elements not yet covered, stopping when everything is covered.
Theorem · The charges add to the answerIf each set taken by greedy charges 1/k to each of the k elements it newly covers, then the sum of all charges equals the number of sets greedy took.
A
s
e
t
c
o
v
e
r
i
n
g
`
k
`
n
e
w
e
l
e
m
e
n
t
s
d
i
s
t
r
i
b
u
t
e
s
`
k
`
c
h
a
r
g
e
s
o
f
`
1
/
k
`
,
w
h
i
c
h
i
s
1
i
n
t
o
t
a
l
,
s
o
e
a
c
h
s
e
t
h
a
n
d
s
o
u
t
e
x
a
c
t
l
y
i
t
s
o
w
n
c
o
s
t
.
E
v
e
r
y
e
l
e
m
e
n
t
i
s
n
e
w
l
y
c
o
v
e
r
e
d
e
x
a
c
t
l
y
o
n
c
e
,
b
y
t
h
e
s
e
t
t
h
a
t
f
i
r
s
t
c
o
v
e
r
s
i
t
,
s
o
n
o
e
l
e
m
e
n
t
i
s
c
h
a
r
g
e
d
t
w
i
c
e
a
n
d
n
o
n
e
i
s
m
i
s
s
e
d
&
m
d
a
s
h
;
g
r
e
e
d
y
s
t
o
p
s
o
n
l
y
w
h
e
n
t
h
e
u
n
i
v
e
r
s
e
i
s
c
o
v
e
r
e
d
.
S
u
m
m
i
n
g
o
v
e
r
s
e
t
s
g
i
v
e
s
t
h
e
c
o
u
n
t
;
s
u
m
m
i
n
g
o
v
e
r
e
l
e
m
e
n
t
s
g
i
v
e
s
t
h
e
s
a
m
e
n
u
m
b
e
r
a
d
i
f
f
e
r
e
n
t
w
a
y
,
w
h
i
c
h
i
s
t
h
e
i
d
e
n
t
i
t
y
.
□
Theorem · Greedy set cover is within H_n of the optimumGreedy returns a cover of size at most H_n · OPT, where n is the size of the universe, OPT is the size of a smallest cover and H_n = 1 + 1/2 + ... + 1/n.
Consider the moment an element is covered, with r elements uncovered including it. An optimal cover of size OPT covers all r, so one of its sets covers at least r / OPT of them; greedy takes a set covering at least that many new elements, so the charge is at most OPT / r.
The elements are covered in some order; the first is charged at most OPT / n, the next at most OPT / (n - 1), and so on down to at most OPT / 1 for the last. Adding, the total charge is at most OPT · H_n. By the identity the total charge is the size of greedy's cover, which gives the bound.
□
What the lab measured
The loaded family is {3,4,5,6}, {1,2,3}, {4,5,6,7} over the universe 1 to 7. Greedy takes the four-element set first, then needs two more; the optimum is 2, found by an exhaustive search over the 8 subfamilies, and it is the second and third sets together. The panel reports a realised ratio of 3/2, H over 7 as 363/140, the bound H × OPT as 363/70, the answer inside the bound, and the charges adding to the answer exactly.
The charges are 1/4 to each of the four elements the first set covered, 1/2 to each of the two the second set newly covered, and 1 to the single element the third set brought in. That is 4 × 1/4 + 2 × 1/2 + 1 = 3, which is the number of sets, and the panel checks the sum rather than showing the prices and moving on.
Example · The allowance each element was entitled toWith OPT = 2 and seven elements, the allowances OPT / r for r from 7 down to 1 are 2/7, 1/3, 2/5, 1/2, 2/3, 1, 2, adding to 2 · H_7 = 363/70. The realised charges are 1/4, 1/4, 1/4, 1/4, 1/2, 1/2, 1, and each is at or below its own allowance — the tightest being the first, 1/4 against 2/7. The bar chart draws each charge against the most the analysis allows it.
Why greedy loses here, and why it usually does not
The family is built to trip the rule. The four-element set is the largest, so greedy takes it first, and afterwards neither of the two sets that together cover everything is whole any more: one has two new elements and the other one. A rule that had looked ahead would have taken those two and finished. This is the same shape as the greedy failure the dynamic programming course opened on — a first choice that is locally best and globally wrong.
Most families are not like this. Switch to the disjoint partition and the ratio is 1 because every cover is the whole family; switch to the one big set with singletons under it and greedy takes the big set and stops, which is the optimum. The panel's default is the interesting case precisely because it is not the common one, and reading 3/2 as typical would be as wrong as reading 1 as a guarantee.
One number here is not a measurement: H_n and the bound H_n · OPT are the proved guarantee evaluated at this instance's numbers. 3/2 was counted. 363/70 was derived. They sit in the same panel and the gap between them — 1.5 against about 5.19 — is the usual state of an approximation guarantee: comfortable, and not evidence that the bound could be improved.