Time-slot assignment for TDMA-systems (Q2265947)

In satellite communication as in other technical systems using the TDMA- technique (time division multiple access) the problem arises to decompose a given (n\(\times n)\)-matrix in a weighted sum of permutation matrices such that the sum of the weights becomes minimal. We show at first that an optimal solution of this problem can be obtained in \(O(n^ 4)\)-time using at most \(O(n^ 2)\) different permutation matrices. Thereafter we discuss shortly the decomposition in O(n) different matrices which turns out to be NP-hard. Moreover it is shown that an optimal decomposition using a class of 2n permutation matrices which are fixed in advance can be obtained by solving a classical assignment problem. This latter problem can be generalized by taking arbitrary Boolean matrices. The corresponding decomposition problem can be transformed to a special max flow min cost network flow problem, and is thus soluble by a genuinely polynomial algorithm.