Tanenbaum, Trenk, and Fishburn introduced the concept of linear
discrepancy in 2001, proposing it as a way to measure a partially
ordered set's distance from being a linear order. In addition to
proving a number of results about linear discrepancy, they posed
eight challenges and questions for future work. This dissertation
completely resolves one of those challenges and makes contributions
on two others. This dissertation has three principal components:
3-discrepancy irreducible posets of width 3, degree bounds, and
online algorithms for linear discrepancy. The first principal
component of this dissertation provides a forbidden subposet
characterization of the posets with linear discrepancy equal to 2
by completing the determination of the posets that are
3-irreducible with respect to linear discrepancy. The second
principal component concerns degree bounds for linear discrepancy
and weak discrepancy, a parameter similar to linear
discrepancy. Specifically, if every point of a poset is incomparable
to at most D other points of the poset, we prove three
bounds: the linear discrepancy of an interval order is at most
D, with equality if and only if it contains an antichain of
size D; the linear discrepancy of a disconnected poset is
at most the greatest integer less than or equal to (3D-1)/2; and the weak discrepancy of a
poset is at most D. The third principal component of this
dissertation incorporates another large area of research, that of
online algorithms. We show that no online algorithm for linear
discrepancy can be better than 3-competitive, even for the class
of interval orders. We also give a 2-competitive online algorithm
for linear discrepancy on semiorders and show that this algorithm is
optimal.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/33810 |
| Date | 24 November 2009 |
| Creators | Keller, Mitchel Todd |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Detected Language | English |
| Type | Dissertation |
Page generated in 0.0019 seconds