separating hyperplanes, memory allocation

QR say that for a given schedule, the projective memory allocation method gives the minimal amount of memory required.
--
What can we do with the separating hyperplanes to minimize the amount of residual memory?
--
The general approach to solve the ZC detection problem: Compute a separating hyperplane called a certificate (using a LP in the case of KMW, KS, DV-KMW or a faster way as in CM-Z) and use the certificate to partition, or decompose, the graph. CM-Z say that the depth of the decomposition tree is bounded by the dimensions of the weights. Should it be n? no. It should be min(n,d).
--
More about QR memory allocation: Darte and others have also proposed a memory allocation algorithm. Their paper, DSV-LM has a nice overview of QR.
--
To do: QR has a nice overview of the scheduling problem in general. Read it.