| Assignment Problem (2008) | |||||||||||||||
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. In this paper we present an algorithm 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 (linear time, if S and T are presorted). This improves the previously best-known O(n 2)-time algorithm for this problem. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||