The Radio Masts

Part A: 3 masts, and greedy builds 4

Masts 2, 3 and 6 cover all ten villages, and no two masts do: only mast 4 covers 5 villages, every other mast covers at most 4, and two masts would need 10 between them. Masts 2, 3 and 6 are also the only three that work. Greedy starts with mast 4, the only mast covering 5 villages. Mast 6 then adds 3 more (1, 7 and 10), and villages 2 and 4 need one mast each: 4 masts. The first choice looked best and was a mistake. Mast 4's villages are each covered by other masts that are needed anyway.

Part B: two rows and a staircase of columns

Put $2(2^k-1)$ villages in two rows of $2^k-1$. Two masts, one per row, cover everything. Then add $k$ "column" masts with $2,4,8,\dots ,2^k$ villages: column $i$ takes $2^{i-1}$ villages from each row, and the columns tile both rows.

With $k=4$ that is 30 villages, rows of 15, and columns of 2, 4, 8 and 16. Greedy compares the 16-village column with the 15-village rows and takes the column. What is left is the same picture with $k=3$, so greedy takes every column: 4 masts against 2, with no ties at any step. For $k=5$ the ratio is $5:2$ on 62 villages. In general greedy pays $k$, about ${\log }_{2}n$, against 2. A county with these masts, in any order:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
1 16
2 3 17 18
4 5 6 7 19 20 21 22
8 9 10 11 12 13 14 15 23 24 25 26 27 28 29 30

Part C: greedy with dual fitting

Weighted greedy builds the mast with the least cost per newly covered village. When it builds mast $S$ and covers $m$ new villages, charge each of them the price $w_S/m$. The prices add up to exactly what greedy pays.

Now take any mast $S$ and list its villages in the order greedy covered them. When the $j$-th from the end was covered, at least $j$ of $S$'s villages were still uncovered, so $S$ itself offered a price of at most $w_S/j$, and greedy chose something at least as cheap. So $$\sum _{e\in S}{\text{price}}_e\le w_S(\frac{1}{|S|}+\dots +\frac{1}{1})=H(|S|)w_S\le H(k)w_S.$$ Dividing every price by $H(k)$ therefore gives a feasible $y$, and $$\text{greedy's cost}=\sum _e{\text{price}}_e=H(k)\sum _e{y}_e\le H(k)·\text{OPT}.$$ This is dual fitting. $y$ is a feasible solution of the dual of the set-cover LP, and it is built by shrinking the prices until they fit. See LP Duality.

Four near-misses fail the grader:

• The prices themselves as $y$. On the two-rows test, the top row costs 1, but its villages are charged $16·\frac{1}{32}+8·\frac{1}{16}+4·\frac{1}{8}+2·\frac{1}{4}+1·\frac{1}{2}=2.5$. That is the part B instance, seen as prices.
• Most villages first, ignoring cost, builds the mast that costs a million because it covers everything. Its prices then cannot fit under the cheap single-village masts.
• Dividing by $H(n)$ instead of $H(k)$ gives a feasible but weaker proof. With 62 villages in masts of at most 32, $H(62)\approx 4.71$, and the proof falls short.
• The cheapest mast first pays for many masts that cover little.

Going further

• Tight on both sides. The cheap-singles test is the weighted bad case: villages $1,\dots ,n$ with single-village masts costing $1/1,1/2,\dots ,1/n$, and one mast for everything costing slightly more than 1. Greedy pays $H(n)$, about $\ln n$ times the best. Feige proved that $(1-\epsilon )\ln n$ cannot be beaten in polynomial time unless $\text{NP}\subseteq \text{DTIME}(n^{O(\log \log n)})$; Dinur and Steurer later showed it is NP-hard.
• Rounding the LP randomly, by building each mast with probability scaled from its LP value over about $\ln n$ rounds, reaches the same $O(\log n)$.
• When each village is in at most $f$ masts, a primal-dual method gives a factor of $f$. That is 2 for vertex cover.

References

1. D. S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9, 1974.
2. V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research 4(3), 1979.
3. U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM 45(4), 1998.
4. I. Dinur, D. Steurer. Analytical approach to parallel repetition. STOC, 2014.