MAXIMUM BETWEENNESS

• INSTANCE: Finite set A, collection C of ordered triples (a,b,c) of distinct elements from A.

• SOLUTION: A one-to-one function $f:A\rightarrow[1..\vert A\vert ]$.

• MEASURE: Number of triples where either f(a)<f(b)<f(c) or f(c)<f(b)<f(a).

  
  

• Good News: Approximable within 2 for satisfiable instances [112].

• Bad News: APX-hard [112].

• Comment: Admits a PTAS if $\vert C\vert=\Theta(\vert A\vert^3)$ [36].

• Garey and Johnson: MS1