1
$\begingroup$

I have a set of objects and a set of comparison results for some of them.

I want an algorithm that returns the next comparison I should make to two objects towards having a way to know the full order of all objects. If the order of all objects can be already known I should get the objects ordered.

Requirements: ask for the minimal number of comparisons between objects as they are the most expensive operation.

For example: I know elements A,B,C,D and relations A->B , A->C , B->D , C->D the algorithm should return next pair to compare B and C

New contributor
Eduardo is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
1
  • $\begingroup$ Unfortunately no efficient algorithms are known for this problem. $\endgroup$ Oct 14 at 7:58
1
$\begingroup$

A similar question has been considered in the literature: given a poset $P$ and a list of elements whose order is consistent with $P$, how many comparisons are needed in order to order the list? If there are $e(P)$ many extensions of $P$ to a linear order, then clearly at least $\log_2 e(P)$ many comparisons are needed. Conversely, Kislytsin and Fredman showed (separately) that $\log_2 e(P) + 2n$ comparisons suffice, but their algorithms cannot be implemented efficiently. Kahn and Kim gave in their classic paper Entropy and Sorting an efficient algorithm which uses $O(\log e(P))$ comparisons.

While these results might have been improved along the years (you can check this by going over papers citing Kahn–Kim), it might be too much to ask for an optimal algorithm which can be implemented efficiently.

$\endgroup$

Your Answer

Eduardo is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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