Betweenness problem

[3] The input to a betweenness problem is a collection of ordered triples of items.

The related problem of finding an ordering that maximizes the number of satisfied triples is MAXSNP-hard, implying that it is impossible to achieve an approximation ratio arbitrarily close to 1 in polynomial time unless P = NP.

[4] The minimum version of the problem restricted to the tournaments was proven to have polynomial time approximation schemes (PTAS).

[8] Although not guaranteed to succeed, a greedy heuristic can find solutions to many instances of the betweenness problem arising in practice.

[2] One application of betweenness arises in bioinformatics, as part of the process of gene mapping.