The total linear discrepancy of an ordered set

In this paper we introduce the notion of the total linear discrepancy   of a poset as a way of measuring the fairness of linear extensions. If LL is a linear extension of a poset PP, and x,yx,y is an incomparable pair in PP, the height difference between xx and yy in LL is |L(x)−L(y)||L(x)−L(y)|. The total linear discrepancy of PP in LL is the sum over all incomparable pairs of these height differences. The total linear discrepancy of PP is the minimum of this sum taken over all linear extensions LL of PP. While the problem of computing the (ordinary) linear discrepancy of a poset is NP-complete, the total linear discrepancy can be computed in polynomial time. Indeed, in this paper, we characterize those linear extensions that are optimal for total linear discrepancy. The characterization provides an easy way to count the number of optimal linear extensions.