2
$\begingroup$

Suppose we have a bunch of bars, which can represent anything (time slots, paths, physical items...) and each of them has a start point, an end point, and an associated value.

enter image description here

Out of all the bars available, we want to choose the set which maximizes the total value but with no overlap between the start points and end points of the bars. In the example above, the selected bars would be the following (in red):

enter image description here

What would be the best way to approach this problem computationally, for n number of bars being potentially large (several thousands) and [x,y] the possible bar positions being large as well?

I thought of a probabilistic approach, but are there deterministic approaches as well?

Improve this question
$\endgroup$
2
  • $\begingroup$ I am familiar with the deterministic approach. Could you please share the probabilistic approach you thought of, I'd like to compare it with probabilistic earliest deadline first. Thank you. $\endgroup$
    – E. Douglas Jensen
    Commented Nov 16, 2017 at 20:27
  • $\begingroup$ @E.DouglasJensen sorry for late answer — it consists of stochastically building a tree of admissible solutions (pick a random element, then pick another one with no conflict, etc), and once we have enough of them, pick the solution with max value. Obviously, this does not guarantee an optimal solution, but for certain cases it can work very well. $\endgroup$
    – Jivan
    Commented Nov 25, 2017 at 19:50

1 Answer 1

Reset to default
7
$\begingroup$

You are looking for a maximum weight independent set in an interval graph, which can be solved in linear time (by a deterministic algorithm). By the way, the same is true also for a superclass of interval graphs, namely chordal graphs.

One such algorithm is based on dynamic programming, you can see e.g., [1] for details and discussion.

[1] Hsiao, Ju Yuan, Chuan Yi Tang, and Ruay Shiung Chang. "An efficient algorithm for finding a maximum weight 2-independent set on interval graphs." Information Processing Letters 43.5 (1992): 229-235.

Improve this answer
$\endgroup$
0

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.