A variant of betweenness problem
The particular minimization version which you mentioned does not make much sense, because even deciding whether all triples can be satisfied simutaneously or not is NP-comlpete.  Also, it is easy to see that unless P=NP, for every choice of constants k1 and k2, there is no polynomial-time approximation algorithm for the minimization version of the betweenness problem in the sense that it produces an assignment which violates at most (k1⋅OPT + k2) triples, where OPT is the minimum number of violated triples.  (Just consider the case where OPT=0.)  [Edit: In an earlier revision, I stated that this follows from [CS98], but [CS98] was overkill for it.]

On a tangentially related topic, if you consider the additive approximation of the ratio of (un)satisfied triples, the problem becomes much more interesting.  Chor and Sudan [CS98] showed that for every s∈(47/48,1), it is NP-complete to decide whether a given instance of the betweenness problem is satisfiable or no assignment satisfies more than s fraction of constraints.  In particular, the ratio version is NP-hard to approximate within any constant additive error less than 1/48, and this clearly applies equally to both the maximization version and the minimization version.

For more on approximation of a satisfaction ratio within an additive error, see my answer to the question “Hardness of approximation - additive error” by Raphael Clifford.

[CS98] Benny Chor and Madhu Sudan.  A geometric approach to betweenness.  SIAM Journal on Discrete Mathematics, 11(4):511–523, Nov. 1998.  DOI: 10.1137/S0895480195296221.