Flexible bandwidth assignment with application to optical networks

Hadas Shachnai (), Ariella Voloshin () and Shmuel Zaks ()
Additional contact information
Hadas Shachnai: Technion IIT
Ariella Voloshin: Technion IIT
Shmuel Zaks: Technion IIT

Journal of Scheduling, 2018, vol. 21, issue 3, No 5, 327-336

Abstract: Abstract 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.

Keywords: Approximation algorithms; Local ratio; Resource allocation; All-optical networks (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-017-0514-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:21:y:2018:i:3:d:10.1007_s10951-017-0514-4

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-017-0514-4

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().