Recoverable Robust Knapsacks: the Discrete Scenario Case
Büsing, Christina; Koster, Arie M. C. A.; Kutschka, Manuel
Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Admission control problems have been studied extensively in the past. In a typical setting, resources like bandwidth have to be distributed to the different customers according to their demands maximizing the profit of the company. Yet, in real-world applications those demands are deviating and in order to satisfy their service requirements often a robust approach is chosen wasting benefits for the company. Our model overcomes this problem by allowing a limited recovery of a previously fixed assignment as soon as the data are known by violating at most k service promises and serving up to l new customers. Applying this approaches to the call admission problem on a single link of a telecommunication network leads to a recoverable robust version of the knapsack problem.
