Speaker: Francis Chin The University of Hong Kong (HKU)
Time: 2007-11-12 15:30-2007-11-12 16:50
Venue: FIT Building 4-603, Tsinghua University
Download: Click!

Abstract:

    Wireless communication has many applications since its invention more than a century ago. The frequency spectrum used for communication is a scarce resource and the Frequency Assignment Problem (FAP), aiming for better utilization of the frequencies, has been extensively studied in the past 20-30 years. Because of the rapid development of new wireless applications such as digital cellular network, cellular phone, the FAP problem has become more important. 
     In Frequency Division Multiplexing (FDM) networks, a geographic area is divided into small cellular regions or cells, usually regular hexagons in shape. Each cell contains one base station that communicates with other base stations via a high-speed wired network. Calls between any two clients (even within the same cell) must be established through base stations. When a call arrives, the nearest base station must assign a frequency from the available spectrum to the call without causing any interference with other calls. Interference may occur, which distorts the radio signals, when the same frequency is assigned to two different calls emanating from cells that are geographically close to each other. Thus the FAP problem can be viewed as a problem of multi-coloring a hexagon graph with the minimum number of colors when each vertex of the graph is associated with an integer that represents the number of calls in a cell.
     FAP has attracted more attention recently because of the following:
     Online analysis techniques: FAP problem is known to be NP-complete and many approximation algorithms have been proposed in the past. As frequency assignments have to be done without knowledge of future call requests and releases, online algorithms have been proposed and competitive analysis has been used to measure their performance.
     New technology and application: Wideband Code-Division Multiple-Access (W-CDMA) technology is a new technology used for the implementation of 3G cellular system. Orthogonal Variable Spreading Factor (OVSF) codes are used to satisfy requests with different data rate requirements. FAP with OVSF code trees representing the frequency spectrum becomes an important problem.

Short Bio:

    Professor Chin received the B.A.Sc. degree from the University of Toronto, Canada, in 1972, and the M.S., M.A. and Ph.D. degrees from Princeton University, in 1974, 1975, and 1976, respectively. Since 1975, he has taught at the University of Maryland, Baltimore County, University of California, San Diego, University of Alberta, Chinese University of Hong Kong, and University of Texas at Dallas. He joined the University of Hong Kong (HKU) in 1985, where he is the Chair of the Department of Computer Science and was the founding Head of the department from its establishment until December 31, 1999. Between 1992-1996, he served as the Associated Dean of Graduate School. In 1996, Prof. Chin was elected to the grade of IEEE Fellow.      Professor Chin is currently serving as Manager Editor of the International Journal of Foundations of Computer Science and is also on the editorial boards of several journals. He has served on the program committees and as conference chairman of numerous international workshops and conferences. Professor Chin's research interests include design and analysis of algorithms, on-line algorithms, and bioinformatics.