Advertisement
Published in:
2009 | OriginalPaper | Chapter
Fractional Weak Discrepancy of Posets and Certain Forbidden Configurations
Authors : Alan Shuchat, Randy Shull, Ann N. Trenk
Published in: The Mathematics of Preference, Choice and Order
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A weak order is a poset
P
= (V, ≺) that can be assigned a real-valued function
f
:
V
→ R so that
a
≺
b
in P if and only if
f(a)
<
f(b)
Bogart (1990). Thus, the elements of a weak order can be ranked by a function that respects the ordering ≺ and issues a tie in ranking between incomparable elements (
a
ǁ
b
). When
P
is not a weak order, it is not possible to resolve ties as fairly. The
weak discrepancy
of a poset, introduced in Trenk (1998) as the
weakness
of a poset, is a measure of how far a poset is from being a weak order [Gimbel and Trenk (1998); Tanenbaum, Trenk, & Fishburn (2001)]. In Shuchat, Shull, and Trenk (2007), the problem of determining the weak discrepancy of a poset was formulated as an integer program whose linear relaxation yields a fractional version of weak discrepancy given in Definition 1 below.