Flexible bandwidth assignment with application to optical networks

We introduce two scheduling problems, the flexible bandwidth allocation problem ( $$\textsc {FBAP}$$ FBAP ) and the flexible storage allocation problem ( $$\textsc {FSAP}$$ FSAP ). In both problems, we have an available resource, and a set of requests, each consists of a minimum and a maximum resource requirement, for the duration of its execution, as well as a profit accrued per allocated unit of the resource. In $$\textsc {FBAP}$$ FBAP , the goal is to assign the available resource to a feasible subset of requests, such that the total profit is maximized, while in $$\textsc {FSAP}$$ FSAP we also require that each satisfied request is given a contiguous portion of the resource. Our problems generalize the classic bandwidth allocation problem (BAP) and storage allocation problem (SAP) and are therefore $$\text {NP-hard}$$ NP-hard . Our main results are a 3-approximation algorithm for $$\textsc {FBAP}$$ FBAP and a $$(3+\epsilon )$$ ( 3 + ϵ ) -approximation algorithm for $$\textsc {FSAP}$$ FSAP , for any fixed $$\epsilon >0 $$ ϵ > 0 . These algorithms make nonstandard use of the local ratio technique. Furthermore, we present a $$(2+\epsilon )$$ ( 2 + ϵ ) -approximation algorithm for $$\textsc {SAP}$$ SAP , for any fixed $$\epsilon >0 $$ ϵ > 0 , thus improving the best known ratio of $$\frac{2e-1}{e-1} + \epsilon $$ 2 e - 1 e - 1 + ϵ . Our study is motivated also by critical resource allocation problems arising in all-optical networks.