Is there any non-trivial approximation algorithm for a variant of betweenness problem: namely, we want to minimize the number of unsatisfied triples rather than to maximize the number of satisfied ones?
A variant of betweenness problem
ds.algorithms;approximation algorithms;csp