The Task
You are given $n$ columns each of length $m$. All values are either $-1$ or $1$. Find an assignment $s$ of each of columns to 1 of $m$ groups in order to maximize the sum of all the absolute values of group row sums.
For example
Suppose
$$n=7,$$ $$m=3,$$ $$a=\left( \begin{array}{ccccccc} -1 & -1 & 1 & 1 & -1 & -1 & -1 \\ -1 & -1 & 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & -1 & 1 & 1 & 1 & 1 \\ \end{array} \right), $$ $$s=\{\{1,5\},\{2,3,6,7\},\{4\}\}$$
In order to compute the quantity we want to maximize $v(a,s)$:
First, identify the groups of columns we chose. (Each list in $s$ in a collection of columns indexes.)
$$
\{
\left(
\begin{array}{cc}
-1 & -1 \\
-1 & 1 \\
1 & 1 \\
\end{array}
\right)
,
\left(
\begin{array}{cccc}
-1 & 1 & -1 & -1 \\
-1 & 1 & -1 & 1 \\
1 & -1 & 1 & 1 \\
\end{array}
\right)
,
\left(
\begin{array}{c}
1 \\
-1 \\
1 \\
\end{array}
\right)
\}
$$
For each row in each group, take the sum and then the absolute value. $$\{\left( \begin{array}{c} 2 \\ 0 \\ 2 \\ \end{array} \right), \left( \begin{array}{c} 2 \\ 0 \\ 2 \\ \end{array} \right), \left( \begin{array}{c} 1 \\ 1 \\ 1 \\ \end{array} \right)\}$$
$v(a,s)$ is the sum of all values: $$v(a,s)=11$$
Formally
Choose $s$ to maximize $$v(a,s)=\sum _{i=1}^m \sum _{j=1}^m \left| \sum _{c=1}^{\left| s_i\right| } a_{j,s_{i,c}}\right|$$
Subject to $$\cup _{i=1}^ms_i=\{1...n\}$$
My Question
I have been trying to find an efficient algorithm to solve this task, without much luck. Towards progress, I have found that if you add additional columns, the columns in the existing optimal groups will not necessarily stay together (ruling out a particular kind of dynamic programming approach). This task is relevant towards mechanism design in game theory.
(1) Does anyone know an efficient algorithm that solves the task? (2) Alternatively, is it NP-hard?
