Next: Sequencing and Scheduling Up: Miscellaneous Previous: Miscellaneous Index

### MINIMUM TREE COMPACT PACKING

- 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, vi 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 [181].

- Comment: If all w(v) are equal then it is approximable with an absolute error guarantee of 1/2.