5 votes
Accepted

Algorithm to establish a global ranking given individual rankings

There is an entire area, rank aggregation (in your case, partial rank aggregation) which deals with these issues. You can take a look at Dwork et al., Rank aggregation revisited and Ailon, Aggregation ...
Yuval Filmus's user avatar
4 votes
Accepted

Generalized sorting algorithm on partially ordered set generated by a relation

You can efficiently test whether $\preceq$ extends to a partial order using topological sorting. Form a directed graph with vertex set $X$ and with an edge $x \to y$ whenever we have $x \preceq y$ ...
D.W.'s user avatar
  • 158k
4 votes
Accepted

Is < binary relation a strict partial order on IEEE doubles?

Yes, it is. (Though you need to consider signed zero as well as NaNs.) For extra confirmation: So, the floating-point operator< does not form weak order and therefore does not form a total order. ...
Alexey Romanov's user avatar
4 votes
Accepted

How to efficiently determine whether a relation is total?

A good first step is to construct a certain matrix corresponding to your relation, which I will let you figure out. Constructing this matrix takes time $O(|X|^2 + |S|)$ (or just $O(|S|)$, depending on ...
Yuval Filmus's user avatar
4 votes
Accepted

Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?

Your problem is the same as interval graph coloring. There is a well-known greedy algorithm solving the problem optimally, running in linear time if the intervals are already sorted.
Yuval Filmus's user avatar
3 votes
Accepted

Disproving well-quasi-order by providing an infinite anti-chain

Your algorithm produces an infinite sequence of antichains whose size is unbounded. However, it doesn't produce a single antichain of infinite size. It is perfectly fine to specify an infinite chain ...
Yuval Filmus's user avatar
3 votes
Accepted

Checking if the mimimum is unique

You cannot avoid enumerating all elements. Consider the following two posets, with elements $x,y,z_1,\ldots,z_n$: $x,y < z_i$ for all $i$. $x,y < z_i$ for all $i < n$, and $z_n < x,y$. ...
Yuval Filmus's user avatar
3 votes
Accepted

Lamport Timestamps and Causality

No, there is no inherent logical/temporal inconsistency in the events described in the question, although it can be considered "unfair" that process P2 can receive and broadcast messages ...
John L.'s user avatar
  • 38.8k
2 votes

Efficient cardinality of set overlap relation

Consider the following problem. We are given $n$ sets $S_1,\ldots,S_n \subseteq \{1,\ldots,\log n\}$, and have to decide whether there are two disjoint sets among them. This problem is known as ...
Yuval Filmus's user avatar
2 votes
Accepted

How do we know that $F^{n + 1}(\overrightarrow{\emptyset}) = F(F^n(\overrightarrow{\emptyset}))$?

In this case, the notation $F^n$ denotes iterated composition, that is, repeatedly applying the function $F$, for $n$ iterations: $F^0(x) = x$. $F^1(x) = F(x)$. $F^2(x) = F(F(x))$. $F^3(x) = F(F(F(x))...
Yuval Filmus's user avatar
2 votes
Accepted

Counting number of permutations respecting partial order

Brightwell and Winkler proved that this program is #P-complete in their paper Counting linear extensions. You can, however, estimate the number of linear extensions efficiently.
Yuval Filmus's user avatar
2 votes
Accepted

relation based on a given partial order - does it have a name?

I searched online. Also checked several articles/papers on poset topological sorting and linear extension of poset. No name has been found for that relation. $E(P)$ can be described as the set of ...
John L.'s user avatar
  • 38.8k
2 votes
Accepted

What happens when two different nodes have the same Lamport clock ID

tl;dr As Lamport writes at the top of page 561 of Time, Clocks, and the Ordering of Events in a Distributed System: To break ties, we use any arbitrary total ordering $\prec$ of the processes. To ...
Kai's user avatar
  • 855
1 vote
Accepted

Terminology for number of topological sorts

"Number of linear extensions" is probably the most popular one. Google scholar returned 1000+ matches for "number of linear extensions" while <...
pcpthm's user avatar
  • 2,324
1 vote
Accepted

Is this algorithm for partial ordering of sets complete and sound?

It is pleasing to see such a nice algorithm. Your algorithm is correct for all inputs except possibly for two corner cases. For example, if we have ...
John L.'s user avatar
  • 38.8k
1 vote

Finding connected components without building the graph first

Okay I'm writing another answer for the sake of tidiness. I suppose that the elements of your sets are integers. Otherwise one could just use pointers to the items. ...
plshelp's user avatar
  • 1,619
1 vote

Finding connected components without building the graph first

I have an idea for the algorithm that's slightly better than a simple dfs based on the fact that the relationship is transitive. From transitivity follows that $a \sim b \land b \sim c \Rightarrow a \...
plshelp's user avatar
  • 1,619
1 vote

Why is there so little literature on partial order production?

This is a comment There is a confusion when you say that sorting is creating the correct total order. When sorting, the total order is input as the relation $\geq$. What sorting does is output the ...
NotDijkstra's user avatar
1 vote

Why is there so little literature on partial order production?

This is a very well-known problem, known as topological sorting. Often it is difficult to find material on a subject because we don't know the proper terms to look for. That's why we have sites such ...
Yuval Filmus's user avatar
1 vote
Accepted

Scheduling: Existence of specific total order

I think you mean partial order, as if you only have a preorder then there might not even exist any total order that is compatible with it. Your argument seems to be missing something about how you ...
Tassle's user avatar
  • 2,442
1 vote
Accepted

Efficiently computing minimal elements over partially ordered sets

One approach is to sort the sets by increasing size, then repeatedly perform the following: take the first set in the list, output it, and remove from the list all supersets of it. This will output ...
D.W.'s user avatar
  • 158k
1 vote
Accepted

The sorting problem for partially ordered sets

Take a worst case scenario. The set is built out of pairs of objects $a_i, b_i$ where $a_i < b_i$ and there exists no order between $a_i < b_j$ when $i\neq j$. This means that to know whether ...
ratchet freak's user avatar
1 vote
Accepted

Efficiently determine relative ordering between two elements in a PO-set

This is the dynamic reachability problem for DAGs, where you only need to handle vertex/edge insertion (but not deletion). It's sometimes known as incremental reachability or incremental DAG ...
D.W.'s user avatar
  • 158k
1 vote

How to solve this partial order reduction in $O(n^2)$?

Your solution looks good to me, except that your lookup arrays are a bit handwavy: What happens if the set contains negative numbers? Or what if it contains an extremely large number ($\gg n^2$), so ...
ruakh's user avatar
  • 613
1 vote
Accepted

How to solve this partial order reduction in $O(n^2)$?

I think I am able to solve it. First, have a lookup array for each sequence where array[element] = element's position in sequence [O(1)]. Phrased another way, this algorithm will find all "...
hazrmard's user avatar
  • 121

Only top scored, non community-wiki answers of a minimum length are eligible