A program can benefit from improved cache block utilization when contemporaneously accessed data elements are placed in the same memory block. This can reduce the program’s memory block working set and thereby, reduce the capacity miss rate. We formally define the problem of data packing for an arbitrary cache size and packing factor (the number of elements fitting in a cache block) and study how well the optimal solution can be approximated for two dual problems. On the one hand, we show that the cache hit maximization problem is approximable within a constant factor, for every fixed cache size. On the other hand, we show that unless P = NP, the cache miss minimization problem cannot be efficiently approximated.