Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Sorting a Partial Order

Expand Messages
  • GASARCH
    I liked the SODA2009 paper Sorting and Selection in Posets since it makes you look at ordinary sorting in a new way. What does it mean to sort a list? We
    Message 1 of 1 , Jan 8, 2009
    • 0 Attachment
      I liked the SODA2009 paper Sorting and Selection in Posets since it makes you look at ordinary sorting in a new way.

      What does it mean to sort a list? We usually think (correctly) that we take a list of ordered objects and put them into an ordered list. How to extend this to partial orders? We need to re-look at total orders.

      Say that making a comparison between elements of the ordered set is HARD Then you want to make as few as possible. But you want to, when you are done, have a data structure that makes comparisons easy. Hence we view sorting as follows:
      Given a set A of n elements from a totally ordered set come up with a data structure of size O(n) such that the operation Given x,y &isin A which one is bigger? can be done in O(1) time. While setting up the data structure you would like to to do this with as few comparisons as possible. We will assume that comparing two elements of {1,...,n} is easy.
      Given a sorted array you can easily obtain such a data structure: pair each element with its index in the array. To compare x,y quickly just compare index(x) and index(y). Note that we think of comparing numbers in {1,...n} as easy but comparing elements of the ordered set as being hard.

      The papers Sorting and Recognition problems for Ordered Sets (SICOMP 1988, Faigle and Turan) and Sorting and Selection in Posets (SODA 2009, Daskalakis, Karp, Mossel, Riesenfeld, Verbin) study this issue.
      Definition: Let P=(X,<) be a partial order.
      1. A chain decomposition of P is a partition of X into sets each one of which is totally ordered under < .
      2. A chain merge data structure for P is a chain decomposition together with the following. For each x &isin X, the following information: (1) which i has x &isin C_i, and (2) for all j, what is the largest element in C_j that is < x. It is easy to see that from such a data structure you can do comparisons in O(1).
      3. The width of P is the min number of elements in a chain decomp.
      RESULTS:
      1. Faigle and Turan showed that if P has width w then it can be sorted in O(wnlog n) comparisons. (Can also see Daskalakis et al paper for this.)
      2. Daskalakis et al showed that if P has width w then it can be sorted in O(n(w+log n)). They use the Chain Merge Data Structure. This bound matches the info-theoretic min.


      --
      Posted By GASARCH to Computational Complexity at 1/08/2009 10:11:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.