LOCATING THE MEDIAN OF A TREE IN REAL TIME
Abstract
Determining the optimal location of a switching center in a tree network of users is accurately modeled by the median problem. A real-time approach is used in this paper to investigate the dynamics of such a communication network in two cases: (1) a growing tree of nodes associated with equal demand rates, and (2) a stream of corrections that arbitrarily change the demand rates at the nodes. The worst-case analysis performed in both situations clearly demonstrates the importance of parallelism in such real-time paradigms. It is shown that the error generated by the best sequential algorithm in the first case can be arbitrarily large. A synergistic behavior is revealed when the quality-up is investigated in the second case.
References
- Journal of Algorithms 10, 287 (1989), DOI: 10.1016/0196-6774(89)90017-5. Crossref, ISI, Google Scholar
S. G. Akl , Nonlinearity, maximization and parallel real-time computation, Proceedings of the Twelfth Conference on Parallel and Distributed Computing and Systems (2000) pp. 31–36. Google Scholar- Computing and Informatics 21(5), 455 (2002). ISI, Google Scholar
- The Journal of Supercomputing 29(1), 89 (2004), DOI: 10.1023/B:SUPE.0000022574.59906.20. Crossref, ISI, Google Scholar
- Parallel Processing Letters 9, 499 (1999), DOI: 10.1142/S0129626499000463. Link, Google Scholar
S. G. Akl and S. D. Bruda , Parallel real-time cryptography: Beyond speedup II, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (2000) pp. 1283–1289. Google Scholar- International Journal of Computers and their Applications, Special Issue on High Performance Computing Systems 7, 31 (2000). ISI, Google Scholar
- The Journal of Supercomputing 19, 219 (2001), DOI: 10.1023/A:1011179823237. ISI, Google Scholar
S. D. Bruda and S. G. Akl , On the data-accumulating paradigm, Proceedings of the Fourth International Conference on Computer Science and Informatics (1998) pp. 150–153. Google Scholar- Theory of Computing Systems 33, 85 (2000), DOI: 10.1007/s002249910005. Crossref, ISI, Google Scholar
- Journal of Parallel and Distributed Computing 61, 688 (2001), DOI: 10.1006/jpdc.2000.1707. Crossref, ISI, Google Scholar
H. Gazit , G. L. Miller and S.-H. Teng , Optimal tree contraction in an EREW model, Proceedings of the 1987 Princeton Workshop on Algorithm, Architecture and Technology Issues for Models of Concurrent Computation (1987) pp. 139–156. Google Scholar- Transportation Science 5, 212 (1971), DOI: 10.1287/trsc.5.2.212. Crossref, Google Scholar
- Operations Research 12, 450 (1964), DOI: 10.1287/opre.12.3.450. Crossref, ISI, Google Scholar
-
G. Y. Handler and P. Mirchandani , Location on Networks: Theory and Algorithms ( MIT Press , Cambridge, Massachusetts , 1979 ) . Google Scholar S. R. Kosaraju and A. L. Delcher , Optimal parallel evaluation of tree-structured computation by raking, Proceedings of the Third Aegean Workshop on Computing (1988) pp. 101–110. Google Scholar- Management Science 29, 482 (1983), DOI: 10.1287/mnsc.29.4.482. Crossref, ISI, Google Scholar


