On Power-Efficient Wireless Broadcasting and Multicasting

Speaker:        Dr. Siu Wing CHENG
                Department of Computer Science
                Hong Kong University of Science & Technology

Title:          "On Power-Efficient Wireless Broadcasting and
                Multicasting"

Date:           Monday, 27 October 2003

Time:           4:00 pm - 5:00 pm

Venue:          Lecture Theatre F
                (Leung Yat Sing Lecture Theatre, near lift nos. 25/26)
                HKUST

Abstract:

We present some recent algorithmic results, by us and others, on
power-efficient broadcasting and multicasting in a wireless network of
stationary nodes. It turns out that there are close connections to some
well-known combinatorial optimization problems, including set cover,
steiner tree, and node weighted Steiner tree.  For example, one can

    - approximate the power-optimal multicast tree to within
      a constant factor in an obstacle-free environment, and
    - approximate the power-optimal broadcast tree to within
      a logarithmic factor in the presence of obstacles.

We also present some experimental results on the above two algorithms.
The above two algorithms and the experimental results are joint work with
Xiaohua Jia, Frankie Hung, and Yajun Wang.



*********************
Biography:


Dr Cheng received his BSc degree (First Class Honours) in Computer
Studies in 1987 from the University of Hong Kong and his PhD degree
in Computer Science in 1992 from the University of Minnesota.
Currently, he is an associate professor of the Department of
Computer Science at HKUST.  His research interests include
computational geometry, algorithms, and data structures.