Parition a multiset of numbers into two subsets, how to maximize the sum of their medians?

Given a multiset $$S$$ of numbers, partition it into two subsets $$S_1$$ and $$S_2$$. How to maximize the sum of their medians? For example, the median of {1,2} is 1.5.

I've found a greedy algorithm that $$S_1$$ contains the maximum of $$S$$ (if multiple, select one), $$S_2$$ contains the rest of $$S$$. It's intuitively correct but I can't prove it.

1 Answer

Your algorithm is correct. The following is its proof of correctness.

Let $$S_1$$ and $$S_2$$ be the optimal partitions of $$S$$. Let their medians be $$m_1$$ and $$m_2$$. Let the maximum element is $$M$$ that belongs to $$S_1$$ (without loss of generality). Let $$m$$ is the median of $$S_1 \cup S_2 \setminus \{M\}$$. Then, we can show that the value $$M + m$$ is at least $$m_1+m_2$$.

Proof: When we merge the sets: $$S_1 \setminus \{M\}$$ and $$S_2$$. Then, in $$S_1 \cup S_2 \setminus \{M\}$$, there are at least $$\lfloor |S_1|/2 \rfloor + \lfloor |S_2|/2 \rfloor-1$$ elements that are larger than $$\min\{m_1,m_2\}$$. Suppose there are at least $$\lfloor |S_1|/2 \rfloor + \lfloor |S_2|/2 \rfloor$$ elements larger than $$\min\{m_1,m_2\}$$; then, we are done. That is, $$\lfloor |S_1|/2 \rfloor + \lfloor |S_2|/2 \rfloor \geq \lfloor (|S_1|+|S_2|-1)/2 \rfloor$$, the median $$m$$ of $$S_1 \cup S_2 \setminus \{M \}$$ has value at least $$\min\{m_1,m_2\}$$. Since $$M \geq \max\{m_1,m_2\}$$. We get $$m+M \geq m_1 + m_2$$. Hence proved.

Therefore, let us assume that there are exactly $$\lfloor |S_2|/2 \rfloor + \lfloor |S_2|/2 \rfloor-1$$ elements that are larger than $$\min\{m_1,m_2\}$$. Let us make some cases:

Case 1: $$|S_1|$$ and $$|S_2|$$ are odd. In this case, there are always $$\lfloor |S_2|/2 \rfloor + \lfloor |S_2|/2 \rfloor$$ elements with value larger than $$\min\{m_1,m_2\}$$. So we are done.

Case 2: $$|S_1|$$ and $$|S_2|$$ are even. Let $$m_1 = \frac{(l_1+r_1)}{2}$$ and $$m_2 = \frac{(l_2+r_2)}{2}$$ such that $$l_1,r_1$$ are middle elements of $$S_1$$, and $$l_2,r_2$$ are middle elements of $$S_2$$. Note that in $$S_1 \cup S_2 \setminus \{M\}$$, there are at least $$\lfloor |S_1|/2 \rfloor + \lfloor |S_2|/2 \rfloor$$ elements larger than $$\min\{l_1,l_2\}$$. Therefore, observe that the median $$m$$ is at least $$\max\{l_1,l_2\}$$ or $$\min\{r_1,r_2\}$$. Since $$M \geq \max\{r_1,r_2\}$$, it is easy to see that $$m+M$$ is at least $$\frac{(l_1+r_1)}{2} + \frac{(l_2+r_2)}{2} = m_1 + m_2$$. Hence proved.

Case 3: $$|S_1|$$ is odd and $$|S_2|$$ is even. Let $$m_2 = \frac{(l_2+r_2)}{2}$$ such that $$l_2,r_2$$ are middle elements of $$S_2$$. Note that the median of $$S_1 \cup S_2 \setminus \{M\}$$ is either at least $$m_1$$ or $$\frac{(l_2+r_2)}{2}$$ or $$\frac{(l_2+m_1)}{2}$$. Since $$M \geq \max\{m_1,l_2,r_2\}$$, it is easy to see that $$m+M$$ is at least $$m_1+m_2$$ for each of the possible values of $$m$$. Hence proved.

Case 4: $$|S_1|$$ is even and $$|S_2|$$ is odd. It is similar to Case 3.

• You said ⌊|S1|/2⌋+⌊|S2|/2⌋≥⌊(|S1|+|S2|−1)/2⌋, however you forget that M >= min(m1, m2), so the inference m >= min(m1, m2) is wrong. An example S1=[-1,100,500]; S2=[1,200]. Though you assume S1 and S2 are the the optimal partition, this condition is not used. Jan 20, 2022 at 8:11
• @Voyager For even sized array, how are you defining the median? Jan 20, 2022 at 10:22
• As same as median wikipedia page Jan 20, 2022 at 10:25
• @Voyager True. I will fix my answer. Else, I will delete it. Thanks for pointing out the mistake. I wrote the proof thinking of odd-sized subsets $S_1$ and $S_2$. Jan 20, 2022 at 11:01
• The solution to the problem of maximising the median looks so obvious, and then turns out to be really hard… Thanks for that answer. Rare to find a problem that looks that obvious intuitively and is that hard. Jan 20, 2022 at 21:53