Heath, Lenwood S.Mateescu, Gabriel2013-06-192013-06-191998-08-01http://hdl.handle.net/10919/20033An instance of the vector sorting problem is a sequence of k-dimensional vectors of length n. A solution to the problem is a permutation of the vectors such that in each dimension the length of the longest decreasing subsequence is O(sqrt(n)). A random permutation solves the problem. Here we derandomize the obvious probabilistic algorithm and obtain a deterministic O(kn^3.5) time algorithm that solves the vector sorting problem. We also apply the algorithm to a book embedding problem.application/postscriptenIn CopyrightTechnical reportTR-98-19http://eprints.cs.vt.edu/archive/00000498/01/TR-98-19.ps