An O(n log n)-Time Algorithm for the Restricted Scaffold Assignment
<|reference_start|>An O(n log n)-Time Algorithm for the Restricted Scaffold Assignment: The assignment problem takes as input two finite point sets S and T and establishes a correspondence between points in S and points in T, such that each point in S maps to exactly one point in T, and each point in T maps to at least one point in S. In this paper we show that this problem has an O(n log n)-time solution, provided that the points in S and T are restricted to lie on a line (linear time, if S and T are presorted).<|reference_end|>
@article{colannino2005an,
    title={An O(n log n)-Time Algorithm for the Restricted Scaffold Assignment},
    author={Justin Colannino, Mirela Damian, Ferran Hurtado, John Iacono, Henk
  Meijer, Suneeta Ramaswami and Godfried Toussaint},
    journal={arXiv preprint arXiv:cs/0507013},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0507013},
    primaryClass={cs.CG cs.DM}
}