Sorting and Selection in Posets

Details Sorting and Selection in Posets Sorting and Selection in Posets

2007-07-10

arxiv.org/abs/0707.1532v1

Computer Science

Data Structures and Algorithms

24 pages

Scientific paper

Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study a more general setting, in which some pairs of objects are incomparable. This generalization is relevant in applications related to rankings in sports, college admissions, or conference submissions. It also has potential applications in biology, such as comparing the evolutionary fitness of different strains of bacteria, or understanding input-output relations among a set of metabolic reactions or the causal influences among a set of interacting genes or proteins. Our results improve and extend results from two decades ago of Faigle and Tur\'{a}n. A measure of complexity of a partially ordered set (poset) is its width. Our algorithms obtain information about a poset by queries that compare two elements. We present an algorithm that sorts, i.e. completely identifies, a width w poset of size n and has query complexity O(wn + nlog(n)), which is within a constant factor of the information-theoretic lower bound. We also show that a variant of Mergesort has query complexity O(wn(log(n/w))) and total complexity O((w^2)nlog(n/w)). Faigle and Tur\'{a}n have shown that the sorting problem has query complexity O(wn(log(n/w))) but did not address its total complexity. For the related problem of determining the minimal elements of a poset, we give efficient deterministic and randomized algorithms with O(wn) query and total complexity, along with matching lower bounds for the query complexity up to a factor of 2. We generalize these results to the k-selection problem of determining the elements of height at most k. We also derive upper bounds on the total complexity of some other problems of a similar flavor.

Affiliated with

Also associated with

No associations

Rating

Sorting and Selection in Posets 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 and Selection in Posets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sorting and Selection in Posets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-434499