In our research, we faced the following problem optimization problem:

Input: a list of $k$ pairs of positive integers $(n_1,d_1), \ldots, (n_k,d_k)$; an integer $m$.
Output: $P$, a partition of the pairs into $m$ nonempty classes,
such that the following objective function is minimized:

$$\sum_{C \in P}\left( \left(\sum_{i \in C} d_i\hspace{-0.08 in}\right) \cdot \left(\sqrt{\frac{ 2\log(4\sum_{i\in C} d_i)}{\sum_{i \in C}n_i}} + \sqrt{\frac{ \log(2\sum_{i\in C} d_i)}{\sum_{i \in C}n_i}}\hspace{.04 in}\right)\hspace{-0.04 in} \right)$$ We think that the problem is NP-hard, but we have not been able to prove this.
We tried to prove that it is NP-hard by reducing it to 3-Partition, but we couldn't.

Is this problem NP-hard?

  • $\begingroup$ Note: Accepted edit since I couldn't view the effects otherwise. Rollbacked because the change did not improve the formula and the second part did not make sense. See edit history for details. $\endgroup$
    – chazisop
    Commented Jul 28, 2015 at 23:37
  • $\begingroup$ I think the OP means "complex" as "not simple", not as "not real" $\endgroup$ Commented Jul 29, 2015 at 3:34
  • $\begingroup$ I don't understand what the inner summation $\sum d_i$ is over $\endgroup$ Commented Jul 29, 2015 at 3:36
  • $\begingroup$ The formulation is wrong. Tried to correct, but was not able to do it. The correct one is $\sum_{C_j}\left(\left(\sum_{I_i \in C_j}d_i\right)\left(\sqrt{\frac{2\log(4\sum_{I_i \in C_j}d_i)}{\sum_{I_i \in C_j}n_i}} + \sqrt{\frac{\log(2\sum_{I_i \in C_j}d_i)}{\sum_{I_i \in C_j}n_i}}\right)\right)$ Hope this formula makes sense. $\endgroup$ Commented Jul 29, 2015 at 17:03


Your Answer

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