New answers tagged

2

The answer to Question (1) is no. The answer to Question (2) is yes. Here are the details. I'll work with the following equivalent problem formulations. For the input, we are given $n$ pairs of values $(v_1, w_1), (v_2, w_2), \ldots, (v_n, w_n)$ in $\mathbb R^2_+$. Problem A. Find $\max\big\{ \sum_{i\not\in S} v_i : S\subseteq [n],\, \sum_{i\not\in S} w_i ...


Top 50 recent answers are included