An Extended Model for the Optimal Sizing of Records

In previous work, Erickson and Luss examined the problem of optimally sizing computer records so as to minimize wasted space. They assumed that a fixed number of record sizes can be used to store messages of various lengths. If a message cannot be stored in any single record, it is stored in multiple records of the same size. However, the record size used to accommodate divided messages is not used to store any message that fits into any of the other record sizes. Here, we relax the latter constraint and allow the record size designated to store divided messages to store also other messages. A dynamic programming algorithm that finds the optimal record sizes is presented. However, since the computational effort needed to find the optimal record sizes is large, we also derive bounds for the optimal solution and give a heuristic algorithm that provides near optimal solutions.