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
-
Johannes Kepler University of Linz
Affiliation as printed
Institute of Financial Mathematics and Applied Number Theory, JKU Linz, Austria
-
Stefan Lendl corresponding
Affiliation as printed
Institute of Discrete Mathematics, TU Graz, Austria
-
Affiliation as printed
Department of Computer Science, RWTH Aachen, Germany
Cited by 11 stored of 9
11 results
No patents citing this paper on Lens.org (checked 2026-10-06).
References 18
-
W6721774119details pending0citations
-
W2963875387details pending0citations
-
W6636543980details pending0citations
-
W4288284074details pending0citations
18 results