Top

Published in:

2014 | OriginalPaper | Chapter

Recoverable Robust Combinatorial Optimization Problems

Authors : Adam Kasperski, Adam Kurpisz, Paweł Zieliński

Published in: Operations Research Proceedings 2012

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper deals with two Recoverable Robust (RR) models for combinatorial optimization problems with uncertain costs. These models were originally proposed by Büsing (2012) for the shortest path problem with uncertain costs. In this paper, we generalize the RR models to a class of combinatorial optimization problems with uncertain costs and provide new positive and negative complexity results in this area.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Approximating Combinatorial Optimization Problems with Uncertain Costs and the OWA Criterion

next chapter A MILP-Based Approach for Hydrothermal Scheduling

Aissi, H., Bazgan, C., Vanderpooten, D.: Complexity of the min-max (regret) versions of cut problems. In: ISAAC 2005, Lecture Notes in Computer Science, vol. 3827, pp. 789–798. Springer-Verlag (2005).

Aissi, H., Bazgan, C., Vanderpooten, D.: Complexity of the min-max and min-max regret assignment problems. Operation Research Letters 33, 634–640 (2005)CrossRef

Averbakh, I.: On the complexity of a class of combinatorial optimization problems with uncertainty. Mathematical Programming 90, 263–272 (2001)CrossRef

Büsing, C.: Recoverable robust shortest path problems. Networks 59, 181–189 (2012)CrossRef

Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H, Freeman and Company (1979)

Kasperski, A., Zieliński, P.: On the approximability of minmax (regret) network optimization problems. Information Processing Letters 109, 262–266 (2009)CrossRef

Kasperski, A., Zieliński, P.: On the approximability of robust spanning tree problems. Theoretical Computer Science 412, 365–374 (2011)CrossRef

Kasperski, A., Kurpisz, A., Zieliński, P.: Approximating the minmax (regret) selecting items problem. Information Processing Letters 113, 23–29 (2013)CrossRef

Kouvelis, P., Yu, G.: Robust Discrete Optimization and its applications. Kluwer Academic Publishers (1997).

Title: Recoverable Robust Combinatorial Optimization Problems
Authors: Adam Kasperski
Adam Kurpisz
Paweł Zieliński
Publisher: Springer International Publishing
Book: Operations Research Proceedings 2012
Print ISBN: 978-3-319-00794-6

Electronic ISBN: 978-3-319-00795-3

Copyright Year: 2014
DOI: https://doi.org/10.1007/978-3-319-00795-3_22