The syntenic distance between two species is the minimum number of
fusions, fissions, and translocations required to transform one genome
into the other. The linear syntenic distance, a restricted form of
this model, has been shown to be close to the syntenic distance. Both
models are computationally difficult to compute and have resisted
efficient approximation algorithms with non-trivial performance
guarantees. In this paper, we prove that many useful properties of
syntenic distance carry over to linear syntenic distance. We also
give a reduction from the general linear synteny problem to the
question of whether a given instance can be solved using the maximum
possible number of translocations. Our main contribution is an
algorithm exactly computing linear syntenic distance in nested
instances of the problem. This is the first polynomial time algorithm
exactly solving linear synteny for a non-trivial class of instances.
It is based on a novel connection between the syntenic distance and a
scheduling problem that has been studied in the operations research
literature.