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.
Last update: August 16, 2004.