Tanenbaum, Trenk, and Fishburn introduced the concept of lineardiscrepancy in 2001, proposing it as a way to measure a partiallyordered set's distance from being a linear order. In addition toproving a number of results about linear discrepancy, they posedeight challenges and questions for future work. This dissertationcompletely resolves one of those challenges and makes contributionson two others. This dissertation has three principal components:3-discrepancy irreducible posets of width 3, degree bounds, andonline algorithms for linear discrepancy. The first principalcomponent of this dissertation provides a forbidden subposetcharacterization of the posets with linear discrepancy equal to 2by completing the determination of the posets that are3-irreducible with respect to linear discrepancy. The secondprincipal component concerns degree bounds for linear discrepancyand weak discrepancy, a parameter similar to lineardiscrepancy. Specifically, if every point of a poset is incomparableto at most D other points of the poset, we prove threebounds: the linear discrepancy of an interval order is at mostD, with equality if and only if it contains an antichain ofsize D; the linear discrepancy of a disconnected poset isat most the greatest integer less than or equal to (3D-1)/2; and the weak discrepancy of aposet is at most D. The third principal component of thisdissertation incorporates another large area of research, that ofonline algorithms. We show that no online algorithm for lineardiscrepancy can be better than 3-competitive, even for the classof interval orders. We also give a 2-competitive online algorithmfor linear discrepancy on semiorders and show that this algorithm isoptimal.
【 预 览 】
附件列表
Files
Size
Format
View
Some results on linear discrepancy for partially ordered sets
PDF
download
878987797
028-85220240
