Return to Question

I have a set of multisets $S = \{ X_1, \dots, X_K\}$ where $X_i \subset \mathbb{R}$. I need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. Denote $K(X) = \cup_{I \in X} I$, then $E(X) := \sum_{i \in K(X)} |i - \text{median}(K(X))|$, where $|.|$ is the absolute value. $X_i$ might contains duplicated elements and all operations are on multisets; in $K(X)$, $\cup$ is a union of multisets, and in $E(X)$, $\sum$ adds "with repetition" (repeated elements are summed multiple times).

I want to prove this problem is hard, but I don't have a very straightforward way to prove it's NP-complete. What I did instead was assuming given extra information, suppose I know the median of both $K(L^*)$ and $K(R^*)$, and then I can show find the optimal partition is an integer linear programming problem, which is NP-complete. Can I conclude the original problem is at least NP-complete?

For the sake of sharing, a wrong attempt I did on proving NP-completeness of with extra information problem.

I was converting this "given $m_L = \textbf{median}(L), m_R = \textbf{median}(R)$ and $S$, find $L$ and $R$" problem into a integer programming feasibility problem. Thanks to D.W helped me, I should do the opposite. Maybe doing the opposite is also possible. So sharing my effort in case it helps.

We can collect two vectors $A, B$ with length $K$, for every $X_i \in S$, get the imbalance with respect to $m_L$ and $m_R$. Namely $A[i] = \sum_{j \in X_i} sign(m_L - j) $, $B[i] = \sum_{j \in X_i} sign(m_R - j) $, where $$\text{sign}(x) = \begin{cases} 1 &\text{if }x>0\\ 0 &\text{if }x=0\\ -1 &\text{if }x<0 \end{cases}$$

Now we can introduce another boolean indicator vector $I = \{0, 1\}^K$. When $I[i] = 0$, we assign $X_i$ to $L$, if $I[i] = 1$, we assigns $X_i$ to $R$.

$$ \langle I, A \rangle = 0 \\ \langle 1-I, B \rangle = 0 $$ Since $m_l$ is the median of $L$, we would definitely have the sum of imbalance equals to 0. The same applies to $m_R$.

And clearly, the newly formed problem is an integer programming problem. Which is well-known NP-complete. Whether if it is possible to convert any such type of problem into our set partition problem in polynomial time, I still need some help

I have a set of multisets $S = \{ X_1, \dots, X_K\}$ where $X_i \subset \mathbb{R}$. I need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. Denote $K(X) = \cup_{I \in X} I$, then $E(X) := \sum_{i \in K(X)} |i - \text{median}(K(X))|$, where $|.|$ is the absolute value. $X_i$ might contains duplicated elements and all operations are on multisets; in $K(X)$, $\cup$ is a union of multisets, and in $E(X)$, $\sum$ adds "with repetition" (repeated elements are summed multiple times).

I want to prove this problem is hard, but I don't have a very straightforward way to prove it's NP-complete. What I did instead was assuming given extra information, suppose I know the median of both $K(L^*)$ and $K(R^*)$, and then I can show find the optimal partition is an integer linear programming problem, which is NP-complete. Can I conclude the original problem is at least NP-complete?

For the sake of sharing, a wrong attempt I did on proving NP-completeness of with extra information problem.

I was converting this "given $m_L = \textbf{median}(L), m_R = \textbf{median}(R)$ and $S$, find $L$ and $R$" problem into a integer programming feasibility problem. Thanks to D.W helped me, I should do the opposite. Maybe doing the opposite is also possible. So sharing my effort in case it helps.

We can collect two vectors $A, B$ with length $K$, for every $X_i \in S$, get the imbalance with respect to $m_L$ and $m_R$. Namely $A[i] = \sum_{j \in X_i} sign(m_L - j) $, $B[i] = \sum_{j \in X_i} sign(m_R - j) $, where $$\text{sign}(x) = \begin{cases} 1 &\text{if }x>0\\ 0 &\text{if }x=0\\ -1 &\text{if }x<0 \end{cases}$$

Now we can introduce another boolean indicator vector $I = \{0, 1\}^K$. When $I[i] = 0$, we assign $X_i$ to $L$, if $I[i] = 1$, we assigns $X_i$ to $R$.

$$ \langle I, A \rangle = 0 \\ \langle 1-I, B \rangle = 0 $$

Since $m_l$ is the median of $L$, we would definitely have the sum of imbalance equals to 0. The same applies to $m_R$. And here $A, B$ are coefficients and $I$ is the variable. If such a problem has any solutions, then we found $L$, $R$.

And clearly, the newly formed problem is an integer programming problem. Which is well-known NP-complete. Whether if it is possible to convert any such type of problem into our set partition problem in polynomial time, I still need some help

