Optimizing airspace closure with respect to politicians egos
2015 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 586, 161-175 p.Article in journal (Refereed) Published
When a president is landing at a busy airport, the airspace around the airport closes for commercial traffic. We show how to schedule the presidential squadron so as to minimize its impact on scheduled civilian flights; to obtain an efficient solution we use a "rainbow" algorithm recoloring aircraft on the fly as they are stored in a special type of forest. We also give a data structure to answer the following query efficiently: Given the presidents ego (the requested duration of airspace closure), when would be the optimal time to close the airspace? Finally, we study the dual problem: Given the time when the airspace closure must start, what is the longest ego that can be tolerated without sacrificing the general traffic? We solve the problem by drawing a Christmas tree in a delay diagram; the tree allows one to solve also the query version of the problem. (C) 2015 Elsevier B.V. All rights reserved.
Place, publisher, year, edition, pages
Elsevier , 2015. Vol. 586, 161-175 p.
Scheduling; Data structure; Algorithms
IdentifiersURN: urn:nbn:se:liu:diva-120226DOI: 10.1016/j.tcs.2015.04.014ISI: 000356751800012OAI: oai:DiVA.org:liu-120226DiVA: diva2:842646
Funding Agencies|Netherlands Organisation for Scientific Research (NWO) [612.001.106, 639.021.123]; Swedens innovation agency VINNOVA [2014-03476]2015-07-212015-07-202015-07-21