1
$\begingroup$

Let's say we have some distinct sets each containing a number of line segments. I want to choose the minimum number of sets such that I will obtain a line from 0 to L with the largest gap being X long.

For example, let's say we have the sets A, B, and C as given below. L is 45 and X is 4.

If we take A, there is a gap from 10 to 15 that is greater than 4, and from 32 to 45. Notice that picking B covers the gap from 10 to 15, but there's still a gap between 40 to 45 so we need to pick C as well. However, we can pick C without picking B and reach our goal.

Is there any way to formulize this? If the problem was to pick the least number of segments I'd use a greedy approach but we are trying to minimize the number of sets here. I can only think of removing a set, inspecting if the goal can be met, and if so, removing another set. Maybe I can make this into a tree to see the effect of removing each set? Or is there another solution with less complexity?

Thanks

$\endgroup$
3
  • $\begingroup$ Just an observation:The constraint on the gap is irrelevant since you can always extend each interval by $X/2$ (and shorten the endpoints by $X/2$). $\endgroup$
    – Steven
    Oct 17, 2022 at 17:36
  • $\begingroup$ Don't you mean "intervals" ? $\endgroup$
    – user16034
    Oct 17, 2022 at 17:42
  • $\begingroup$ I mean that you can move the left (resp. right) endpoint of each segment to the left (resp. right) by $X/2$ and simultaneously consider the line $[X/2, L-X/2]$ instead of $[0,L]$. $\endgroup$
    – Steven
    Oct 17, 2022 at 17:46

2 Answers 2

1
$\begingroup$

The problem is NP-hard in general. Consider the setting where X=0, and each line segment has length 1. Then this becomes an instance of the set cover problem, which is well-known to be NP-hard. So, you can't expect any efficient algorithm that always solve this problem and has good worst-case running time.

You could try applying any of the standard methods for set cover, e.g., using an ILP solver, or adapting the greedy algorithm.

$\endgroup$
1
$\begingroup$

In addition to D.W.'s answer, notice that the constraint on the gap is irrelevant since you can always extend each interval endpoint by $X/2$ (and shorten the endpoints of the line by $X/2$).

Then the problem can be reduced to set cover: create an item for each maximal (w.r.t. inclusion) sub-interval of $[0,L]$ that is covered by the same set of segments; each set of the set cover instance corresponds to a set of your instance and contains all items (i.e., sub-intervals) that are covered by some segment in that set.

The optimal measure and the number of sets of the two problems coincide, while the number of items is at most twice the number of segments (each segment endpoint creates at most one item, and you can't have uncovered portions of the line).

This provides you with a concrete strategy for using any approximation algorithm for set-cover (as D.W. suggested) to approximate your problem within the same asymptotic approximation ratio.

$\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.