For a finite poset $P = (X, \preceq)$ the {\it fractional weak discrepancy} of $P$, denoted $wd_F(P)$, is the minimum value $t$ for which there is a function $f: X \longrightarrow \mathbb{R}$ ...satisfying (1) $f(x) + 1 \le f(y)$ whenever $x \prec y$ and (2) $|f(x) - f(y)| \le t$ whenever $x \| y$. In this paper, we determine the range of the fractional weak discrepancy of $(M, 2)$-free posets for $M \ge 5$, which is a problem asked in \cite{sst3}. More precisely, we showed that (1) the range of the fractional weak discrepancy of $(M, 2)$-free interval orders is $W = \{ \frac{r}{r+1} \colon r \in \mathbb{N} \cup \{ 0 \} \} \cup \{ t \in \mathbb{Q} \colon 1 \le t < M - 3 \}$ and (2) the range of the fractional weak discrepancy of $(M, 2)$-free non-interval orders is $\{ t \in \mathbb{Q} \colon 1 \le t < M - 3 \}$. The result is a generalization of a well-known result for semiorders and the main result for split semiorders of \cite{sst3} since the family of semiorders is the family of $(4, 2)$-free posets. KCI Citation Count: 1
The aim of this work is to approximate the trajectory solution of parabolic partial differential equations (PDEs) by the probabilistic method. This method is based on the representation of ...Feynman-Kac and Monte Carlo methods. As an alternative to classical Monte Carlo, here we employ quasi-Monte Carlo methods and propose some solutions to the problem of using this alternative through a more efficient algorithm than the classics.
The
fractional weak discrepancy
w
d
F
(
P
)
of a poset
P
=
(
V
,
≺
)
was introduced in Shuchat et al. (2007)
6 as the minimum nonnegative
k
for which there exists a function
f
:
V
→
R
satisfying (i) ...if
a
≺
b
then
f
(
a
)
+
1
≤
f
(
b
)
and (ii) if
a
∥
b
then
|
f
(
a
)
−
f
(
b
)
|
≤
k
. In this paper we generalize results in Shuchat et al. (2006, 2009)
5,7 on the range of
w
d
F
for semiorders to the larger class of split semiorders. In particular, we prove that for such posets the range is the set of rationals that can be represented as
r
/
s
for which
0
≤
s
−
1
≤
r
<
2
s
.
The
fractional weak discrepancy
w
d
F
(
P
)
of a poset
P
=
(
V
,
≺
)
was introduced in A. Shuchat, R. Shull, A. Trenk, The fractional weak discrepancy of a partially ordered set, Discrete Applied ...Mathematics 155 (2007) 2227–2235 as the minimum nonnegative
k
for which there exists a function
f
:
V
→
R
satisfying (i) if
a
≺
b
then
f
(
a
)
+
1
≤
f
(
b
)
and (ii) if
a
∥
b
then
|
f
(
a
)
−
f
(
b
)
|
≤
k
. In this paper we generalize results in A. Shuchat, R. Shull, A. Trenk, Range of the fractional weak discrepancy function, ORDER 23 (2006) 51–63; A. Shuchat, R. Shull, A. Trenk, Fractional weak discrepancy of posets and certain forbidden configurations, in: S.J. Brams, W.V. Gehrlein, F.S. Roberts (Eds.), The Mathematics of Preference, Choice, and Order: Essays in Honor of Peter C. Fishburn, Springer, New York, 2009, pp. 291–302 on the range of the
w
d
F
function for semiorders (interval orders with no induced
3
+
1
) to interval orders with no
n
+
1
, where
n
≥
3
. In particular, we prove that the range for such posets
P
is the set of rationals that can be written as
r
/
s
, where
0
≤
s
−
1
≤
r
<
(
n
−
2
)
s
. If
w
d
F
(
P
)
=
r
/
s
and
P
has an optimal forcing cycle
C
with
up
(
C
)
=
r
and
side
(
C
)
=
s
, then
r
≤
(
n
−
2
)
(
s
−
1
)
. Moreover when
s
≥
2
, for each
r
satisfying
s
−
1
≤
r
≤
(
n
−
2
)
(
s
−
1
)
there is an interval order having such an optimal forcing cycle and containing no
n
+
1
.
In this paper we introduce the notion of the fractional weak discrepancy of a poset, building on previous work on weak discrepancy in J.G. Gimbel and A.N. Trenk, On the weakness of an ordered set, ...SIAM J. Discrete Math. 11 (1998) 655–663; P.J. Tanenbaum, A.N. Trenk, P.C. Fishburn, Linear discrepancy and weak discrepancy of partially ordered sets, ORDER 18 (2001) 201–225; A.N. Trenk, On
k-weak orders: recognition and a tolerance result, Discrete Math. 181 (1998) 223–237. The
fractional weak discrepancy
wd
F
(
P
)
of a poset
P
=
(
V
,
≺
)
is the minimum nonnegative
k for which there exists a function
f
:
V
→
R
satisfying (1) if
a
≺
b
then
f
(
a
)
+
1
⩽
f
(
b
)
and (2) if
a
∥
b
then
|
f
(
a
)
-
f
(
b
)
|
⩽
k
. We formulate the fractional weak discrepancy problem as a linear program and show how its solution can also be used to calculate the (integral) weak discrepancy. We interpret the dual linear program as a circulation problem in a related directed graph and use this to give a structural characterization of the fractional weak discrepancy of a poset.
The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable, then |hL(x)−hL(y)|≤k, whereas the weak discrepancy is the least ...k such that there is a weak extension W of P such that if x and y are incomparable, then |hW(x)−hW(y)|≤k. This paper resolves a question of Tanenbaum, Trenk, and Fishburn on characterizing when the weak and linear discrepancy of a poset are equal. Although it is shown that determining whether a poset has equal weak and linear discrepancy is NP-complete, this paper provides a complete characterization of the minimal posets with equal weak and linear discrepancy. Further, these minimal posets can be completely described as a family of interval orders.
In this paper we introduce the notion of the
total linear discrepancy of a poset as a way of measuring the fairness of linear extensions. If
L
is a linear extension of a poset
P
, and
x
,
y
is an ...incomparable pair in
P
, the height difference between
x
and
y
in
L
is
|
L
(
x
)
−
L
(
y
)
|
. The total linear discrepancy of
P
in
L
is the sum over all incomparable pairs of these height differences. The total linear discrepancy of
P
is the minimum of this sum taken over all linear extensions
L
of
P
. While the problem of computing the (ordinary) linear discrepancy of a poset is NP-complete, the total linear discrepancy can be computed in polynomial time. Indeed, in this paper, we characterize those linear extensions that are optimal for total linear discrepancy. The characterization provides an easy way to count the number of optimal linear extensions.
The t -discrepancy of a poset Howard, David; Trenk, Ann N.
Discrete Applied Mathematics,
08/2010, Letnik:
158, Številka:
16
Journal Article
Recenzirano
Odprti dostop
Linear discrepancy and weak discrepancy have been studied as a measure of fairness in giving integer ranks to the points of a poset. In linear discrepancy, the points are totally ordered, while in ...weak discrepancy, ties in rank are permitted. In this paper we study the
t
-discrepancy of a poset, which can be viewed as a hybrid between linear and weak discrepancy, in which at most
t
points can receive the same rank. Interestingly,
t
-discrepancy is not a comparability invariant while both linear and weak discrepancy are. We show that for a poset
P
and positive integers
t
and
k
, the decision problem of determining whether the
t
-discrepancy of
P
is at most
k
is NP-complete in general; however, we give a polynomial time algorithm for computing the
t
-discrepancy of a semiorder. We also find the
t
-discrepancy for posets that are the disjoint sum of chains.
PDF
