A linear time algorithm for the robust recoverable selection problem

Discrete Applied Mathematics, vol. 303, pp. 94–107

Abstract

The feasible solutions in the robust recoverable selection problem are subsets of size p that are to be selected from a ground set of size n. The objective is to construct a feasible solution in two sequential stages with two separate (but interleaved) cost structures. The fastest algorithm for this problem in the literature up to now has quadratic running time. We improve on this by developing an algorithm with linear running time.

Authors 3

1. Thomas Lachmann

   Johannes Kepler University of Linz

   Affiliation as printed

   Institute of Financial Mathematics and Applied Number Theory, JKU Linz, Austria

2. Stefan Lendl corresponding

   Graz University of Technology

   Affiliation as printed

   Institute of Discrete Mathematics, TU Graz, Austria

3. Gerhard J. Woeginger Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen, Germany