Next: MINIMUM DECISION TREE Up: Miscellaneous Previous: Miscellaneous Index

### 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 .

- 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 [104].

- Bad News: APX-hard [104].

- Comment: Admits a PTAS if [34].

- Garey and Johnson: MS1