Given a set of sets of vectors $V=\{V_1=\{v_{11},v_{12},..,v_{1n}\},...,V_m\{v_{m1},v_{m2},..,v_{mn}\}\}$,$v_{ij} \in\{-1,0,1\}^r$. We choose one vector from each set, so that the maximum component of their sum is minimal. Can you advise on how best to approximate the optimal solution of the problem?
UPD: I'm interested in case m=256,n=65536,r=256.
You can solve the problem via mixed integer linear programming as follows. Let binary decision variable $x_{i,j}$ indicate whether vector $v_{i,j}$ is chosen, and let $z$ represent the maximum component of the sum of the chosen vectors. The problem is to minimize $z$ subject to \begin{align} \sum_{j=1}^n x_{i,j} &= 1 &&\text{for $i\in\{1,\dots,m\}$} \tag1 \\ \sum_{i=1}^m \sum_{j=1}^n (v_{i,j})_k x_{i,j} &\le z &&\text{for $k\in\{1,\dots,r\}$} \tag2 \end{align} Constraint $(1)$ chooses one vector from each set. Constraint $(2)$ enforces the min-max objective.