TY - JOUR

T1 - Optimizing airspace closure with respect to politicians’ egos

AU - Kostitsyna, I.

AU - Löffler, M.

AU - Polishchuk, V.

PY - 2015

Y1 - 2015

N2 - 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 president's 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.
Keywords: Scheduling; Data structure; Algorithms

AB - 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 president's 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.
Keywords: Scheduling; Data structure; Algorithms

U2 - 10.1016/j.tcs.2015.04.014

DO - 10.1016/j.tcs.2015.04.014

M3 - Article

VL - 586

SP - 161

EP - 175

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -