Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Let a polyhedron
P
be defined by one of the following ways:
P
=
{
x
∈
R
n
:
A
x
≤
b
}
, where
A
∈
Z
(
n
+
k
)
×
n
,
b
∈
Z
(
n
+
k
)
and
rank
A
=
n
,
P
=
{
x
∈
R
+
n
:
A
x
=
b
}
, where
A
∈
Z
k
×
n
,
b
∈
Z
k
and
rank
A
=
k
,
and let all rank order minors of
A
be bounded by
Δ
in absolute values. We show that the short rational generating function for the power series
∑
m
∈
P
∩
Z
n
x
m
can be computed with the arithmetical complexity
O
T
SNF
(
d
)
·
d
k
·
d
log
2
Δ
,
where
k
and
Δ
are fixed,
d
=
dim
P
, and
T
SNF
(
m
)
is the complexity of computing the Smith Normal Form for
m
×
m
integer matrices. In particular,
d
=
n
, for the case (i), and
d
=
n
-
k
, for the case (ii). The simplest examples of polyhedra that meet the conditions (i) or (ii) are the
simplices
, the
subset sum
polytope and the
knapsack
or
multidimensional knapsack
polytopes. Previously, the existence of a polynomial time algorithm in varying dimension for the considered class of problems was unknown already for simplicies (
k
=
1
). We apply these results to parametric polytopes and show that the step polynomial representation of the function
c
P
(
y
)
=
|
P
y
∩
Z
n
|
, where
P
y
is a parametric polytope, whose structure is close to the cases (i) or (ii), can be computed in polynomial time even if the dimension of
P
y
is not fixed. As another consequence, we show that the coefficients
e
i
(
P
,
m
)
of the Ehrhart quasi-polynomial
m
P
∩
Z
n
=
∑
j
=
0
n
e
j
(
P
,
m
)
m
j
can be computed with a polynomial-time algorithm, for fixed
k
and
Δ
.