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

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.

1. 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.

2. 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?

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

• Welcome to CS.SE! What are typical values of $n,d,k$ for the kinds of problems you want to solve? Do you want an algorithm that always returns the optimal set $W^*$, or are you ok with approximation algorithms that return a set that is not optimal? – D.W. Mar 27 at 2:06
• Thank you for the welcome! Approximation algorithms are fine although I would prefer to find an exact solution if I can. – Akhil Jalan Mar 27 at 5:56
• For the application I have in mind, approximate ranges would be $10 \leq d \leq 100$, $100 \leq n \leq 1000$, and I would want to solve for all $k \in [n]$. If forced to pick values for $k$ I would want evenly spaced $k$ in $[n]$, for example $k = 0.1n, 0.2n, ..., 0.9n$. – Akhil Jalan Mar 27 at 5:57

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.
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$$.
• Thank you, this certainly answers my question about NP-hardness. For reference my application involves an approximate range of $10 \leq d \leq 100$. I'm not sure if this is the range of "small $d$" you had in mind. What kinds of guarantees exist for these ILP solvers? I assume they use some sort of approximation algorithms. Do we know of polynomial-time algorithms with constant approximation factors for set packing, for example? – Akhil Jalan Mar 27 at 6:09