{menu secondaire item-03}

Résumé Séminaire -- LISSER

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., acyclic
subsets of edges, is a matroïd. We extend this approach to the case of
two-stage stochastic maximum weight forest problem. The set of edges is
composed of first stage edges with known weights and second stage edges
where the weights are random variables with discrete distribution. In
this case, we transform the stochastic problem into a deterministic
equivalent problem. In this talk, we prove TDIness for the two stage
maximum weight forest problem in the case of two scenarios. We provide
a counter example to prove that the problem is not TDI for more than
two scenarios.