Next: Sequencing and Scheduling
Up: Miscellaneous
Previous: Miscellaneous
  Index
- INSTANCE:
A tree
,
a node-weight function
such that
,
and a page-capacity p.
- SOLUTION:
A compact packing of T into pages of capacity p, i.e., a
function
such that
.
- MEASURE:
The number of page faults of the packing, i.e.,
where
l(v) denotes the number of edges in the path from the root to v,
denotes the ith node in this path, and
is
equal to 0 if the parent of v is assigned the same page of u, it
is equal to 1 otherwise.
- Good News:
Approximable with an absolute error guarantee of 1 [193].
- Comment:
If all w(v) are equal then it is approximable with an absolute error
guarantee of 1/2.
Viggo Kann
2000-03-20