- 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*i*th 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.