# Tag Info

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 ...
• 276k
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$ ...
• 158k
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. ...
• 3,127
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 ...
• 276k
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.
• 276k
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 ...
• 276k
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$. ...
• 276k
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 ...
• 38.8k

### 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 ...
• 276k
Accepted

• 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 ...
• 111
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 ...
• 276k
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 ...
• 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 ...
• 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 ...
• 4,361
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 ...
• 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 ...
• 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 "...
• 121

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