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.