### The total weak discrepancy of a partially ordered set

#### Abstract

We define the total weak discrepancy of a poset

*P*as the minimum nonnegative integer*k*for which there exists a function*f*:*V*→**Z**satisfying (i) if*a*\prec*b*then*f*(*a*) + 1 ≤*f*(*b*) and (ii) Σ|*f*(*a*) −*f*(*b*)| ≤*k*, where the sum is taken over all unordered pairs {*a*,*b*} of incomparable elements. If we allow*k*and*f*to take real values, we call the minimum*k*the fractional total weak discrepancy of*P*. These concepts are related to the notions of weak and fractional weak discrepancy, where (ii) must hold not for the sum but for each individual pair of incomparable elements of*P*. We prove that, unlike the latter, the total weak and fractional total weak discrepancy of*P*are always the same, and we give a polynomial-time algorithm to find their common value. We use linear programming duality and complementary slackness to obtain this result.#### Keywords

Partial orders; weak discrepancy; graph algorithms; network models; linear programming duality

DOI: https://doi.org/10.26493/1855-3974.159.1f8

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications