Given a list of comparisons, sort items with as few additional comparisons as possible

user_1114253 0
Viewed 91

You have n items x[0], ..., x[n-1]. Beforehand, you're given a list of several comparisons c[0], ..., c[k] for those items (e.g. c[0] = (x[0] < x[4]), c[1] = (x[3] > x[7]), etc.).

The objective is to sort the items by requesting as few additional comparisons as possible.

For example, if c contains all the pairwise comparisons, then you don't need to request any additional ones to be able to sort the list. If c contained nothing, then you'd request O(n*log(n)) additional comparisons to perhaps quicksort the items. But if c contained something in between, how could we smartly leverage those existing comparisons to guide the extra comparisons we request?

Computation time doesn't matter (so long as it's sub-exponential). All that matters is the algorithm requests roughly the fewest additional comparisons.

Vaguely, I have an idea about constructing a DAG from the comparisons in c, and then doing a topological sort for the DAG to get a partial ordering, but I'm not sure where to go from there.

directed-acyclic-graphs graph-theory time-complexity sorting algorithm
2 Answers

Further ideas about the DAG representation:

  1. You're not done if your graph has more than one component.

  2. You're not done if your graph has more than one node with 0 in-degree or more than one node with 0 out-degree.

  3. The transitive reduction of the graph should be linear — that is, if any node in the transitive reduction has in-degree or out-degree of more than 1, you're not done.

  4. Equivalent to #3, there should be no antichains of more than one element.

I'm assuming that you don't have to choose all of your comparisons in advance, but that graph operations are cheap relative to comparisons (maybe the comparisons require running an experiment, or slow external communication). Then it seems like this would be a decent approach:

  1. Identify components.

  2. For each component, get all of the antichains of more than one element, and do enough comparisons to sort all of the elements of each antichain (you can use any conventional sorting algorithm here; by definition, we have no useful prior information about antichains, so it's like sorting a random list), adding the edges as you discover them. When this is complete, the transitive reduction of each component should equal its toposort, which will be unique — that is, you've reduced each component to a sorted list.

  3. Take components pairwise and "merge sort" them by comparing the smallest elements of the two components to each other, "popping" off the smaller of the two to the end of a new component, and repeating. If one component becomes empty, the remaining items of the other one can be tacked on to the end with no more comparisons. I suspect that repeatedly merging the two smallest components would be optimal for this stage; when there's only one component left, you're done.

user_1529480

The answer is Karzanov and Khachiyan (1991) (randomized), and Kahn and Kim (1995) (improved and deterministic).

Both are on the order of optimal O(log(E(P))), where E(P) is the total number of permutations of the items that satisfy your list of comparisons c.

I'll quickly go over the randomized algorithm here. Here's how you choose the next comparison to make:

  1. Generate n sample permutations of the items that satisfy the comparisons via the RandWalk algorithm
  2. Assign each item an average rank r_i based on its average index over the samples
  3. Choose to compare two items whose difference in average rank is less than 1.

The RandWalk algorithm is as follows

  1. Do a topological sort to get an ordering x_1, ..., x_n of the items that satisfies the comparisons c.
  2. To get the next sample, repeat n times:
  3. choose an index i uniformly from 1 to n-1. If x_i < x_(i+1) is not implied by your comparisons c (no direct path between them), then swap x_i and x_(i+1).
  4. the ordering you're left with will be 1 sample ordering that's approximately uniformly chosen from all possible orderings that satisfy c.
user_11142530
Related