Geodesic
The total weak discrepancy of a partially ordered set
Ars Mathematica Contemporanea, Tome 4 (2011) no. 1, pp. 95-109.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.159.1f8
Keywords: Partial orders, weak discrepancy, graph algorithms, network models, linear programming duality 
@article{10_26493_1855_3974_159_1f8,
     author = {Alan Shuchat and Randy Shull and Ann N. Trenk},
     title = {The total weak discrepancy of a partially ordered set},
     journal = {Ars Mathematica Contemporanea},
     pages = {95--109},
     publisher = {mathdoc},
     volume = {4},
     number = {1},
     year = {2011},
     doi = {10.26493/1855-3974.159.1f8},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.159.1f8/}
}
TY  - JOUR
AU  - Alan Shuchat
AU  - Randy Shull
AU  - Ann N. Trenk
TI  - The total weak discrepancy of a partially ordered set
JO  - Ars Mathematica Contemporanea
PY  - 2011
SP  - 95
EP  - 109
VL  - 4
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.159.1f8/
DO  - 10.26493/1855-3974.159.1f8
LA  - en
ID  - 10_26493_1855_3974_159_1f8
ER  - 
%0 Journal Article
%A Alan Shuchat
%A Randy Shull
%A Ann N. Trenk
%T The total weak discrepancy of a partially ordered set
%J Ars Mathematica Contemporanea
%D 2011
%P 95-109
%V 4
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.159.1f8/
%R 10.26493/1855-3974.159.1f8
%G en
%F 10_26493_1855_3974_159_1f8
Alan Shuchat; Randy Shull; Ann N. Trenk. The total weak discrepancy of a partially ordered set. Ars Mathematica Contemporanea, Tome 4 (2011) no. 1, pp. 95-109. doi : 10.26493/1855-3974.159.1f8. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.159.1f8/

Cité par Sources :