2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Mar 27 at 2:06
  • $\begingroup$ Thank you for the welcome! Approximation algorithms are fine although I would prefer to find an exact solution if I can. $\endgroup$ – Akhil Jalan Mar 27 at 5:56
  • $\begingroup$ 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$. $\endgroup$ – Akhil Jalan Mar 27 at 5:57
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Akhil Jalan Mar 27 at 6:09
  • $\begingroup$ @AkhilJalan, got it, thanks. That sounds like an intermediate range where I don't know how to make a good nearest-neighbor data structure but I don't have a good sense for whether it might be possible. ILP solvers come with very few guarantees; think of them as a heuristic. In principle they are guaranteed to find the optimal solution if you run them long enough but their worst-case running time is exponential, so that's not a very useful guarantee. Some provide an option to run for a set amount of time and return the best solution found so far. They're not an approx. algorithm. $\endgroup$ – D.W. Mar 27 at 6:22
  • $\begingroup$ Your last question sounds worth asking separately (use the 'Ask Question' button) after doing some research to see what you can find. $\endgroup$ – D.W. Mar 27 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.