With the time-division multiple access technique in satellite communication the problem arises to decompose a given n×n traffic matrix into a weighted sum of a small number of permutation matrices such that the sum of the weights becomes minimal. There are polynomial algorithms when the number of permutation matrices in a decomposition is allowed to be as large as n2. When the number of matrices is restricted to n, the problem is NP-hard. In this paper the authors propose a heuristic based on a scaling technique which for each number of allowed matrices in the range from n to n’2 allows to give a performance guarantee with respect to the total weight of the solution. As a subroutine they use new heuristic methods for decomposing a matrix of small integers into as few matrices as possible without exceeding the lower bound on the total weight. Computational results indicate that the method might also be practical.
