We study the Recoverable Selection problem, a generalization of the well-studied classic Selection problem. Given an element set , two cost vectors and two parameters , we want to find sets such that and minimizing the cost .
We show that a simple greedy algorithm solves this problem to optimality. By a detailed mathematical analysis of the solution structure, we obtain discrete-convexity and unimodality results for parameterized objective functions related to this problem. Using this, we obtain an asymptotically optimal linear time algorithm for the problem, matching the optimal asymptotic running time of the classic Selection problem.