title: An O(n log n)-time algorithm for the restriction scaffold assignment problem.
abstract: The restriction scaffold assignment problem takes as input two finite point sets S and T (with S containing more points than 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. An algorithm is presented that finds a minimum-cost solution for this problem in O(n log n) time, provided that the points in S and T are restricted to lie on a line and the cost function delta is the L(1) metric. This algorithm runs in linear time, if S and T are presorted. This improves the previously best-known O(n (2))-time algorithm for this problem.
authors.affiliation: School of Computer Science, McGill University, Montréal, Québec Canada.
authors.forename: Justin
authors.initials: J
authors.lastname: Colannino
authors.forename: Mirela
authors.initials: M
authors.lastname: Damian
authors.forename: Ferran
authors.initials: F
authors.lastname: Hurtado
authors.forename: John
authors.initials: J
authors.lastname: Iacono
authors.forename: Henk
authors.initials: H
authors.lastname: Meijer
authors.forename: Suneeta
authors.initials: S
authors.lastname: Ramaswami
authors.forename: Godfried
authors.initials: G
authors.lastname: Toussaint
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D003627:Data Interpretation, Statistical; D016014:Linear Models