11
$\begingroup$

I'd like to learn something about this optimization problem: For given non-negative whole numbers $a_{i,j,k}$, find a function $f$ minimizing the expression

$$\max_k \sum_i a_{i,f(i),k}$$

An example using a different formulation might make it clearer: You're given a set of sets of vectors like

{
    {(3, 0, 0, 0, 0), (1, 0, 2, 0, 0)},
    {(0, 1, 0, 0, 0), (0, 0, 0, 1, 0)},
    {(0, 0, 0, 2, 0), (0, 1, 0, 1, 0)}
}

Choose one vector from each set, so that the maximum component of their sum is minimal. For example, you may choose

(1, 0, 2, 0, 0) + (0, 1, 0, 0, 0) + (0, 1, 0, 1, 0) = (1, 1, 2, 1, 0)

with the maximum component equal to 2, which is clearly optimal here.

I'm curious if this is a well-known problem and what problem-specific approximate solution methods are available. It should be fast and easy to program (no ILP solver, etc.). No exact solution is needed as it's only an approximation of the real problem.


I see that I should have added some details about the problem instances I'm interested in:

  • $i \in \{0, 1, \ldots, 63\}$, i.e., there're always 64 rows (when written as in the above example).
  • $j \in \{0, 1\}$, i.e., there're only 2 vectors per row.
  • $k \in \{0, 1, \ldots, N-1\}$ where $N$ (the vector length) is between 10 and 1000.

Moreover, on each row the sum of the elements of all vectors is the same, i.e.,

$$\forall i, j, j':\quad \sum_k a_{i,j,k} = \sum_k a_{i,j',k}$$

and the sum of the elements of the sum vector is less than its length, i.e.,

$$\sum_k \sum_i a_{i,f(i),k} < N$$

$\endgroup$
  • 4
    $\begingroup$ It is not hard to reduce the 3-partition problem to your problem. This means that your problem is NP-complete even if the numbers are given in unary, and this rules out one of the common approaches for an approximation algorithm. $\endgroup$ – Tsuyoshi Ito Jul 14 '12 at 14:56
  • $\begingroup$ Thanks for the corrections and thanks to @Tsuyoshi Ito for the insight. If I understand it correctly, the restriction to two vectors per line (which I forgot to state) invalidates the reduction and may make the problem much easier. $\endgroup$ – maaartinus Jul 15 '12 at 10:41
  • $\begingroup$ You are right, the reduction from the 3-partition problem I was thinking of does not work if there are only two vectors per row. $\endgroup$ – Tsuyoshi Ito Jul 15 '12 at 12:07
  • $\begingroup$ So there are $j^i$ combinations to compare? $\endgroup$ – Jason Kleban Jul 15 '12 at 18:28
  • $\begingroup$ @uosɐſ: To be precise, there are $J^I=2^{64}$ possible combinations, where $J=2$ is the number of possibilities for $j$ and $I=64$ is the number of possibilities for $i$. $\endgroup$ – maaartinus Jul 15 '12 at 23:54
7
$\begingroup$

Reduction from 3SAT to the two-vector version: given a formula, let $i$ index variables, $j \in \{0,1\}$, and $k$ index clauses. Let $a_{i,j,k}$ be the number of times variable $i$ appears positively (if $j = 0$) or negatively (if $j = 1$) in clause $k$. OPT is less than $3$ iff the formula is satisfiable (the bijection is obvious).

How I would attack this problem: large neighborhood search. Start with any solution. Choose $r$ rows at random. Use brute force to find the best solution where $f$ can change only on those rows—very doable for even moderate $k$ given that the problem size is $64$ rows. Repeat.

$\endgroup$
  • 1
    $\begingroup$ This is a beautiful reduction. I am not sure why it does not have any up-votes. Anyway, here is my +1. $\endgroup$ – Tsuyoshi Ito Jul 25 '12 at 16:51
  • $\begingroup$ I think you should elaborate a tad more on the reduction. In particular, you have $f$ hidden well, maybe too well, as it makes the bijection a bit hard to see. $\endgroup$ – Raphael Jul 30 '12 at 13:53
7
$\begingroup$

We cannot discuss the complexity of a problem when the problem size is fixed to a constant, because (most part of) the complexity theory deals with the asymptotic behavior of the complexity of the problem as the problem size tends to infinity. Here, I consider both the number of rows and the dimention of the vectors as variables.

Then the problem is NP-complete even if the numbers in the input are given in unary. This is not an answer to your question because you are asking about approximation, but it is something.

Define the problem rigorously:

Instance: n pairs of vectors ai, bi ∈ ℕm (i ∈ {1, …, n}), and K ∈ ℕ, all in unary.
Question: Can we choose either ai or bi for each i so that the sum of these n vectors has at most K in each coordinate?

The following is a known NP-complete problem called 3-partition:

3-partition
Instance: B ∈ ℕ, and 3k integers c1, …, c3k between B/4 and B/2, exclusive, such that ∑i=13k ci = kB, all in unary.
Question: Can the multiset {c1, …, c3k} be partitioned into k multisets S1, …, Sk such that the sum of each Sj is equal to B?

Given an instance (B; c1, …, c3k) of the 3-partition problem, construct an instance of the above problem as follows. For each i = 1, …, 3k and j = 1, …, k, we will construct a pair of 4k-dimensional vectors, representing the choice on whether ci belongs to Sj or not:

  • The vector representing the choice “ciSj” has only one nonzero entry, which is (k−1)ci at the jth coordinate.
  • The vector representing the choice “ciSj” also has only one nonzero entry, which is B at the (k+i)-th coordinate.

It is not hard to see that the instance (B; c1, …, c3k) of the 3-partition problem has a solution if and only if there is a way to choose a vector from each of the 3k2 constructed pairs so that all the coordinates of the sum of these vectors are at most (k−1)B. (In fact, when this happens, all the coordinates of the sum are equal to (k−1)B.) So this is a reduction from the 3-partition problem to the above problem.

So far, I ignored the two additional constraints stated at the end of the question, but both are easy to enforce by modifying this reduction slightly. The condition that the sum of the elements of each vector is equal can be enforced by appending dummy coordinates which contain only 0 or 1. The condition that this sum is less than the dimension can be enforced by appending dummy coordinates which contain only 0.

$\endgroup$
  • $\begingroup$ Nice answer, just some notes: 1. I don't care about the theoretical complexity here. 2. The number of rows is fixed and can stay so, as varying $N$ suffices. That said, thanks a lot. $\endgroup$ – maaartinus Dec 31 '12 at 4:45

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.