0 KB333 KB37 KB200820252011Shuchat, AlanShull, RandyTrenk, Ann N.številka:1letnik:4str. 95-109COBISSID:16263513ISSN:1855-3966URN:URN:NBN:SI:doc-1JB7GEWTenDruštvo matematikov, fizikov in astronomov SlovenijeArs mathematica contemporaneadelno urejene množicefractional weak discrepancypopolnoma linearna neskladnostposetsšibka neskladnosttotal linear discrepancyweak discrepancyThe total weak discrepancy of a partially ordered set|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 resultTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije