Search

Abstract: The fractional weak discrepancy of a poset was introduced in Shuchat et al. (2007)  as the minimum nonnegative for which there exists a function satisfying (i) if then and (ii) if then . In this paper we generalize results in Shuchat et al. (2006, 2009) on the range of for semiorders to the larger class of split semiorders. In particular, we prove that for such posets the range is the set of rationals that can be represented as for which . [Copyright &y& Elsevier]

Abstract: The fractional weak discrepancy of a poset was introduced in [A. Shuchat, R. Shull, A. Trenk, The fractional weak discrepancy of a partially ordered set, Discrete Applied Mathematics 155 (2007) 2227–2235] as the minimum nonnegative for which there exists a function satisfying (i) if then and (ii) if then . In this paper we generalize results in [A. Shuchat, R. Shull, A. Trenk, Range of the fractional weak discrepancy function, ORDER 23 (2006) 51–63; A. Shuchat, R. Shull, A. Trenk, Fractional weak discrepancy of posets and certain forbidden configurations, in: S.J. Brams, W.V. Gehrlein, F.S. Roberts (Eds.), The Mathematics of Preference, Choice, and Order: Essays in Honor of Peter C. Fishburn, Springer, New York, 2009, pp. 291–302] on the range of the function for semiorders (interval orders with no induced ) to interval orders with no , where . In particular, we prove that the range for such posets is the set of rationals that can be written as , where . If and has an optimal forcing cycle with and , then . Moreover when , for each satisfying there is an interval order having such an optimal forcing cycle and containing no. [Copyright &y& Elsevier]

Abstract: In this paper we introduce the notion of the fractional weak discrepancy of a poset, building on previous work on weak discrepancy in [J.G. Gimbel and A.N. Trenk, On the weakness of an ordered set, SIAM J. Discrete Math. 11 (1998) 655–663; P.J. Tanenbaum, A.N. Trenk, P.C. Fishburn, Linear discrepancy and weak discrepancy of partially ordered sets, ORDER 18 (2001) 201–225; A.N. Trenk, On k-weak orders: recognition and a tolerance result, Discrete Math. 181 (1998) 223–237]. The fractional weak discrepancy of a poset is the minimum nonnegative k for which there exists a function satisfying (1) if then and (2) if then . We formulate the fractional weak discrepancy problem as a linear program and show how its solution can also be used to calculate the (integral) weak discrepancy. We interpret the dual linear program as a circulation problem in a related directed graph and use this to give a structural characterization of the fractional weak discrepancy of a poset. [Copyright &y& Elsevier]