Minimize the maximum component of a sum of vectors

Question

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$$

Answer 1

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.

Answer 2

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 a_i, b_i ∈ ℕ^m (i ∈ {1, …, n}), and K ∈ ℕ, all in unary.
Question: Can we choose either a_i or b_i 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 c₁, …, c_3k between B/4 and B/2, exclusive, such that ∑_i=1^3k c_i = kB, all in unary.
Question: Can the multiset {c₁, …, c_3k} be partitioned into k multisets S₁, …, S_k such that the sum of each S_j is equal to B?

Given an instance (B; c₁, …, c_3k) 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 c_i belongs to S_j or not:

• The vector representing the choice “c_i ∈ S_j” has only one nonzero entry, which is (k−1)c_i at the jth coordinate.
• The vector representing the choice “c_i ∉ S_j” 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; c₁, …, c_3k) of the 3-partition problem has a solution if and only if there is a way to choose a vector from each of the 3k² 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.