Thought about the Minimum Disk Cover problem today.

This much is sure - skyline property will fail. Also lemma about there being an optimum solution without a supercovered disk will not hold.

So let us assume that the LP solution given produces some disks that are covered by only skyline disks and some that are partly covered by skyline and non-skyline disks and some that are completely covered by non-skyline disks.


Now if the skyline disks contribute more than 1/2 we can just pick those since we can afford an approximation factor of 2. In the other case ... this is where we need to see.

Disks are either skyline disks or they are supercovered ? Is this true ? NO. Of course not. Disks that are not in the skyline are supercovered only if the 2 disks that cover it have a point p in P that both of them cover but the non-skyline-disk does not.

It is not possible to apply the technique of skyline disks while moving from Unit Disk Cover problem to Weighted Disk Cover Problem because a disk in skyline may have arbitrarily higher cost than one which is not.

Paper Contributions

1. 6-approx. algo for MFSP in O(n * logn) time
2. 3-approx. algo for MFSP in O(n * log(square(n))) time
3. Exact algo O(n^2 * log n) and 2-approx. algo O(n * log n) for special case of MFSP where all 2-hop nodes in same quadrant
4. Constant-factor approx algo for MDCP with disks of SAME RADIUS (based on rounding a LP solution)

Facts

Greedy algorithm for set cover - approximation factor O(log m) where m is the number of sets.

Dominating Set Problem in Unit Disk Graphs is NP Hard but admits a PTAS.

Minimum Forwarding Set Problem does not reduce to Dominating Set Problem.
Its complexity is not known.

Unit Disk Cover Problem is also NP Hard and admits a PTAS.