Seminars: A. Berezin, I. A. Vakula, S. Leonova, Paths of maximal weight in some special vertex-weighted oriented graphs

SEMINARS


Seminar for Optimization Laboratory May 16, 2014 11:00, Ekaterinburg, Sophya Kovalevskaya street 16, Big Hall, 3 floor, Krasovsky Institute of Mathematics and Mechanics Ural Branch of RAS

Paths of maximal weight in some special vertex-weighted oriented graphs A. Berezin, I. A. Vakula, S. Leonova Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg
Abstract: A maximal weighted path problem is considered on special vertex weighted oriented graphs. This setting and respective graphs are related to rolling planning problem for hot and cold rolling mills. Based on specifics of these graphs we give an $O(n^3)$-time approximation algorithm for this NP-hard problem. Directions are given for further investigation and applications of our results.