The tt-discrepancy of a poset

Linear discrepancy and weak discrepancy have been studied as a measure of fairness in giving integer ranks to the points of a poset. In linear discrepancy, the points are totally ordered, while in weak discrepancy, ties in rank are permitted. In this paper we study the tt-discrepancy of a poset, which can be viewed as a hybrid between linear and weak discrepancy, in which at most tt points can receive the same rank. Interestingly, tt-discrepancy is not a comparability invariant while both linear and weak discrepancy are. We show that for a poset PP and positive integers tt and kk, the decision problem of determining whether the tt-discrepancy of PP is at most kk is NP-complete in general; however, we give a polynomial time algorithm for computing the tt-discrepancy of a semiorder. We also find the tt-discrepancy for posets that are the disjoint sum of chains.