The Effect of a Capacity Constraint on the Minimal Cost of a Partition

Abstract

A recent paper by Chandra and Wong considered the problem of finding a partition of nonnegatlve numbers into m groups to minimize a certain cost, the sum of the squares of the group sums. One apphcatlon of thin problem is m allocation of data records to disks to minimize arm contention, under certain assumptions about record accessing behavior In the paper by Chandra and Wong it was assumed that the dmk capacltms were so large that capacity constraints could be ignored Consideration of the effect of such constraints, assuming equal-razed data records and equalsized dmks, leads to the problem of partitioning numbers (which represent access probabihtles) into m groups of at most k numbers each A practical method for partltmmng is shown to ymld a cost no more than of the minimal cost without the constraint on group size (Cases are constructed that approach this limit asymptotically ) Therefore, within the context of the model, increasing the disk capacity (keeping the number of arms fixed) and arbitrarily changing the partitmn cannot reduce the arm contention cost below 75 percent of that achieved on the existing system with the suggested partition The result also shows that the proposed partition has a cost for the constrained problem at most of the minimal cost for the constrained problem However, the exact worst-case performance is not yet known except in the case when the group size is 2. In that case, the proposed partition is actually optimal. © 1975, ACM. All rights reserved.