Narodna in univerzitetna knjižnica, Ljubljana (NUK)
Naročanje gradiva za izposojo na dom
Naročanje gradiva za izposojo v čitalnice
Naročanje kopij člankov
Urnik dostave gradiva z oznako DS v signaturi
  • The total weak discrepancy of a partially ordered set
    Shuchat, Alan ; Shull, Randy ; Trenk, Ann N.
    We define the total weak discrepancy of a poset ▫$P$▫ as the minimum nonnegative integer ▫$k$▫ for which there exists a function ▫$f : V \to {\mathbf Z}$▫ satisfying (i) if ▫$a \prec b$▫ then ▫$f(a) ... + 1 \leq f(b)$▫ and (ii) ▫$\sum|f(a) - f(b)| \leq 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.
    Vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 4, no. 1, 2011, str. 95-109)
    Vrsta gradiva - članek, sestavni del
    Leto - 2011
    Jezik - angleški
    COBISS.SI-ID - 16263513

    Povezava(-e):

    http://amc.imfm.si/index.php/amc/article/view/159
    Digitalna knjižnica Slovenije - dLib.si

vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 4, no. 1, 2011, str. 95-109)

loading ...
loading ...
loading ...

Vnos na polico