Derandomized Vector Sorting

Simple item page
dc.contributor.authorHeath, Lenwood S.en
dc.contributor.authorMateescu, Gabrielen
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:36:46Zen
dc.date.available2013-06-19T14:36:46Zen
dc.date.issued1998-08-01en
dc.description.abstractAn 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.en
dc.format.mimetypeapplication/postscripten
dc.identifierhttp://eprints.cs.vt.edu/archive/00000498/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000498/01/TR-98-19.psen
dc.identifier.trnumberTR-98-19en
dc.identifier.urihttp://hdl.handle.net/10919/20033en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.relation.ispartofHistorical Collection(Till Dec 2001)en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleDerandomized Vector Sortingen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Name:
TR-98-19.ps
Size:
160.7 KB
Format:
Postscript Files
Download

Collections

Computer Science Technical Reports