0
$\begingroup$

Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric_set_cover_problem.

The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the analysis of that?

Is there a constant approximation factor possible for the one-dimensional case if each of the sets in the family contains only consecutive integers and the universe is the set of first n natural numbers? In the usual greedy algorithm for set cover, we take the set that covers the most number of elements, is that some constant times worse than the optimal in this case?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Consider $x_1, …, x_n\in \mathbb{R}$ and $I_1, …, I_k$ be intervals, $I_i = [a_i, b_i]$.

Suppose without loss of generality that $x_1 < x_2 < … < x_n$. Let $I_i$ be an interval such that $x_1 \in I_i$, and $b_i$ maximal for such intervals.

Then there is an optimal solution containing $I_i$. Indeed, suppose $I_i$ is not in an optimal solution. Replace any interval containing $x_1$ (there exists at least one) with $I_i$. This is still a solution, because there is no point $< x_1$, and $b_i$ was supposed to be maximal.

Reiterate the process with points $x_j$ for $b_i < x_j$ to obtain an optimal solution.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Just to clarify, the algorithm that you gave looks is the greedy algorithm, i.e. take the largest set covering most elements from one side and reiterate. Is this exactly the optimal solution or will be some constant times the optimal solution? That will mean every set from the optimal solution will intersect some constant number of sets in your solution. $\endgroup$
    – Sandra
    Commented Jan 11, 2023 at 20:30
  • $\begingroup$ This is the optimal solution, I gave some ideas of the proof in my answer. $\endgroup$
    – Nathaniel
    Commented Jan 11, 2023 at 20:38
  • $\begingroup$ Suppose we don't start from $x_1$ and rather pick up the interval $I_i$ that covers the largest number of elements( i.e. $x_i$), take this $I_i$ in our solution, delete all those $x_i$ and reiterate, i.e. pick the next largest interval $I_j$ and so on until none of $x_i$ are left. This is also a greedy solution, will this be the optimal too? Or will this be some constant times the optimal solution that you gave? $\endgroup$
    – Sandra
    Commented Jan 11, 2023 at 20:43
  • $\begingroup$ I already answered your question. If you have another question to ask, ask it in a new post. $\endgroup$
    – Nathaniel
    Commented Jan 11, 2023 at 20:55
  • $\begingroup$ Also, consider $x_1 = 0$, $x_2 = 2$, $x_3 = 3$, $x_4 = 5$, $x_5 = 6$, $x_6 = 8$ and $I_1 = [0, 4]$, $I_2 = [1, 7]$ and $I_3 = [4, 8]$. Can you see why your algorithm fails? $\endgroup$
    – Nathaniel
    Commented Jan 11, 2023 at 22:31

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.