3
$\begingroup$

The interval partitioning problem can be solved efficiently using a greedy algorithm. However, adding restrictions on the interval assignment to the problem results in a problem that appears harder. Here's my problem formulation:

  • There are $n$ rooms. We want to hold $m$ events in these rooms. These events have fixed (given as input) starting times $s_1,\dots,s_m$ and finishing times $f_1,\dots,f_m$.
  • Each event must be held in exactly one room, and two events cannot be held in the same room at the same time.
  • Certain events can be held in only certain rooms. This is given as an input as an $n$ by $m$ matrix of booleans.
  • We want to figure out whether all events can be held in these rooms.

It seems to me that a greedy algorithm can't solve this. Additionally, since bipartite matching is a special case of this problem (when all events are held at the same time), I have attempted to transform this "interval partitioning with restrictions" problem into a maximum flow problem, with no success. I have also considered trying to prove that this problem is NP-complete, but I don't know where to start.

Could anybody help me either find an efficient algorithm for this or prove that it is NP-complete?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ @MarzioDeBiasi I don't see how the reduction from the 3-partition problem to this problem could be possible. That problem deals with sums of integers, but my problem doesn't have any summing. Could you give me some directions? $\endgroup$
    – Theemathas Chirananthavat
    Apr 18, 2020 at 9:52
  • $\begingroup$ sorry, I read the question too quickly and didn't notice the "fixed starting time"; there is no direct/quick reduction to 3-PARTITION ! ... I'll think if there is a quick reduction to another problem later. $\endgroup$
    – Marzio De Biasi
    Apr 18, 2020 at 23:04
  • $\begingroup$ @NealYoung: of course, forget my quick fart-like comment (I'll delete it ;-). Lacker's reduction is elegant and correct (so I didn't spend more time on the problem) $\endgroup$
    – Marzio De Biasi
    Apr 27, 2020 at 22:04

1 Answer 1

Reset to default
3
$\begingroup$

Here's a reduction from 3SAT. For each of your 3SAT variables $x_0$, imagine there is one event $x_0$ and two rooms called "Room $x_0$ is true" and "Room $x_0$ is false". The event $x_0$ has to be in one of those two rooms. Whichever statement is true, that's the room we don't use. And it is going to take all day. So the only rooms generally available for other events are the rooms named with a true statement.

Now let's say you want to add a condition - $x_0$ OR $x_1$ OR NOT $x_2$. Make that into an event that's just one nanosecond long, at a random time so it doesn't conflict with the other condition-events. And it has to be held in one of "Room $x_0$ is true", "Room $x_1$ is true", or "Room $x_2$ is false".

Now solving your event assignment problem lets you solve an arbitrary 3SAT problem.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Yes. That does, in fact, work, huh. I somehow didn't consider reducing directly from 3-SAT. Thanks! $\endgroup$
    – Theemathas Chirananthavat
    Apr 19, 2020 at 9:37
  • $\begingroup$ Your answer starts by "Here's a reduction to 3SAT", but you mean a reduction from 3SAT, right? $\endgroup$
    – a3nm
    Apr 20, 2020 at 22:07
  • $\begingroup$ I guess so - I always get the two confused. I edited the answer. It's the direction that proves this scheduling problem is hard :P $\endgroup$
    – lacker
    Apr 22, 2020 at 19:00

Your Answer

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

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