OPTIMIZATIONACADEMIC WEBSITE
26 Mar 2019

Efficient Algorithms for the Recoverable (Robust) Selection Problem

We study the Recoverable Selection problem, a generalization of the well-studied classic Selection problem. Given an element set E, two cost vectors \alpha, \beta \in \rr^{E} and two parameters p, q \in \mathbb{N}, we want to find sets A, B \subseteq E such that |A| = |B| = p and |A \cap B| \geq q minimizing the cost \sum_{i \in A} \alpha_{i} + \sum_{j \in B} \beta_{j}.

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.

Comments Off on Efficient Algorithms for the Recoverable (Robust) Selection Problem