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?

Improve this question
$\endgroup$
4
  • $\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
    Commented Jan 12, 2015 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
    Commented Jan 12, 2015 at 16:32
  • $\begingroup$ I'll write a sketch of the proof. $\endgroup$
    – Marzio De Biasi
    Commented Jan 12, 2015 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
    Commented Jan 12, 2015 at 16:48

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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