Capacitated Domination Problem

Speaker:	Professor D. T. LEE
		Institute of Information Science &
		Research Center for IT Innovation
		Academia Sinica
		Taiwan

Title:		"Capacitated Domination Problem"

Date:		Monday, 4 May, 2009

Time:		4:00pm - 5:00pm

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

Abstract:

We consider a generalization of the well-known domination problem on
graphs. The capacitated domination problem (CDP) with demand constraints
is to find a capacitated dominating multi-set D of minimum cardinality.
Consider a graph G=(V,E), in which each vertex has a demand and a
capacity. The capacity of a vertex specifies the maximum amount of service
that the vertex can deliver to meet the demands of all the vertices it
dominates, and the demand constraint of a vertex specifies that the demand
of the vertex can only be met by the vertices in D that dominate the
vertex. The CDP is said to be unsplittable, if the demand of each vertex
can be met by exactly one vertex in D, and splittable, otherwise.

In this talk, we investigate the capacitated domination problem on trees
and present a linear time algorithm for the unsplittable demand model, and
a pseudo-polynomial time algorithm for the splittable demand model. We
also show that the capacitated domination problem with splittable demand
constraints on trees is NP-complete, even for its integer version, and
provide a polynomial time approximation scheme.

This is a joint work with Mong-Jen Kao and Chung-Shou Liao, Dept. of
Computer Science and Information Engineering, National Taiwan University,
and the Institute of Information Science, Academia Sinica, Taiwan.

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

Dr. Lee has been with the Institute of Information Science, Academia
Sinica, Taiwan, where he is a Distinguished Research Fellow since July 1,
1998. Prior to joining the Institute of Information Science, he was a
Professor of the Department of Electrical Engineering and Computer
Science, Northwestern University, where he has worked since 1978. He spent
one year (August 1989 - August 1990) working as Program Director for
Computer & Computation Theory Program, Division of Computer & Computation
Research of the National Science Foundation and was Director of the
Institute of Information Science, Academia Sinica from 1998 to 2008.

Dr. Lee is also a Distinguished Research Chair Professor in the Dept. of
Computer Science and Information Engineering, and the Graduate Institute
of Electronics Engineering, National Taiwan University; Chair Professor of
National Taiwan University of Science and Technology, National Chiao-Tung
University and National Chung-Hsing University.  He serves as Executive
Director of the Taiwan Information Security Center (TWISC), Research
Center for Information Technology Innovation, Academia Sinica, Deputy
Program Director of the Taiwan e-Learning and Digital Archives Program
(TELDAP), and Chair of the International Collaboration for Advancing
Security Technology (iCAST), both sponsored by the National Science
Council, Taiwan.

His research interests include design and analysis of algorithms,
computational geometry, VLSI layout, web-based computing, algorithm
visualization, software security, bio-informatics, and digital libraries.

He has published over 150 technical articles in scientific journals and
conference proceedings. He is Editor of Algorithmica, ACM Journal on
Computing and Cultural Heritage, International J. of Information and
Computer Security, LNCS Transactions on Computational Science, Co-Chief
Editor of Int'l Journal of Computational Geometry & Applications, and
Series Editor of Lecture Notes Series on Computing for World Scientific
Publishing Co., Singapore.

Dr. Lee is Fellow of IEEE, Fellow of ACM, Member of the Academia Sinica,
recipient of Humboldt Research Award from the Alexander von Humboldt
Foundation, Germany in 2007 and elected Member of the Academy of Sciences
for the Developing World (TWAS) in 2008.