MINIMUM TREE COMPACT PACKING

• INSTANCE: A tree $T=\left(V,E\right)$, a node-weight function $w: V \rightarrow Q^{+}$ such that $\sum_{v \in V}w(v)=1$, and a page-capacity p.

• SOLUTION: A compact packing of T into pages of capacity p, i.e., a function $\tau : V \rightarrow Z^{+}$ such that $\vert\tau^{-1}(i)\vert = p$.

• MEASURE: The number of page faults of the packing, i.e., $\sum_{v \in V}c_{\tau}(v)w(v)$ where
  
  $$c_{\tau}(v)=\sum_{i=0}^{l(v)-1}\Delta_{\tau}(v_{i}),$$
  
  
  l(v) denotes the number of edges in the path from the root to v, $v_{i}$ denotes the ith node in this path, and $\Delta_{\tau}(v)$ 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.