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


                                                     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

 

 

 

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