The Complexity Landscape of Two-Stage Robust Selection Problems with Budgeted Uncertainty
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910025776103424 |
|---|---|
| author | Goerigk, Marc Henke, Dorothee Wulf, Lasse |
| author_facet | Goerigk, Marc Henke, Dorothee Wulf, Lasse |
| contents | A standard type of uncertainty set in robust optimization is budgeted uncertainty, where an interval of possible values for each parameter is given and the total deviation from their lower bounds is bounded. In the two-stage setting, discrete and continuous budgeted uncertainty have to be distinguished. The complexity of such problems is largely unexplored, in particular if the underlying nominal optimization problem is simple, such as for selection problems. In this paper, we give a comprehensive answer to long-standing open complexity questions for three types of selection problems and three types of budgeted uncertainty sets. In particular, we demonstrate that the two-stage selection problem with continuous budgeted uncertainty is NP-hard, while the corresponding two-stage representative selection problem is solvable in polynomial time. Our hardness result implies that also the two-stage assignment problem with continuous budgeted uncertainty is NP-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_16465 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Complexity Landscape of Two-Stage Robust Selection Problems with Budgeted Uncertainty Goerigk, Marc Henke, Dorothee Wulf, Lasse Optimization and Control Data Structures and Algorithms 90C17, 90C27, 68Q25 A standard type of uncertainty set in robust optimization is budgeted uncertainty, where an interval of possible values for each parameter is given and the total deviation from their lower bounds is bounded. In the two-stage setting, discrete and continuous budgeted uncertainty have to be distinguished. The complexity of such problems is largely unexplored, in particular if the underlying nominal optimization problem is simple, such as for selection problems. In this paper, we give a comprehensive answer to long-standing open complexity questions for three types of selection problems and three types of budgeted uncertainty sets. In particular, we demonstrate that the two-stage selection problem with continuous budgeted uncertainty is NP-hard, while the corresponding two-stage representative selection problem is solvable in polynomial time. Our hardness result implies that also the two-stage assignment problem with continuous budgeted uncertainty is NP-hard. |
| title | The Complexity Landscape of Two-Stage Robust Selection Problems with Budgeted Uncertainty |
| topic | Optimization and Control Data Structures and Algorithms 90C17, 90C27, 68Q25 |
| url | https://arxiv.org/abs/2602.16465 |