1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Are you looking for a practical implementation or just a theoretical one like the current answer? $\endgroup$ Apr 3, 2022 at 23:08
  • $\begingroup$ @SalvatoreAmbulando a practical implementation would be nice, but I was mostly interested in the theory $\endgroup$
    – chausies
    Apr 4, 2022 at 5:35
  • 1
    $\begingroup$ This paper talks about the problem and gives what they say is a more practical solution. I found it a bit easier to understand too. arxiv.org/abs/0911.0086 I didn't know this was a question people were specifically studying before I saw your question, thanks! $\endgroup$ Apr 4, 2022 at 15:28

1 Answer 1

2
$\begingroup$

Your problem is solved in Kahn and Kim, Entropy and sorting.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.