I have a set of multisets $S = \{ X_1, \dots, X_K\}$ where $X_i \subset \mathbb{R}$. I need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. Denote $K(X) = \cup_{I \in X} I$, then $E(X) := \sum_{i \in K(X)} |i - \text{median}(K(X))|$, where $|.|$ is the absolute value. $X_i$ might contains duplicated elements and all operations are on multisets; in $K(X)$, $\cup$ is a union of multisets, and in $E(X)$, $\sum$ adds "with repetition" (repeated elements are summed multiple times).

I want to prove this problem is hard, but I don't have a very straightforward way to prove it's NP-complete. What I did instead was assuming given extra information, suppose I know the median of both $K(L^*)$ and $K(R^*)$, and then I can show find the optimal partition is an integer linear programming problem, which is NP-complete. Can I conclude the original problem is at least NP-complete?

I have a set of multisets $S = \{ X_1, \dots, X_K\}$ where $X_i \subset \mathbb{R}$. I need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. Denote $K(X) = \cup_{I \in X} I$, then $E(X) := \sum_{i \in K(X)} |i - \text{median}(K(X))|$, where $|.|$ is the absolute value. $X_i$ might contains duplicated elements and all operations are on multisets; in $K(X)$, $\cup$ is a union of multisets, and in $E(X)$, $\sum$ adds "with repetition" (repeated elements are summed multiple times).

I want to prove this problem is hard, but I don't have a very straightforward way to prove it's NP-complete. What I did instead was assuming given extra information, suppose I know the median of both $K(L^*)$ and $K(R^*)$, and then I can show find the optimal partition is an integer linear programming problem, which is NP-complete. Can I conclude the original problem is at least NP-complete?

For the sake of sharing, a wrong attempt I did on proving NP-completeness of with extra information problem.

I was converting this "given $m_L = \textbf{median}(L), m_R = \textbf{median}(R)$ and $S$, find $L$ and $R$" problem into a integer programming feasibility problem. Thanks to D.W helped me, I should do the opposite. Maybe doing the opposite is also possible. So sharing my effort in case it helps.

We can collect two vectors $A, B$ with length $K$, for every $X_i \in S$, get the imbalance with respect to $m_L$ and $m_R$. Namely $A[i] = \sum_{j \in X_i} sign(m_L - j) $, $B[i] = \sum_{j \in X_i} sign(m_R - j) $, where $$\text{sign}(x) = \begin{cases} 1 &\text{if }x>0\\ 0 &\text{if }x=0\\ -1 &\text{if }x<0 \end{cases}$$

Now we can introduce another boolean indicator vector $I = \{0, 1\}^K$. When $I[i] = 0$, we assign $X_i$ to $L$, if $I[i] = 1$, we assigns $X_i$ to $R$.

$$ \langle I, A \rangle = 0 \\ \langle 1-I, B \rangle = 0 $$ Since $m_l$ is the median of $L$, we would definitely have the sum of imbalance equals to 0. The same applies to $m_R$.

And clearly, the newly formed problem is an integer programming problem. Which is well-known NP-complete. Whether if it is possible to convert any such type of problem into our set partition problem in polynomial time, I still need some help

Suppose, I have a set of mulltisets $S = \{ X_1, \cdots, X_i, \cdots, X_K\}, X_i \subset \mathbb{R}$ and need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. It is rather hard, so I want to prove it's hard. Denote $K(X) = \cup_{I \in X} I$, $E(X) := \sum_{i \in K(X)} |i - \textbf{median}(K(X))|$. And $|.|$ is the absolute value. $X_i$ might contains duplicated element and in $K(X)$, the union of multiset is defined as concatinating. $ \exists X_i,X_j \in S, i\neq j, X_i \cap X_j \neq \emptyset$.

But I don't have a very straightforward way to prove it's NP-complete. What I did instead was assuming given extra information, suppose I know the median of both $K(L^*)$ and $K(R^*)$, and then I can show find the optimal partition is an integer linear programming problem, which is NP-complete.

Can I conclude the original problem is at least NP-complete?

I have a set of multisets $S = \{ X_1, \dots, X_K\}$ where $X_i \subset \mathbb{R}$. I need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. Denote $K(X) = \cup_{I \in X} I$, then $E(X) := \sum_{i \in K(X)} |i - \text{median}(K(X))|$, where $|.|$ is the absolute value. $X_i$ might contains duplicated elements and all operations are on multisets; in $K(X)$, $\cup$ is a union of multisets, and in $E(X)$, $\sum$ adds "with repetition" (repeated elements are summed multiple times).

I want to prove this problem is hard, but I don't have a very straightforward way to prove it's NP-complete. What I did instead was assuming given extra information, suppose I know the median of both $K(L^*)$ and $K(R^*)$, and then I can show find the optimal partition is an integer linear programming problem, which is NP-complete. Can I conclude the original problem is at least NP-complete?