
32 Energy-Aware Memory Management for EMSs
Table 2.1 Duality between polyhedra and cones.
Inhomogeneous system
Homogeneous system
Structure Polyhedron P, dimension d Cone C, dimension d +1
Implicit
representation
using
equations
and
inequalities
P = {x |Ax = b, Cx ≥ d}C= {ˆx |
ˆ
Aˆx =0,
ˆ
C ˆx ≥ 0}
ˆx =
x
ˆ
A =
A −b
ˆ
C =
C −d
0 1
Parametric
representation
using
vertices, rays,
and lines
P = {x |x = L + R + V ,
, ≥ 0,
=1}
C = {ˆx | ˆx =
ˆ
L +
ˆ
R,
≥ 0}
Vertices v =
⎛
⎜
⎜
⎝
v
1
v
2
.
.
.
v
d
⎞
⎟
⎟
⎠
,v∈ V ˆr
v
=
⎛
⎜
⎜
⎜
⎝
v
1
v
2
.
.
.
v
d
⎞
⎟
⎟
⎟
⎠
, > 0, ˆr
v
∈
ˆ
R
Rays r =
⎛
⎜
⎜
⎝
r
1
r
2
.
.
.
r
d
⎞
⎟
⎟
⎠
,r∈ R ˆr
r
=
⎛
⎜
⎜
⎜
⎝
r
1
r
2
.
.
.
r
d
0
⎞
⎟
⎟
⎟
⎠
, ˆr
r
∈
ˆ
R
Lines l =
⎛
⎜
⎜
⎝
l
1
l
2
.
.
.
l
d
⎞
⎟
⎟
⎠
,l∈ L
ˆ
l =
⎛
⎜
⎜
⎜
⎝
l
1
l
2
.
.
.
l
d
0
⎞
⎟
⎟
⎟
⎠
,
ˆ
l ∈
ˆ
L
differen ...