Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem

ABSTRACT

(MATH) Consider a synchronous network of processors, modeled by directed or undirected graph G = (V,E), in which on each round every processor is allowed to choose one of its neighbors and to send him a message. Given a processor s &egr; V, and a subset T ⊆ V of processors, the telephone multicast problem requires to compute the shortest schedule (in terms of the number of rounds) that delivers a message from s to all the processors of T. The particular case T = V is called telephone broadcast problem.These problems have multiple applications in distributed computing. Several approximation algorithms with polylogarithmic ratio, including one with logarithmic ratio, for the undirected variants of these problems are known. However, all these algorithms involve solving large linear programs. Devising a polylogarithmic approximation algorithm for the directed variants of these problems is anopen problem, posed in [15].We devise a combinatorial logarithmic approximation algorithm for these problems, that applies also for the directed broadcast problem. Our algorithm has significantly smaller running time, and seems to reveal more information about the combinatorial structure of the solution, than the previous algorithms, that are based on linear programming.(MATH) We also improve the lower bounds on the approximation threshold of these problems. Both problems are known to be 3/2-inapproximable. For the undirected (resp., directed) broadcast problem we show that it is NP-hard (resp., impossible unless $NP ⊇ DTIME(n^{O(log n)})) to approximate it within a ratio of 3 —&egr; for any &egr; ρ 0 (resp., ω(\sqrt log n)).Finally, we study the radio broadcast problem. Its setting is similar to the telephone broadcast problem, but in every round every processor may either send a message to all its neighbors or may not send it at all. A processor is informed in a certain round if and only if it receives a message from precisely one neighbor.(MATH) This problem was known to admit O(log² n)-approximation algorithm, but no hardness of approximation was known. In this paper we show that the problem is ω(log n)-inapproximable unless NP ⊆ BPTIME(n^{log log n}}).

REFERENCES

• 1: Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
• 2: R. Bar-Yehuda. Private communication.
• 3: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in radio networks: an exponential gap between determinism randomization, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.98-108, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41849]
• 4: Avrim Blum , David Karger, An Õ(n3/14)-coloring algorithm for 3-colorable graphs, Information Processing Letters, v.61 n.1, p.49-53, Jan. 14, 1997 [doi>10.1016/S0020-0190(96)00190-1]
• 5: Amotz Bar-Noy , Sudipto Guha , Joseph (Seffi) Naor , Baruch Schieber, Multicasting in heterogeneous networks, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.448-453, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276857]
• 6: Yevgeniy Dodis , Sanjeev Khanna, Design networks with bounded pairwise distance, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.750-759, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301447]
• 7: Pierre Fraigniaud, Approximation Algorithms for Minimum-Time Broadcast under the Vertex-Disjoint Paths Mode, Proceedings of the 9th Annual European Symposium on Algorithms, p.440-451, August 28-31, 2001
• 8: Iris Gaber , Yishay Mansour, Broadcast in radio networks, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.577-585, January 22-24, 1995, San Francisco, California, United States
• 9: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 10: Edited by Dorit S. Hochbaum. Approximation Algorithms for NP-Hard Problems PWS Publishing Company, Boston, MA, 1995.
• 11: S. Hedetniemi, S. Hedetniemi, A. Liestman. A survey of broadcasting and gossiping in communication networks. Networks, 18: 319--349, 1988.
• 12: Guy Kortsarz, On the Hardness of Approximation Spanners, Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, p.135-146, July 18-19, 1998
• 13: Guy Kortsarz , David Peleg, Approximation Algorithms for Minimum-Time Broadcast, SIAM Journal on Discrete Mathematics, v.8 n.3, p.401-427, Aug. 1995 [doi>10.1137/S0895480193245923]
• 14: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
• 15: R. Ravi. Rapid rumor ramification: Approximating the minimum broadcast time. Proc. of the IEEE Symp. on Foundations of Computer Science (FOCS '94), 202--213, 1994.
• 16: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 17: Christian Schindelhauer, On the inapproximability of broadcasting time, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, p.226-237, September 05-08, 2000

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Experimentation, Performance, Theory