Optimizing bandwidth allocation in elastic optical networks with application to scheduling

We study a problem of optimal bandwidth allocation in the elastic optical networks technology, where usable frequency intervals are of variable width. In this setting, each lightpath has a lower and upper bound on the width of its frequency interval, as well as an associated profit, and we seek a bandwidth assignment that maximizes the total profit. This problem is known to be NP-complete. We strengthen this result by showing that, in fact, the problem is inapproximable within any constant ratio even on a path network. We further derive NP-hardness results and present approximation algorithms for several special cases of the path and ring networks, which are of practical interest. Finally, while in general our problem is hard to approximate, we show that an optimal solution can be obtained by allowing resource augmentation. Some of our results resolve open problems posed by Shalom et al. (2013) 28]. Our study has applications also in real-time scheduling.