# A variant of betweenness problem

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?

• You cannot hope for any multiplicative approximation because it is NP-complete to decide whether all triples can be simultaneously satisfied or not (the original, decision version of betweenness). May 28, 2012 at 18:07
• fair enough, but what if we allow some (small) additive error? May 28, 2012 at 18:08
• Then what is the difference between maximizing the number of satisfied triples and minimizing the number of unsatisfied triples? May 28, 2012 at 18:09
• I don't see how an algorithm with an additive error 1 for the minimization problem is implied by any known algorithm for the maximization version. May 28, 2012 at 18:12
• Well, that is because an algorithm with an additive error 1 in the minimization version is equivalent to an algorithm with an additive error 1 in the maximization version (which does not exist unless P=NP). May 28, 2012 at 18:16