tag:blogger.com,1999:blog-3722233.post907395260882083622..comments2024-03-03T22:21:38.304-06:00Comments on Computational Complexity: Sorting a Partial OrderLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-9218138765507413642011-09-14T09:52:08.881-05:002011-09-14T09:52:08.881-05:00I've found this post after reading the "P...I've found this post after reading the "Poset Sorting Paper". So I hope somebody is reading this comment after almost 3 years :)<br /><br />pciaccia's statement: "computing a minimal chain decomposition of a poset takes more than quadratic time" is based on a sentence found in the paper he links.<br /><br />Anyway, we have to carefully notice that what Daskalakis et al. do is to "keep" a chain decomposition of q <= w chains. In other words, for each element considered in loop at 4. maintaining the decomposition C is O(w log n) as it requires, at most, w binary search to find the right chain.<br /><br />Am I wrong?Fabrizio Silvestrihttp://pomino.isti.cnr.it/~silvestrnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5188151320800232192009-04-22T08:49:00.000-05:002009-04-22T08:49:00.000-05:00Hi, I've 1 comment and 1 question
Comment to ...Hi, I've 1 comment and 1 question<br /><br />Comment to Anonymous' question: computing a minimal chain decomposition of a poset takes more than quadratic time, as asserted here:<br /><br />http://www.inf.unibz.it/~franconi/papers/appl-int-94.ps.gz <br /><br />The same paper provides a heuristic algorithm.<br /><br />Question: it is tightly related to (but different from) the problem of sorting a poset: <br /><br />If you have a poset (P,<) and an element x not in P, which is the complexity of determining the <I>cover</I> of x, i.e., the set of minimal elements in P that dominate x (a.k.a. parents of x)? <br /><br />If P is decomposed into w chains (ChianMerge data structure in SODA09 paper), then O(w*logn + w^2) clearly suffices:<br />- O(w*logn) to perform binary search on the w chains to find the parent of x (if any) in each chain; this yields a superset of the cover of x.<br />- O(w^2) to test that such parents are indeed incomparable (if p1 and p2 are both returned from step 1 and p1 < p2 then p2 is not a parent of x)<br /><br />But the above is quadratic in w :-(<br />Any reference?Paolo Ciacciahttps://www.blogger.com/profile/10789404431022997891noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55030678634008735192009-01-12T09:42:00.000-06:002009-01-12T09:42:00.000-06:00So a quick newbie question. I understand that you ...So a quick newbie question. I understand that you can obtain a minimum(?) chain decomposition of a partial order in linear time. Can you please point out some references to such algorithms? Thank you very much.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63534041811757021382009-01-08T11:32:00.000-06:002009-01-08T11:32:00.000-06:00&lt stands for the less-than sign. Opps.&lt stands for the less-than sign. Opps.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55090031753792969852009-01-08T11:30:00.000-06:002009-01-08T11:30:00.000-06:00Interestingly, in the Daskalakis et al paper, in t...Interestingly, in the Daskalakis et al paper, in the optimal algorithm that takes O(n(w+logn)) comparisons, it takes a long (but still polynomial) _running time_ (with potentially large exponent) to decide which comparisons to make. It's still open to get an optimal algorithm that also takes O(n(w+logn)) _time_. I don't even have any idea how to do it if you assume correctness of the 1/3--2/3 conjecture.<BR/><BR/>I wonder if an algorithm that works like quicksort works. I.e. choose a random element, compare all elements to it, get all the information you can and put it in a "knowledge base" (i.e. a directed graph), and keep doing this. Each time, if you picked x and the knowledge that x &lt y or x &gt y or that they're incomparable is already in your database, then you don't compare x to y. Furthermore, it might be helpful to perform these comparisons in a random order, and some of them may be spared because you might get information in the process.<BR/><BR/>Note that the rules of updating the data base should include the following two rules (and maybe only them and their symmetric counterparts). First of all, if you already knew that x &lt y and you now find out that y &lt z, then you add the knowledge that x &lt z. Second of all, if you already know that z &lt x &lt y and that both z and y are incomparable to w, then you conclude that x is incomparable to w. I wonder how well this does...Anonymousnoreply@blogger.com