An efficient algorithm for the minimum cost min-max load terminal assignment problem

One of the main issues to be addressed in topological design of centralized networks is that of assigning terminals to concentrators in such a way that each terminal is assigned to one (and only one) concentrator and the total number of terminals assigned to any concentrator (which is referred to as load in this paper) does not overload that concentrator, i.e. is within the concentrator's capacity. Under these constraints, an assignment with the lowest possible cost is sought. An assignment of terminals to concentrators which minimizes the maximum load among the concentrators (which qualitatively represents congestion at some hot spots in a network service area) is referred to as a min-max load assignment. In this paper, we consider the problem of finding a min-max load assignment with the-lowest cost. We call this problem the Minimum Cost Min-Max Load Terminal Assignment Problem (MCMLTAP). We present an algorithm for MCMLTAP and prove that the problem is optimally solvable in polynomial time using our proposed algorithm.