<p>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.</p>

<p>Given:</p>

<ul>
<li>a set $\tau$ of $N$ pairs $(C_i, U_i) \in \mathbb{Q}^2$, with
$C_i &gt; 0$ and $0 &lt; U_i \le 1$ for all
$i \in \{1, 2, \ldots, N\}$,</li>
<li>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$),</li>
<li>an integer $M'$ with $1 \le M' \le M$,</li>
<li>a strictly positive value $b \in \mathbb{Q}$;</li>
</ul>

<p>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 ?
 $$</p>

<p>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?</p>

CC BY-SA 3.0
2015-09-02T07:48:14.340Z
@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.
Paolo Valente
CC BY-SA 3.0
2015-09-03T17:30:15.593Z
Please [do not post the same question on multiple sites](http://meta.stackexchange.com/q/64068). 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.
D.W.
CC BY-SA 3.0
2015-09-04T07:35:25.137Z
@usul I have removed the question from Mathematics, so it should appear only here now. Sorry for the mistake.
Paolo Valente
CC BY-SA 3.0
2015-09-04T12:42:48.900Z
I am closing this one, so we don't have multiple copies of the same question.
Lev Reyzin
<np-hardness><time-complexity><np-complete>
Is this permutation-sum problem NP-complete?
Paolo Valente
# Is this permutation-sum problem NP-complete?

(Asked by: username_0 on 2015-09-01)

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?

**Tags:** np-hardness, time-complexity, np-complete

> **Comments:**
> **username_0**: @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.  
> **username_1**: Please [do not post the same question on multiple sites](http://meta.stackexchange.com/q/64068). 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.  
> **username_0**: @usul I have removed the question from Mathematics, so it should appear only here now. Sorry for the mistake.  
> **username_2**: I am closing this one, so we don't have multiple copies of the same question.  

---

## 0 answers

