0
$\begingroup$

Given a set of weighted intervals, the weighted interval scheduling problem is to select a subset of the intervals such that none of the intervals in the subset overlap and the sum of their weights is maximized. This can be solved in linear time with dynamic programming or memoized recursion.

Is there a version of this problem where intervals are grouped, i.e. interval $a$ can only be in the solution if intervals $b$ and $c$ are also in the solution? By this formulation, there would be a weight associated with each group, or set, of intervals.

The most similar problem I've come across is the exact cover problem, which is NP-Complete, but in this instance we're maximizing weight and all vertices need not be covered.

Any insight will be much appreciated. Thanks!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

This is equivalent to the maximum weighted independent set problem - given a graph with weighted vertices, find a subset of the vertices such that no two vertices in the subset are adjacent in the graph and the sum of their weights is maximized.

The graph the problem is being solved on is a type of interval graph where each vertex represents a group of intervals and its weight is the sum of the intervals' weights. An edge is drawn between two vertices if one or more of their intervals overlap.

I haven't determined if this formulation is tractable or not. While the problem is NP-hard, we know it can be solved efficiently for certain types of graphs, including interval graphs where each vertex represents a single interval.

Improve this answer
$\endgroup$
0
$\begingroup$

Sure, you can define any problem you want. Effectively you would no longer seek a cover of intervals, but a cover of sets, where each set is a union of intervals. Over a discrete set, any set can be expressed as a union of intervals. Thus, this is equivalent to the maximum set packing problem. Consequently, it is NP-hard.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm not looking for a cover though, just a set of non-overlapping intervals, i.e. the solution need not cover anything. $\endgroup$
    – alan
    Commented Apr 28, 2020 at 17:32
  • $\begingroup$ @alan, you're right, sorry, I wasn't thinking clearly -- see edited answer. $\endgroup$
    – D.W. ♦
    Commented Apr 28, 2020 at 19:11

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.