Dokt-seminar-l December 2017

dokt-seminar-l@kam.mff.cuni.cz

2 participants
2 discussions

no seminar tomorrow
by Robert Samal 20 Dec '17

20 Dec '17

Dear all, our planned speaker for tomorrow is ill, so tomorrow's seminar is canceled. (There is an interesting noon seminar planned, though, highly recommended!) Enjoy your holiday, R -- Robert Šámal IÚUK MFF UK -- CSI of Charles University in Prague

1 0

Doct. seminar 7. 12.: A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization
by Martin Böhm 06 Dec '17

06 Dec '17

Dear colleagues, let me invite you to the next session of our doctoral seminar that will take place tomorrow (7. 12.) at 9:50 in S6. I will present a paper by Neil Olver and Laszló Végh titled A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization. ( https://arxiv.org/abs/1611.01778 ) The paper presents a new strongly polynomial algorithm for generalized flow maximization. In generalized flow maximization, there are additional gain factors on edges, so that flow can actually multiplicatively change when going through an edge. Solving generalized flows in strongly polynomial time is an important progress towards showing that general LPs have strongly polynomial algorithms; this is due to the fact that we can use generalized flows to find a feasible solution to an LP of the form Ax=b, x>=0 with A having two arbritrary non-zero entries per column. The first strongly polynomial algorithm was given by Végh in 2016; the algorithm we will see is a substantial simplification of the first algorithm. The new algorithm also improves qualitatively on the previous one, with a running time bound of O( (m+n log n) mn log(n^2/m) ). --- Only basic knowledge of maximum flows will be assumed; everyone is welcome. Last but not least, I'll bring some tea, fruit and cookies at 9:45, so come in on time to get a mini-breakfast! See you all there, Martin Böhm

1 0

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

Dokt-seminar-l December 2017