Subset of $k$ vectors with shortest sum, with respect to $\ell_\infty$ norm

Question

I have a collection of $n$ vectors $x_1, ..., x_n \in \mathbb{R}_{\geq 0}^{d}$. Given these vectors and an integer $k$, I want to find the subset of $k$ vectors whose sum is shortest with respect to the uniform norm. That is, find the (possibly not unique) set $W^* \subset \{x_1, ..., x_n\}$ such that $\left| W^* \right| = k$ and

$$W^* = \arg\min\limits_{W \subset \{x_1, ..., x_n\} \land \left| W \right| = k} \left\lVert \sum\limits_{v \in W} v \right\rVert_{\infty}$$

The brute-force solution to this problem takes $O(dkn^k)$ operations - there are ${n \choose k} = O(n^k)$ subsets to test, and each one takes $O(dk)$ operations to compute the sum of the vectors and then find the uniform norm (in this case, just the maximum coordinate, since all vectors are non-negative).

My questions:

1. Is there are a better algorithm than brute force? Approximation algorithms are okay.

One idea I had was to consider a convex relaxation where we assign each vector a fractional weight in $[0, 1]$ and require that the weights sum to $k$. The resulting subset of $\mathbb{R}^d$ spanned by all such weighted combinations is indeed convex. However, even if I we can find the optimum weight vector, I am not sure how to use this set of weights to choose a subset of $k$ vectors. In other words, what integral rounding scheme to use?

I have also thought abut dynamic programming but I'm not sure if this would end up being faster in the worst-case.

2. Consider a variation where we want to find the optimal subset for every $k$ in $[n]$. Again, is there a better approach than solving the problem naively for each $k$? I think there ought to be a way to use the information from runs on subsets of size $k$ to those of size $(k + 1)$ and so on.

3. Consider the variation where instead of a subset size $k$, one is given some target norm $r \in \mathbb{R}$. The task is to find the largest subset of $\{x_1, ..., x_n\}$ whose sum has uniform norm $\leq r$. In principle one would have to search over $O(2^n)$ subsets of the vectors. Do the algorithms change? Further, is the decision version (for example, we could ask if there exists a subset of size $\geq k$ whose sum has uniform norm $\leq r$) of the problem NP-hard?

4. Suppose we now know that our vectors $x_i$ all come from $\{0, 1\}^d$. Does anything change?

Answer 1

The problem is NP-hard by a reduction from https://en.wikipedia.org/wiki/Independent_set_(graph_theory) or set packing.

One approach to solve the problem is to use integer linear programming: define 0-or-1 variables $v_1,\dots,v_n$, and then minimize $t$ subject to the constraints $\|\sum_i v_i x_i \|_\infty \le t$ and $\sum_i v_i = k$. Note that $\|\sum_i v_i x_i \|_\infty \le t$ iff $-t \le \sum_i v_i x_{ij} \le t$ for all $j$, so this can be expressed using linear constraints. Then, apply an off-the-shelf ILP solver and hope it terminates in a reasonable amount of time.

(The ILP solver will probably apply methods such as solving the associating linear program and then applying randomized rounding, so you don't need to implement it yourself.)

If $d$ is very small, it might be possible to solve the problem in something like $\tilde{O}(dkn^{k/2})$ time using meet-in-the-middle search combined with a nearest-neighbor data structure, but I haven't worked out the details, and I expect it won't scale to large $d$.