Some new results for combinatorial problems with risk functions and controllable data - Evgeny Gurevsky (LS2N, Université de Nantes)

The presentation deals with recently introduced optimization problems of risk management under limited resources and studied within the framework of routing and network design applications.
Earlier publications explore the following three problem versions: total risk minimization (or min-sum risk), maximum risk minimization (or min-max risk) and constrained risk.They have been proven to be either polynomially or pseudo-polynomially solvable.

 

Our main contribution consists in extending and improving the results obtained previously.
Namely, we show that the considered problems are also polynomially (resp. pseudo-polynomially)
solvable for a larger class of risk functions. And finally, we suggest an original resolution approach
that outperforms, in terms of running time, the algorithms developed before.

(Joint work with Pr. Mikhail Y. Kovalyov from UIIP, NASB, Belarus)