THE COMPLEXITY OF THE MAXIMAL REQUESTS SATISFACTION PROBLEM IN MULTIPOINT COMMUNICATION
Abstract
A multipoint request is a group of collaborating nodes that wish to establish a communication for a certain duration of time. This need arises in parallel applications executed on processing elements connected either by specialized interconnection networks or over wide area networks (collective communication operations). Each individual request is satisfied by a given subtree connecting the participating nodes. We aim to maximize the number of requests that can be simultaneously satisfied. In this paper, we show that this problem is NP-complete and we propose for it an approximation algorithm provided that the number of requests using the same edge is bounded by a constant.
References
- Parallel Processing Letters 12(1), 31 (2002). Link, Google Scholar
- BIT 32(2), 180 (1992). Crossref, ISI, Google Scholar
- D. Cavendish, A. Fei, M. Gerla, and R. Ram, "On the construction of low cost multicast trees with bandwidth reservation", In the proceedings of the High Performance Computing and Networking, 658–667, Amsterdam, NL, April 1998 . Google Scholar
- Journal of Algorithms 39(2), 223 (2001). Crossref, ISI, Google Scholar
- Journal of Parallel and Distributed Computing 24(1), 55 (1995). Crossref, ISI, Google Scholar
- Journal of Parallel and Distributed Computing 32(2), 173 (1996). Crossref, ISI, Google Scholar
- Parallel Computing 22(8), 991 (1996). Crossref, ISI, Google Scholar
-
M. R. Garey and D. S. Johnson , Computers and Intractability: A Guide to the Theory of NP-Completeness ( W.H. Freeman and Company , 1979 ) . Google Scholar - Journal of Graph Algorithms and Applications 4(1), 1 (2000). Crossref, Google Scholar
- Discrete Applied Mathematics 6, 243 (1983). Crossref, ISI, Google Scholar
- T. Hofmeister and H. Lefmann, "Approximating Maximum Independent Sets in Uniform Hypergraphs", Proc. of the 23rd Intl. Symp. Math. Found. of Comp. Sci. (MFCS), Lecture Notes in Computer Science, 1450:562-570, 1998 . Google Scholar
- A. Irlande, J.-C. König, and C. Laforest, "Construction of low-cost and low-diameter steiner trees for multipoint groups", Technical Report 39-1999, LaMI, Université d'Evry, November 1999 . Google Scholar
- Journal of Combinatorial Optimization 1(1), 47 (1997). Crossref, ISI, Google Scholar
- Discrete Mathematics and Theoretical Computer Science 4, 157 (2001). Google Scholar
-
C. H. Papadimitriou and K. Steiglitz , Combinatorial optimization: algorithms and complexity ( Prentice Hall , 1982 ) . Google Scholar - ACM Computing Surveys 29(2), 171 (1997). Crossref, ISI, Google Scholar
- T. Vorakosit and P. Uthayopas, "Generating an Efficient Dynamics Multicast Tree under Grid Environment", in Proceedings of the 10th European PVM/MPI User's Group Meeting, Venice, IT, Sept. 2003, Lecture Notes in Computer Science, 2840:636–643, 2003 . Google Scholar
- Computer Communications 27, 1389 (2004). Crossref, ISI, Google Scholar
- B. Y. Wu, G. Lancia, V. Bafna, K.-M. Chao, R. Ravi, and C. Y. Tan, "A polynomial time approximation scheme for minimum routing cost spanning trees", in the proceedings of the ACM Symposium On Discrete Algorithms, 21–32, San Francisco, CA, January 1998 . Google Scholar


