January 01, 2024 conference-paper Aachen paper

The Complexity Classes of Hamming Distance Recoverable Robust Problems

Lecture notes in computer science, pp. 321–335

DOI: 10.1007/978-3-031-55598-5_21 OpenAlex

Authors 1

Christoph Grüne corresponding Aachen Department of Computer Science

RWTH Aachen University

Affiliation as printed

Department of Computer Science, RWTH Aachen University, Aachen, Germany

Cited by 1 stored of 1

Completeness in the Polynomial Hierarchy for Many Natural Problems in Bilevel and Robust Optimization
2025 Lecture notes in computer science conference-paper Computer Science Complexity and Algorithms in Graphs

4

citations

1 result

No patents citing this paper on Lens.org (checked 2026-10-06).

References 16

The polynomial-time hierarchy
1976 Theoretical Computer Science article Computer Science Computability, Logic, AI Algorithms Open access

1,302

citations
The Concept of Recoverable Robustness, Linear Programming Recovery, and Railway Applications
2009 Lecture notes in computer science conference-paper Engineering Railway Systems and Energy Efficiency

273

citations
A survey on robustness in railway planning
2017 European Journal of Operational Research article Engineering Railway Systems and Energy Efficiency Open access

150

citations
The Recoverable Robust Tail Assignment Problem
2013 Transportation Science article Engineering Air Traffic Management and Optimization

61

citations
Recoverable robust shortest path problems
2011 Networks article Computer Science Complexity and Algorithms in Graphs

54

citations
Recoverable robust knapsacks: the discrete scenario case
2011 Optimization Letters article Engineering Optimization and Packing Problems

52

citations
The recoverable robust stand allocation problem: a GRU airport case study
2018 OR Spectrum article Engineering Air Traffic Management and Optimization Open access

41

citations
Reducing the complexity of reductions
2001 Computational Complexity article Computer Science Complexity and Algorithms in Graphs

38

citations
Recoverable robust single day aircraft maintenance routing problem
2014 Computers & Operations Research article Engineering Air Traffic Management and Optimization

36

citations
On the recoverable robust traveling salesman problem
2015 Optimization Letters article Engineering Vehicle Routing Optimization Methods Open access

35

citations
Multi-stage recovery robustness for optimization problems: A new concept for planning under disturbances
2011 Information Sciences article Decision Sciences Risk and Portfolio Optimization Open access

26

citations
Investigating the recoverable robust single machine scheduling problem under interval uncertainty
2022 Discrete Applied Mathematics article Engineering Scheduling and Optimization Algorithms Open access

25

citations
Recoverable Robust Knapsacks: Γ-Scenarios
2011 Lecture notes in computer science conference-paper Engineering Optimization and Packing Problems

20

citations
Recoverable robust spanning tree problem under interval uncertainty representations
2016 Journal of Combinatorial Optimization article Computer Science Complexity and Algorithms in Graphs Open access

19

citations
Robust recoverable perfect matchings
2015 Networks article Computer Science Advanced Graph Theory Research

13

citations
Formulations and algorithms for the recoverable Γ -robust knapsack problem
2018 EURO Journal on Computational Optimization article Engineering Optimization and Packing Problems Open access

6

citations

16 results