The total weak discrepancy of a partially ordered set - Shuchat, Alan (Ars mathematica contemporanea, 2011)
We define the total weak discrepancy of a poset ?$P$? as the minimum nonnegative integer ?$k$? for which there exists a function ?$f : V → {\mathbf Z}$? satisfying (i) if ?$a \prec b$? then ?$f(a) + 1 ≤ f(b)$? and (ii) ?$\sum|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: delno urejene množice; fractional weak discrepancy; popolnoma linearna neskladnost; posets; šibka neskladnost; total linear discrepancy; weak discrepancy