Sorting under Partial Information (without the Ellipsoid Algorithm)

Details Sorting under Partial Information (without the Ellipsoid Algorithm) Sorting under Partial Information (without the Ellipsoid Algorithm)

2009-10-31

arxiv.org/abs/0911.0086v2

Computer Science

Data Structures and Algorithms

v2: Major revision; the algorithm for merging under partial information has been simplified. A preliminary version appeared in

Scientific paper

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (J. Comput. System Sci. 51 (3), 390-399, 1995) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once, in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present: - an O(n^2) algorithm performing O(log n log e(P)) comparisons; - an O(n^2.5) algorithm performing at most (1+ epsilon) log e(P) + O_epsilon (n) comparisons; - an O(n^2.5) algorithm performing O(log e(P)) comparisons. All our algorithms can be implemented in such a way that their computational bottleneck is confined in a preprocessing phase, while the sorting phase is completed in O(q) + O(n) time, where q denotes the number of comparisons performed.

Affiliated with

Also associated with

No associations

Rating

Sorting under Partial Information (without the Ellipsoid Algorithm) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sorting under Partial Information (without the Ellipsoid Algorithm), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sorting under Partial Information (without the Ellipsoid Algorithm) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-150107