2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ (For effective line breaks in mark-down, append two spaces to the line you want a break after.) $\endgroup$
    – greybeard
    Nov 21 at 6:54
  • $\begingroup$ In your example, shouldn't the first group be $(2,0,2)$ instead of $(2,2,2)$? $\endgroup$ Nov 21 at 6:55
  • $\begingroup$ We prefer that you avoid "EDIT:", or just appending stuff at the bottom; we'd prefer that you revise the question to read well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755. $\endgroup$
    – D.W.
    Nov 21 at 9:08
  • $\begingroup$ @InuyahaYagami Yes, I have fixed it. Thanks. $\endgroup$
    – k-0348
    Nov 22 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.