Combinatorial Problems in Network Broadcasting

Speaker:	Lap Chi Lau
		Department of Computer Science
		University of Toronto

Title:		"Combinatorial Problems in Network Broadcasting"

Date:		Monday, 17 October 2005

Time:		4:00pm - 5:00pm

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

Abstract:

Sending data through a network is a task that is indispensable in our
modern lives.  Initiated by the seminal work of Ahlswede, Cai, Li and
Yeung, the area of network coding has received a great deal of attention
in recent years, as it provides a new perspective on the data transmission
problems in computer networks, and a new source of fundamental and
exciting open problems.  In this talk we focus on a special case known as
the network broadcasting problem in undirected networks, where a sender
must send all its data to a set of receivers and the objective is to
maximize the transmission rate subject to the capacity constraints in the
network. The following questions come up naturally.

(1) 	How to compute the maximum broadcasting rate if network coding
	is used?

(2) 	How to compute the maximum broadcasting rate if network coding is
	not used?

(3) 	How big could the coding advantage be?

We model the first two questions as purely combinatorial problems, namely
the "graph rooted-orientation" problem and the "Steiner tree packing"
problem; both are generalizations of fundamental problems in graph theory.
Then we show the hardness of both problems and present efficient
approximation algorithms using techniques in combinatorial optimization.
As a consequence, a non-trivial upper bound on the third question is
obtained.  Finally, we conclude with a discussion of open problems, future
directions, and the intriguing relations with other long standing open
combinatorial problems.


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

Lap Chi Lau is a fifth year graduate student in the Department of Computer
Science at the University of Toronto, under the supervision of Professor
Michael Molloy.  He got a M.Sc. in the same department with Professor
Derek Corneil.  Previously he received a B.Sc. from the Chinese University
of Hong Kong, and was a research assistant of Professor Leizhen Cai and
Professor John C.S. Lui.

His current research lies mostly in theoretical computer science,
particularly on discrete combinatorial problems and approximation
algorithms. For his work on Steiner tree packing, he received the Machtey
award for the best student paper in the IEEE conference FOCS 2004. He is a
recipient of the Microsoft Fellowship for 2005-2007, and was an intern in
the Microsoft Research Theory Group under the mentorship of Dr. Kamal Jain
in the summers of 2004 and 2005.  He was also a research visitor in the
Egervary Research Group at Eotvos University in Budapest under the
supervision of Professor Andras Frank in the winter of 2004.