Optimal Sorting with Persistent Comparison Errors
Published in arXiv (Cornell University) • Apr 20, 2018
NobleIDNI1P52W01R89S76
Authors:,,
Barbara Geissmann
Stefano Leucci
Chih-Hung Liu
Abstract
We consider the problem of sorting $n$ elements in the case of \emph{persistent} comparison errors. In this model (Braverman and Mossel, SODA'08), each comparison between two elements can be wrong with some fixed (small) probability $p$, and \emph{comparisons cannot be repeated}. Sorting perfectly i...
Finding related papers...
Discussions
(0)No comments yet
Be the first to share your thoughts!