Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty
| Autor: | Paweł Zieliński, Adam Kasperski, Marc Goerigk |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Polynomial
Mathematical optimization Control and Optimization Computer science Applied Mathematics Regular polygon Approximation algorithm Ellipsoid Computer Science Applications Set (abstract data type) Computational Theory and Mathematics Shortest path problem Theory of computation Discrete Mathematics and Combinatorics Selection (genetic algorithm) |
| Zdroj: | Journal of Combinatorial Optimization. 43:497-527 |
| ISSN: | 1573-2886 1382-6905 |
| DOI: | 10.1007/s10878-021-00776-4 |
| Popis: | In this paper a class of robust two-stage combinatorial optimization problems is discussed. It is assumed that the uncertain second-stage costs are specified in the form of a convex uncertainty set, in particular polyhedral or ellipsoidal ones. It is shown that the robust two-stage versions of basic network optimization and selection problems are NP-hard, even in a very restrictive cases. Some exact and approximation algorithms for the general problem are constructed. Polynomial and approximation algorithms for the robust two-stage versions of basic problems, such as the selection and shortest path problems, are also provided. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink