A Semidefinite Relaxation for Air Traffic Flow Scheduling
<|reference_start|>A Semidefinite Relaxation for Air Traffic Flow Scheduling: We first formulate the problem of optimally scheduling air traffic low with sector capacity constraints as a mixed integer linear program. We then use semidefinite relaxation techniques to form a convex relaxation of that problem. Finally, we present a randomization algorithm to further improve the quality of the solution. Because of the specific structure of the air traffic flow problem, the relaxation has a single semidefinite constraint of size dn where d is the maximum delay and n the number of flights.<|reference_end|>
@article{d'aspremont2006a,
    title={A Semidefinite Relaxation for Air Traffic Flow Scheduling},
    author={Alexandre d'Aspremont, Laurent El Ghaoui},
    journal={arXiv preprint arXiv:cs/0609145},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0609145},
    primaryClass={cs.CE}
}