  Input to the Load Balanced Demand Distribution (LBDD) consists of the
following: (a) a set of service centers; (b) a set of demand nodes and; (c) a
cost matrix containing the cost of assignment for each (demand node, service
center) pair. In addition, each service center is also associated with a notion
of capacity and a penalty which is incurred if it gets overloaded. Given the
input, the LBDD problem determines a mapping from the set of n demand vertices
to the set of k service centers, n being much larger than k. The objective is
to determine a mapping that minimizes the sum of the following two terms: (i)
the total cost between demand units and their allotted service centers and,
(ii) total penalties incurred. The problem of LBDD has a variety of
applications. An instance of the LBDD problem can be reduced to an instance of
the min-cost bi-partite matching problem. The best known algorithm for min-cost
matching in an unbalanced bipartite graph yields a complexity of O($n^3k$).
This paper proposes novel allotment subspace re-adjustment based approach which
allows us to characterize the optimality of the mapping without invoking
matching or mincost flow. This approach yields an optimal solution with time
complexity $O(nk^3 +nk^2 log n)$, and also allows us to efficiently maintain an
optimal allotment under insertions and deletions.
