日時: 2015年12月9日(水) 14:00–15:00
場所：東京大学工学部14号館5階534号室
http://www.u-tokyo.ac.jp/campusmap/cam01_04_15_j.html
講演者: S. Thomas McCormick (University of British Columnbia)
題目: Weighted Abstract Flow: Structure and Algorithms
(joint work with Maren Martens, Jannik Matuschke, and Britta Peis)
Abstract:
In 1974 Alan Hoffman proposed an abstract model generalizing max
flow/min cut, and min-cost flow. We call his model Weighted Abstract
Flow (WAF). Hoffman left as an open problem whether there is a
combinatorial algorithm for WAF. In a 2008 IPCO paper, Marens and
McCormick proposed such an algorithm, but many details were incomplete.
We recently filled in all those details, and we present some of them
here. We also review other recent work on WAF, including applications
to flows over time, and a generalization of a result of
Gallo-Grigoriadis-Tarjan (GGT) on parametric min cuts to parametric WAF.