We study ordinal embedding relaxations in the realm of parameterized complexity. We prove the existence of a quadratic kernel for the Betweenness problem parameterized above tight lower bound, which is stated as follows.

For a set V of variables and set C of constraints "u is between v and w", decide whether there is a bijection from V to the set {1,...,|V|} satisfying at least |C|/3 + k of the constraints in C.