= Solution
The required <linear program> is
$$
\boxed{f_k(x)=\max_{y\in\mathbb R^n}\left\{x^Ty:y_i\geq0,\ y_i\leq1\ (1\leq i\leq n),\ \sum_i y_i=k\right\}.}
$$
There are $2n$ inequality constraints and one equality constraint, all independent of $x$.
The feasible set is the <capped simplex>, a nonempty <compact set>. A <linear function> attains its maximum at an <extreme point>; the previous part identifies these as the indicators of $k$-element subsets. At such a <vector>, the objective is the sum of the selected coordinates. Maximizing selects the $k$ largest coordinates, including when some are negative or tied. Equivalently, $f_k$ is the <support function> called the <sum of the largest components>.
Back to article page
