A linear time algorithm for the robust recoverable selection problem

DOI10.1016/j.dam.2020.08.012zbMath1477.90052OpenAlexW3083622237MaRDI QIDQ1983118

Stefan Lendl, Thomas Lachmann, Gerhard J. Woeginger

Publication date: 15 September 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.08.012

zbMATH Keywords

computational complexityselection problemrobust optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Robustness in mathematical programming (90C17)

Related Items (2)

Min‐sum controllable risk problems with concave risk functions of the same value range ⋮ Combinatorial optimization problems with balanced regret

Cites Work

• Time bounds for selection
• On recoverable and two-stage robust selection problems with budgeted uncertainty
• The recoverable robust spanning tree problem with interval costs is polynomially solvable
• Recoverable robust spanning tree problem under interval uncertainty representations
• Robust recoverable and two-stage selection problems
• Recoverable robust shortest path problems
• The Concept of Recoverable Robustness, Linear Programming Recovery, and Railway Applications
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems

This page was built for publication: A linear time algorithm for the robust recoverable selection problem