1
$\begingroup$

It is given n sets with k vectors. (k is element-wise positive or zero) Choose one vector of each set so that the biggest element of the sum of the chosen vectors is minimal.

What i also know but is more problem specific is that the vector are very sparse (has very few non-zero entries and all non-zero entries appear in a row(next to each other)) Each vector in the same set has the same values but which some shift.

Two example sets:

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

I'm interested if this problem can be reduced to some known problem.

Currently i did not find something suitable in literature.

Or Maybe you know a good idea for a heuristic.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ That's another universal one ("NP-complete" to use a scientific language). Let's reduce the graph 3-coloring to it. Make 3 copies of the same $n$-vertex graph. All edges are the placeholders for entries. Each set has 3 vectors: choose a vertex and put $1$ on every incident edge in one of 3 graphs, after which put 0 on all remaining edges of all graphs. The graph is 3-colorable iff the minimax equals $1$. Actually, your the setup is so flexible, that it is hard to find a problem that cannot be stated in these terms. So, alas, no good news to expect. $\endgroup$
    – fedja
    Commented Jun 17, 2014 at 22:24

0

Reset to default

You must log in to answer this question.