Fishburn, Tanenbaum and Trenk \cite{FTT01a}
define the linear discrepancy ${\rm ld}(P)$ of a poset $P=(V,<_P)$
as the minimum integer $k\geq 0$
for which there exists a bijection $f:V\to\{ 1,2,\ldots,|V|\}$
such that $u<_P v$ implies $f(u) < f(v)$
and $u||_P v$ implies $|f(u)-f(v)|\leq k$.
In \cite{FTT01b} they prove that the linear discrepancy of
a poset equals the bandwidth of its cocomparability graph.
Here we provide partial solutions to some problems formulated
in \cite{FTT01a} about the linear discrepancy and the bandwidth
of cocomparability graphs.
DIMACS Home Page