<p>In our research, we faced the following problem optimization problem:</p>

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

<p>$$\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.
<br>
We tried to prove that it is NP-hard by reducing it to 3-Partition, 
but we couldn't.</p>

<p>Is this problem NP-hard?</p>

CC BY-SA 3.0
2015-07-28T23:37:36.140Z
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.
chazisop
CC BY-SA 3.0
2015-07-29T03:34:13.890Z
I think the OP means "complex" as "not simple", not as "not real"
Suresh Venkat
CC BY-SA 3.0
2015-07-29T03:36:54.200Z
I don't understand what the inner summation $\sum d_i$ is over
Suresh Venkat
CC BY-SA 3.0
2015-07-29T17:03:53.627Z
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.
LaplacePuzzle
<cc.complexity-theory><np-hardness><optimization><partition-problem>
NP-hardness of minimizing sum of complicated objective function
user34956
# NP-hardness of minimizing sum of complicated objective function

(Asked by: username_0 on 2015-07-28)

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?

**Tags:** cc.complexity-theory, np-hardness, optimization, partition-problem
> **Comments:**
> **username_1**: 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.  
> **username_2**: I think the OP means "complex" as "not simple", not as "not real"  
> **username_2**: I don't understand what the inner summation $\sum d_i$ is over  
> **username_3**: 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.  

---

## 0 answers

