Aliens Needs A Curve

The Aliens trick removes an exact- $k$ constraint by charging a penalty $\lambda$ per selected item and binary searching $\lambda$ . What has to be true, and what is the failure mode when it is not?

The relaxed problem must be solvable in $O(n)$ . Varying $\lambda$ sweeps a line of that slope across the lower hull of the feasible $(g(x), f(x))$ points, and every feasible point is the minimizer for some $\lambda$ , so any penalty eventually produces it.

The optimum as a function of the count must be convex. Varying $\lambda$ sweeps a line of that slope across the lower hull of the feasible $(g(x), f(x))$ points, and a point strictly inside the hull is never the minimizer for any $\lambda$ , so no penalty ever produces it.

The optimum as a function of the count must be monotone. Varying $\lambda$ sweeps a line of that slope across the lower hull of the feasible $(g(x), f(x))$ points, and a point strictly inside the hull is still reachable for some $\lambda$ , so the reported objective stays optimal.

The count $k$ must be a power of two. Varying $\lambda$ sweeps a line of that slope across the lower hull of the feasible $(g(x), f(x))$ points, and a point whose count is not a power of two is never the minimizer for any $\lambda$ , so no penalty ever produces it.