0
$\begingroup$

Given a 1-D universe $U$ (e.g. $\mathbb{Z}$) and a set-of-sets $\pmb{S}$, where each element of $\pmb{S}$ is a closed, connected subset of $U$ (e.g. $[a .. b]$ given $ a,b\in\mathbb{Z}$) and $\bigcup\pmb{S}=U$, what is the quickest way to find $\pmb{S}^*\subseteq \pmb{S}$ with the smallest cardinality such that $\bigcup \pmb{S}^* = U$?

In other words, is there a fast 1-D set cover optimisation algorithm given that the sets you're working from are closed-connected?

It seems to me that the naive greedy set cover will in fact be optimal here, but I'm not expert enough to prove it. Can anyone think of a counter-example?

$\endgroup$
  • $\begingroup$ You can use a greedy algorithm starting from the lower element and picking the largest interval that covers the first lowest uncovered element. It's not hard to prove that it is optimal. $\endgroup$ – Marzio De Biasi Jan 12 '15 at 16:29
  • $\begingroup$ That was the first solution we thought of. Do you have a reference to a proof that it's optimal? This isn't my area of expertise. $\endgroup$ – John_C Jan 12 '15 at 16:32
  • $\begingroup$ I'll write a sketch of the proof. $\endgroup$ – Marzio De Biasi Jan 12 '15 at 16:38
  • $\begingroup$ :-) Gerhard posted an answer while I was writing mine ... see the correctness notes in the linked lecture. $\endgroup$ – Marzio De Biasi Jan 12 '15 at 16:48
1
$\begingroup$

The leftmost point must be covered by some interval. There is no harm in picking the longest interval that covers the leftmost point. Then iterate (after removing the interval and all covered points from the instance).

This is the well-known greedy algorithm for the "Interval Point Cover" problem; see for instance the course page by Andranik Mirzaian for a full analysis.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.