I've been reading this paper: https://ac.els-cdn.com/S0304397511002623/1-s2.0-S0304397511002623-main.pdf?_tid=bc074517-2b81-4d37-bc92-a5c20dba6b23&acdnat=1527946614_083eb7104693637d83e7d26751a7d23e

where it talks about the interval scheduling problem but with n processors for k jobs.

I was wondering if there's a proof if the same algorithm would work if it was only two processors for k jobs? If there isn't can you explain why it would work?

Something similar to this question: Interval Scheduling Problem with Three Resources

but instead of 3 resources, 2 resources but I'm trying to get O(n^2) instead of O(n^3).

  • $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. The short version is: include title, authors, where published, and if possible, a link to a freely available PDF. Thank you! $\endgroup$
    – D.W.
    Jun 2 '18 at 16:48
  • $\begingroup$ Presumably you can set $n=2$ and see what the paper's results say about that special case. It might help to provide more background, to summarize what the algorithm is, what theorem the paper has proven, and what is preventing you from working through the same proof but substituting $n=2$. $\endgroup$
    – D.W.
    Jun 2 '18 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.