A Study to Generate a Weak Order from a Partially Ordered Set, Taken. . .
69
H av(x) :=
h (L(k), x)
/LT
(k = 1, . . . , LT )
(5)
where LT is the number of linear extensions derived from a specific poset.
Equation 5 could be a good starting point, when the set of linear extensions is
small. Taking into mind that the number of linear extensions for an object set with
n objects can be up to n! the problem to generate linear extensions and store them
into a memory is computationally hard (see e.g. Atkinson and Chang 1986).
The above mentioned difficulty leads to several variants:
• There is still an exact method available. It is based on the fact that the storage
of some sets derived from the poset needs less memory than the storage of
the linear extensions. From a methodological, mathematical point of view this
method transforms the original poset into a lattice and the quantities of interest
can be directly derived from this lattice (De Loof et al. 2006). However, the
lattice-method is only working, when U*n (U: number of incomparabilities in a
set of n objects) is not too large, for details see Bruggemann and Carlsen (2011).
• Some approximations seem to have found more applications, for instance the
method of Bubley and Dyer (1999), which suggests a “good” sampling of linear
extensions.
• Another one has a graph – theoretical background and considers the local
environment around each object within a poset. There are two variants: (1)
the LPOM0 (local partial order model 0) Bruggemann et al. 2004) and (2)
an extended model (LPOMext) (Bruggemann and Carlsen 2011). Although the
extended variant is thought of as delivering better results than LPOM0, it turned
out (Rocco and Tarantola 2014) that the more simple method (LPOM0) may be
in some cases a better approximation than the extended one.
2.6 Idea for an Alternative for the Hav-Calculation
Often partial order can be considered as being composed from simpler posets, here
for example, the concept of linear sum is of specific interest. It is defined as follows:
Let X 1 , X 2 be disjoint subsets of X with
X = X 1 ⊕ X 2
(6a)
x ∈ X 1 , y ∈ X 2 implies x > y for every x, y
(6b)
Equation (6b) can be formulated as follows: If two sets can be found where for
an element of the first set, x, and for any element of the second set, y, is valid: x > y;
the relations among the first, and the second set, resp., are not of interest.
69
H av(x) :=
h (L(k), x)
/LT
(k = 1, . . . , LT )
(5)
where LT is the number of linear extensions derived from a specific poset.
Equation 5 could be a good starting point, when the set of linear extensions is
small. Taking into mind that the number of linear extensions for an object set with
n objects can be up to n! the problem to generate linear extensions and store them
into a memory is computationally hard (see e.g. Atkinson and Chang 1986).
The above mentioned difficulty leads to several variants:
• There is still an exact method available. It is based on the fact that the storage
of some sets derived from the poset needs less memory than the storage of
the linear extensions. From a methodological, mathematical point of view this
method transforms the original poset into a lattice and the quantities of interest
can be directly derived from this lattice (De Loof et al. 2006). However, the
lattice-method is only working, when U*n (U: number of incomparabilities in a
set of n objects) is not too large, for details see Bruggemann and Carlsen (2011).
• Some approximations seem to have found more applications, for instance the
method of Bubley and Dyer (1999), which suggests a “good” sampling of linear
extensions.
• Another one has a graph – theoretical background and considers the local
environment around each object within a poset. There are two variants: (1)
the LPOM0 (local partial order model 0) Bruggemann et al. 2004) and (2)
an extended model (LPOMext) (Bruggemann and Carlsen 2011). Although the
extended variant is thought of as delivering better results than LPOM0, it turned
out (Rocco and Tarantola 2014) that the more simple method (LPOM0) may be
in some cases a better approximation than the extended one.
2.6 Idea for an Alternative for the Hav-Calculation
Often partial order can be considered as being composed from simpler posets, here
for example, the concept of linear sum is of specific interest. It is defined as follows:
Let X 1 , X 2 be disjoint subsets of X with
X = X 1 ⊕ X 2
(6a)
x ∈ X 1 , y ∈ X 2 implies x > y for every x, y
(6b)
Equation (6b) can be formulated as follows: If two sets can be found where for
an element of the first set, x, and for any element of the second set, y, is valid: x > y;
the relations among the first, and the second set, resp., are not of interest.