SR10 M INIMUM T REE C OMPACT P ACKING

   
• I NSTANCE : A tree , a node-weight function such that , and a page-capacity p .
• S OLUTION : A compact packing of T into pages of capacity p , i.e., a function such that .
• M EASURE : 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 within absolute error 1 [ 130 ].
• Comment: If all w(v) are equal then it is approximable within absolute error 1/2.