Derandomized Vector Sorting
| dc.contributor.author | Heath, Lenwood S. | en |
| dc.contributor.author | Mateescu, Gabriel | en |
| dc.contributor.department | Computer Science | en |
| dc.date.accessioned | 2013-06-19T14:36:46Z | en |
| dc.date.available | 2013-06-19T14:36:46Z | en |
| dc.date.issued | 1998-08-01 | en |
| dc.description.abstract | An 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.mimetype | application/postscript | en |
| dc.identifier | http://eprints.cs.vt.edu/archive/00000498/ | en |
| dc.identifier.sourceurl | http://eprints.cs.vt.edu/archive/00000498/01/TR-98-19.ps | en |
| dc.identifier.trnumber | TR-98-19 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/20033 | en |
| dc.language.iso | en | en |
| dc.publisher | Department of Computer Science, Virginia Polytechnic Institute & State University | en |
| dc.relation.ispartof | Historical Collection(Till Dec 2001) | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.title | Derandomized Vector Sorting | en |
| dc.type | Technical report | en |
| dc.type.dcmitype | Text | en |
Files
Original bundle
1 - 1 of 1