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


Only top voted, non community-wiki answers of a minimum length are eligible