Abstract
In satellite communication as in other technical systems using the TDMA-technique (time division multiple access) the problem arises to decompose a given (n×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 inO(n 4)-time using at mostO(n 2) different permutation matrices. Thereafter we discuss shortly the decomposition inO(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.
Zusammenfassung
Bei der Nachrichtenübertragung via Satelliten unter Benützung der TDMA-Technik, wie auch bei mannigfachen anderen technischen Systemen, tritt das Problem auf, daß eine gegebene (n×n)-Matrix mit nichtnegativen Elementen derart in eine Summe von Permutationsmatrizen zu zerlegen ist, daß die Summe der Gewichte minimal wird. Zunächst wird gezeigt, daß eine Optimallösung dieses Problems inO(n 4) Schritten konstruiert werden kann. Dabei werden maximaln 2−2n+2 verschiedene Permutationsmatrizen verwendet. Danach wird kurz die Zerlegung inn Matrizen diskutiert. Dieses Problem ist NP-schwer. Wenn 2n Permutationsmatrizen im vorhinein fixiert werden, kann eine optimale Zerlegung in eine gewichtete Summe dieser Permutationsmatrizen inO(n 3) Zeit durch das Lösen eines linearen Zuordnungsproblems gefunden werden. Dieses letztere Problem kann auf beliebige Boolesche Matrizen verallgemeinert werden. Dies führt dann auf ein maximales Flußproblem mit minimalen Kosten und kann daher ebenfalls durch einen echt-poynomialen Algorithmus gelöst werden.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Balas, E., Landweer, P. R.: Traffic assignment in communication satellites. OR Letters2, 141–147 (1983).
Birkhoff, G.: Tres observaciones sobre el algebra lineal. Rev. univ. nac. Tucumán (Ser. A)5, 147–151 (1940).
Frieze, A. M.: Complexity of a 3-dimensional assignment problem. European Journal of Operations Research13, 161–164 (1983).
Garey, M. K., Johnson, D. S.: Computers and intractability: A guide to the theory of NP-completeness. San Francisco: Freeman 1979.
Heller, I., Tompkins, C. B.: An extension of a theorem of Dantzig. In: Linear Inequalities and Related Systems (Kuhn, H. W., Tucker, A. W., eds.), pp. 247–254, Princeton: Princeton Univ. Press 1958.
Inukai, T.: An efficient SS/TDMA time slot assignment algorithm. IEEE Transactions on CommunicationsCOM-27, 1449–1455 (1979).
Lewandowski, J. L., Liu, J. W. S., Liu, C. L.: SS/TDMA time slot assignment with restricted switching modes. IEEE Transactions on CommunicationsCOM-31, 149–154 (1983).
Rendl, F.: On the complexity of decomposing matrices arising in satellite communications. OR Letters4, 5–8 (1985).
Rothe, G.: Private Communication (1984).
Tardos, E.: A strongly polynomial minimum cost circulation algorithm. Bericht 84356 — OR, Institut für Operations Research, Universität Bonn; to appear in: Combinatorica, May 1985.
Author information
Authors and Affiliations
Additional information
This work was partially supported by the Austrian Science Foundation (Fonds zur Förderung der wissenschaftlichen Forschung), Project S 32/01.
Rights and permissions
About this article
Cite this article
Burkard, R.E. Time-slot assignment for TDMA-systems. Computing 35, 99–112 (1985). https://doi.org/10.1007/BF02260498
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02260498