2009 | OriginalPaper | Buchkapitel
Fractional Weak Discrepancy of Posets and Certain Forbidden Configurations
verfasst von : Alan Shuchat, Randy Shull, Ann N. Trenk
Erschienen in: The Mathematics of Preference, Choice and Order
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.