<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-01T14:39:49.060Z
Simultaneously cross-posted at http://mathoverflow.net/q/216142
Emil Jeřábek
CC BY-SA 3.0
2015-09-02T07:57:39.207Z
@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-02T10:29:20.787Z
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.
Emil Jeřábek
CC BY-SA 3.0
2015-09-03T17:30:42.323Z
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-04T13:42:15.143Z
@D.W. I have removed the other copies, so this is now the only remaining copy. I apologize again for the mistake.
Paolo Valente
<np-hardness><time-complexity>
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
> **Comments:**
> **username_1**: Simultaneously cross-posted at http://mathoverflow.net/q/216142  
> **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**: 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.  
> **username_2**: 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**: @D.W. I have removed the other copies, so this is now the only remaining copy. I apologize again for the mistake.  

---

## 0 answers

