Next: Sequencing and Scheduling
a node-weight function
and a page-capacity p.
A compact packing of T into pages of capacity p, i.e., a
The number of page faults of the packing, i.e.,
l(v) denotes the number of edges in the path from the root to v,
denotes the ith node in this path, and
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 .
If all w(v) are equal then it is approximable with an absolute error
guarantee of 1/2.