1. Günter Rote and Andreas Vogel:

A heuristic for decomposing traffic matrices in TDMA satellite communication

ZOR — Methods and Models of Operations Research 38 (1993), 281–307, (Zbl 785.90069). doi:10.1007/BF01416610

2. Günter Rote and Andreas Vogel:

A heuristic for decomposing traffic matrices in TDMA satellite communication

Bericht 73-1990, Technische Universität Graz, 28 pages; (slightly extended version of 1.)

3. Günter Rote:

Eine Heuristik für ein Matrizenzerlegungsproblem, das in der Telekommunikation via Satelliten auftritt (Kurzfassung)

(Short and preliminary version of 1.)
ZAMM · Zeitschrift für angewandte Mathematik und Mechanik 69 (1989), T29–T31. doi:10.1002/zamm.19890690402

Abstract

With the time-division multiple access (TDMA) 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 we propose a heuristic based on a scaling technique which for each number of allowed matrices in the range from n to n2 allows to give a performance guarantee with respect to the total weight of the solution. As a subroutine we use new heuristics 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.

  pdf file (gzipped)
other papers about this subject
Last update: August 16, 2004.