reckless intuitions of an epistemic hygienist ([info]gustavolacerda) wrote,
@ 2008-05-05 16:14:00
Previous Entry  Add to memories!  Tell a Friend  Next Entry
algorithmic problem
Given a set L of permutations of a list, compute the maximal partial order (DAG) under which all lists in L are topological sorts. How would you do this? Can you do better than O(m n^2 k^2)? (m = number of lists in L, k = # of things in domain = the size of the elements of L)
Sounds like an ILP problem.

One idea: whenever a cycle is detected, all the elements are deemed incomparable.

(17 comments) - (Post a new comment)


[info]bhudson
2008-05-06 12:01 am UTC (link)
Store the complete graph, then mark edges as inconsistent. Then DAGify it (um... not clear on that one, but that seems easy enough?). Marking edges is n work per item, and there are mn items. *Plus* k^2, instead of *times* k^2 like in your thing. Still not exactly palatable.

(Reply to this) (Thread)

[info]gustavolacerda
2008-05-06 12:07 am UTC (link)
<< Marking edges is n work per item, >>

What is an "item"?

(Reply to this) (Parent)

[info]gustavolacerda
2008-05-06 12:25 am UTC (link)
<< Marking edges is n work per item, and there are mn items.>>
and there are k(k-1) edges to loop through.

(Reply to this) (Parent)(Thread)

[info]bhudson
2008-05-06 02:39 am UTC (link)
An item is a thing, of which you have k in the universe, but only n in any given list.

You don't need to loop through the entire set of edges just to mark one, hence you have an additive rather than multiplicative dependence on k2. O(mn2) to mark the edges, then another O(k2) to write out the edges that weren't marked.

Of course, what comes out isn't a DAG. We leave the final step as an exercise to the reader.

(Reply to this) (Parent)(Thread)

[info]gustavolacerda
2008-05-06 03:44 am UTC (link)
<< You don't need to loop through the entire set of edges just to mark one >>

Sure. But you want to mark *all* edges, right?



<< Marking edges is n work per item, >>

are you marking *all edges* in O(nk)?

(Reply to this) (Parent)(Thread)

[info]bhudson
2008-05-06 03:53 pm UTC (link)
There is confusion here. Maybe you should try to parrot my algorithm and we can figure out if we at least agree on that.

(Reply to this) (Parent)

[info]gustavolacerda
2008-05-06 12:17 am UTC (link)
One vague idea:

* take the UNION of all the complete DAGs corresponding to each list
* find all cycles there. A, B in the same cycle => A, B in the same "set" (permutations between things in the same set are graph automorphisms of the final DAG)

Edited at 2008-05-06 12:18 am UTC

(Reply to this) (Thread)

[info]gustavolacerda
2008-05-06 06:08 pm UTC (link)
<< permutations between things in the same set are graph automorphisms of the final DAG >>

Therefore, all nodes in the same set have the same incoming and outgoing edges. This means we can collapse sets of nodes into "supernodes".
For the final DAG, you just make sure that there are no edges between members of the same set (and propagate each supernode's incoming and outgoing edges into all members... or you could just leave the final DAG in the supernode representation.

(Reply to this) (Parent)
another idea
[info]gustavolacerda
2008-05-06 12:21 am UTC (link)
sequence alignment

(Reply to this) (Thread)
Re: another idea
[info]gustavolacerda
2008-05-06 06:08 pm UTC (link)
just like in diff.

(Reply to this) (Parent)

[info]rdore
2008-05-06 08:50 am UTC (link)
Your description is awful. I spent 10 minutes reading it and the comments over and over and I'm still not sure what the question is.

1. Use variables of some sort to denote things you're talk about
2. Don't call something a list unless its ordering is important

As far as I can tell you have:

A collection of k objects, let's call it X
A collection of linear orderings of subsets of X, which you call L

The size of L is m. Each linear ordering is on a subset of size n.

What you want to output is the maximum partial order of X which is a weaken of each element of L (on that element's domain).

If this is the right question, the answer is often not unique. For example, X={a,b,c} and L={[a,b],[a,c]}, then a maximal partial order will relate b and c in some way, but either way will do.


Edited at 2008-05-06 10:30 am UTC

(Reply to this) (Thread)

[info]gustavolacerda
2008-05-06 02:24 pm UTC (link)
<< then a maximal partial order will relate b and c in some way, but either way will do. >>

This will not happen if all lists in L are permutations of each other (as stated). I guess I should have noticed that k=n.

(Reply to this) (Parent)(Thread)

[info]rdore
2008-05-06 07:35 pm UTC (link)
Oh ok. Well suppressing log factors, I think the complexity is O(mk+k2). Make a graph on the k objects by throwing in all the consecutive pairs from all the lists. This is O(mk). Then detect all the strongly connected components - O(k2). Remove the edges of the strongly connected components - O(k2). Then take the transitive closure - I think this is O(k2) at least for a DAG, not sure.

(Reply to this) (Parent)

[info]gustavolacerda
2008-05-06 02:32 pm UTC (link)
I think this post is a great example of how difficult mathematical communication is. The people exposing want to take shortcuts, while the people listening want to be completely clear on what everything means (but they don't share the language used in the shortcuts). It's very hard to put oneself in the other person's shoes.

(Reply to this) (Parent)

[info]bhudson
2008-05-06 03:59 pm UTC (link)
It seemed clear enough to me -- definitely well out of the realm of awful. I guess it is my bread and butter to work these things out.

(Reply to this) (Parent)(Thread)

[info]rdore
2008-05-06 07:26 pm UTC (link)
It wasn't the technical terms that confused me, it was the less technical ones. Using "a list" to refer to two completely different things in the space of about eight words was the biggest problem. Also the fact that n and k were used to refer to the same quantity.

(Reply to this) (Parent)(Thread)

[info]bhudson
2008-05-06 07:57 pm UTC (link)
For a good time, man perldsc.

(Reply to this) (Parent)

(17 comments) - (Post a new comment)

Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…