ABSOLUTE ROBUSTNESS FOR OPTIMAL SELECTION PROBLEMS WITH FIXED PAST
https://doi.org/10.29235/1561-8323-2018-62-2-147-150
Abstract
A novel approach to solving optimal selection problems under dynamic uncertainty is described. The approach is called absolute robustness with fixed past. An efficient algorithm is presented for the main problem and several its variants. The approach can be employed for solving other combinatorial optimization problems under dynamic uncertainty.
About the Author
M. Ya. Kovalyov
United Institute of Informatics Problems of the National Academy of Sciences of Belarus
Belarus
Corresponding Member, D. Sc. (Physics and Mathematics), Professor, Deputy General Director for Research
Belarus
Corresponding Member, D. Sc. (Physics and Mathematics), Professor, Deputy General Director for Research
References
1. Cicerone S., D’Angelo G., Stefano G. D., Frigioni D., Navarra A. Robust algorithms and price of robustness in shunting problems. Proceedings of the 7th workshop on algorithmic approaches for transportation modeling, optimization, and systems (ATMOS07). Berlin, 2007, pp. 175–190.
2. Erera A. L., Morales J. C., Savelsbergh M. Robust optimization for empty repositioning problems. Operations Research, 2009, vol. 57, no. 2, pp. 468–483. DOI: 10.1287/opre.1080.0650
3. Liebchen С., Lubbecke M. E., Mohring R. H., Stiller S. The concept of recoverable robustness, linear programming recovery, and railway applications. Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems. Berlin, Springer, 2009, pp. 1–27. DOI: 10.1007/978-3-642-05465-5_1
4. Kasperski A., Zielinski P. Robust recoverable and two-stage selection problems. Discrete Applied Mathematics, 2017, vol. 233, pp. 52–64. DOI: 10.1016/j.dam.2017.08.014
5. Bertsimas D., Sim M. Robust discrete optimization and network flows. Mathematical Programming Series B, 2003, vol. 98, no. 1–3, pp. 49–71. DOI: 10.1007/s10107-003-0396-4
6. Blum M., Floyd R. W., Pratt V., Rivest R. L., Tarjan R. E. Time bounds for selection. Journal of Computer and Systems Sciences, 1973, vol. 7, no. 4, pp. 448–461. DOI: 10.1016/s0022-0000(73)80033-9
Review
Views: 819
Email this article 