Simple linear time approximation algorithm for betweenness

M. Charikar, V. Guruswami, R. Manokaran, Every Permutation CSP of arity 3 is Approximation Resistant, in Proc. of the 24th Annual IEEE Conference on Computational Complexity, pp. 62–73, 2009. http://dx.doi.org/10.1109/CCC.2009.29. Chor, 1998, A geometric approach to betweenness, SIAM Journal on Discrete Mathematics, 11, 511, 10.1137/S0895480195296221 Opatrny, 1979, Total ordering problem, SIAM Journal on Computing, 8, 111, 10.1137/0208008