Optimal Load Balanced Demand Distribution under Overload Penalties

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.