6
$\begingroup$

A new, tighter tardiness bound has been found for global Earliest-Deadline-First scheduling of jobs on symmetric multiprocessors. But this bound seems to be particularly hard to compute. In particular, we were not able either to find a polynomial-time algorithm to compute this bound, or to prove that the problem is NP-hard. In this respect, a sufficient condition for the problem to be NP-hard, is that the following sub-problem is NP-complete.

Given:

  • a set $\tau$ of $N$ pairs $(C_i, U_i) \in \mathbb{Q}^2$, with $C_i > 0$ and $0 < U_i \le 1$ for all $i \in \{1, 2, \ldots, N\}$,
  • the smallest natural number $M$ such that $\sum_{i=1}^{N} U_i \le M$ (which implies $M \le N$, because $U_i \le 1$),
  • an integer $M'$ with $1 \le M' \le M$,
  • a strictly positive value $b \in \mathbb{Q}$;

does a permutation $\tau' = ( (C_{i_1},U_{i_1}), (C_{i_2},U_{i_2}), \ldots, (C_{i_{M'-1}}, U_{i_{M'-1}}))$ of $M' - 1$ pairs in $\tau$ exist, such that $$ \sum_{g = 1}^{M'-1}\frac{C_{i_g}}{M - \sum_{v=1}^{g-1}U_{i_v}} \ge b \quad ? $$

Any suggestion for proving that this is problem is NP-hard, or, on the other hand, for finding a way to solve the problem in polynomial time?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Simultaneously cross-posted at mathoverflow.net/q/216142 $\endgroup$ – Emil Jeřábek supports Monica Sep 1 '15 at 14:39
  • $\begingroup$ @EmilJeřábek Actually, I posted this question on Math Stackexchange first. After that, Mike Haskell kindly suggested me to post it also on cstheory and math overflow, to have more chances to get a good answer. But, most certainly, I had to wait for a few days between each cross-post. I am sorry for not waiting. If it is better to remove the question for now, I will do it. $\endgroup$ – Paolo Valente Sep 2 '15 at 7:57
  • $\begingroup$ Since it's already posted, it's probably better to leave it as is, but please keep the rule in mind for future. Also, if you crosspost under any circumstances, mention it in the question and include links in both directions. $\endgroup$ – Emil Jeřábek supports Monica Sep 2 '15 at 10:29
  • $\begingroup$ Please do not post the same question on multiple sites. Cross-posting violates site rules. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration. $\endgroup$ – D.W. Sep 3 '15 at 17:30
  • 1
    $\begingroup$ @D.W. I have removed the other copies, so this is now the only remaining copy. I apologize again for the mistake. $\endgroup$ – Paolo Valente Sep 4 '15 at 13:42

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.