Loading…

A linear time algorithm for the robust recoverable selection problem

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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2021-11, Vol.303, p.94-107
Main Authors: Lachmann, Thomas, Lendl, Stefan, Woeginger, Gerhard J.
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2020.08.012