Transforming an optimization problem to maxmin formulation

Question

Given $N=mn$ real numbers $a_i$, we seek to partition them into $n$ subsets $S_j$ ($1\le j\le n$), each containing $m$ numbers, so as to maximize $\prod_{j=1}^n \sum_{a_i\in S_j} a_i$. My questions are: (1) Can this problem be cast to a known problem? (2) Given its NP-hardness, how to design approximation algorithms with constant approximation factor?

Answer 1

You can approximate the problem by minimizing the range via integer linear programming. Let binary decision variable $x_{i,j}$ indicate whether number $i\in N$ is assigned to group $j\in\{1,\dots,n\}$. The problem is to minimize $u-\ell$ subject to: \begin{align} \sum_j x_{i,j} &=1 &&\text{for all $i$}\\ \sum_i x_{i,j} &= m &&\text{for all $j$}\\ \ell \le \sum_i a_i x_{i,j} &\le u &&\text{for all $j$} \end{align} To obtain a formulation for the min-max or max-min problem, omit the parts involving $\ell$ or $u$, respectively.

Answer 2

This answer is partial.

We assume that all $a_i$ are non-negative. Put $A=\tfrac 1m \sum a_i$ and $A_j=\sum_{i\in S_j} a_i$. We want to maximize $\Pi=\prod A_j$. But by AM-GM inequality, $P^{1/m}\le \tfrac 1m \sum A_j=A$ and the equality holds iff each $A_j$ equals $A$.

Even when $m=2$ and all $a_i$ are positive integers the problem to check whether the equality can hold is a variant of the partition problem, and at the first reference is stated that it is $NP$-hard (but without a citation). So this should be a known problem and there can be already developed heuristic and approximation algorithms for it.

I guess that a heuristics can be based on some balancing idea, which looks promising when there are no big gaps between $a_i$’s.

For instance, I can propose the following algorithm to find an initial feasible partition. Assign $m$ piles, order $a_i$ in a non-increasing order, and then split this sequence of $a_i$’s into bags $B_1,\dots, B_n$ each containing $m$ consecutive $a_i$’s. An each step we pick a next bag and distribute its $a_i$’s into the piles, one number to each pile, trying to make the vector of the sums of elements of the piles more balanced (a measure of a balancedness of a vector $x=(x_1,\dots,x_m)$ can be a norm (for instance, $\ell_2$ or $\ell_\infty$) of a vector $x-\left(\frac 1m \sum x_i\right) (1,1,\dots,1)$). I guess this should be done as follows: put the biggest element of the bag to the pile with the smallest sum, the second biggest element of the bag to the second smallest sum, and so forth.

The obtained feasible partition (or even a random one) can be further iterative balanced by local search. Namely, given sets $S_1,\dots S_m$ and a small constant $b\ge 1$ (maybe even $b=1$ will provide a good approximation) we check all subsets $C_i$ of size $b$ in each of $S_j$ (so there are ${n\choose b}^m$ possibilities to consider in total). For each of the possibilities we consider a union $C$ of $C_i$ and try to redistribute $C$ between $S_j$ trying to make the sequence of their sums more balanced. In particular, when $b=1$ and $m=2$, we look for indices $i_1\in S_1$ and $i_2\in S_2$ such that when we swap $i_1$ and $i_2$ between $S_1$ and $S_2$, the difference $|A_1-A_2|$ will decrease.