********************************************************************

                                                     Seminar

             Department of Systems Engineering and Engineering Management
The Chinese University of Hong Kong

------------------------------------------------------------------------------------------

Title	:	Stochastic Maximum Weight Forest Problem
Speaker	:	Prof. Abdel Lisser
		Department of Computer Science
		University of Paris Sud
Date	:	July 20th, 2011 (Wednesday)
Time	:	4:30 p.m. - 5:30 p.m.
Venue	:	Room 513
		William M.W. Mong Engineering Building
		(Engineering Building Complex Phase 2)
		CUHK

------------------------------------------------------------------------------------------

Abstract:
　

The maximum weight forest problem (MWFP) in a graph is solved by the famous greedy algorithm due to Edmonds (1971) where every edge has a known weight. In particular, the system of constraints on the set of edges is TDI (totally dual integral), since the set of independent edges, i.e., of acyclic subsets of edges, is a matroïd. We extend this approach to the case of two-stage maximum weight forest problems. The set of edges is
composed of first stage edges with known weights and second stage ones where the weights are known a priorily in terms of discrete random variables. As the probability distribution is discrete, we transform the stochastic problem into a deterministic equivalent problem. In this article, we prove TDIness for the two stage maximum weight forest problem in the following cases: Two scenarios with reduced number of first stage variables and we propose an efficient greedy algorithm for solving this problem. We provide a counter example to prove that the problem is not TDI for more than two scenarios.

-------------------------------------------------------------------------------------------

Biography:
　

After more than 10 years in France Telecom Research center, A.Lisser joined the University of Paris Sud as full Professor in the department of Computer Science. He graduated at the University of Paris Dauphine in 1987 and got the Habilitation thesis in computer science and operation research at the University of Paris Nord. His main research topics are combinatorial and stochastic optimization, semidefinite programming, netorwk design and power electric planning.

************************* ALL ARE WELCOME ************************

Host	:	Prof. Janny Leung
Tel	:	(852) 2609-8238
Email	:	janny@se.cuhk.edu.hk
Enquiries	:	Prof. Nan Chen or Prof. Sean X. Zhou
	:	Department of Systems Engineering and Engineering Management
		CUHK
Website	:	http://www.se.cuhk.edu.hk/~seem5201
Email	:	seem5201@se.cuhk.edu.hk

********************************************************************