| Title: | Fake It Till You Make It: Circuits of Pseudoflow Polyhedra |
| Speaker: | Angela Morrison Mrs. Mathematical and Statistical Sciences University of Colorado Denver Denver, Colorado |
| Abstract: | There is a wealth of combinatorial algorithms for classical min-cost flow problems and their simpler variants like max flow or shortest-path problems. It is well-known that several of these algorithms are intimately related to the Simplex method and the more general circuit augmentation schemes. Prime examples are the network Simplex method, a refinement of the primal Simplex method, and (min-mean) cycle canceling, which corresponds to a (steepest-descent) circuit augmentation scheme over the underlying polyhedron. We are interested in deepening and expanding the understanding of the close relationship between circuit augmentation and combinatorial network flows algorithms. To this end, we generalize from the consideration of primal or dual feasible flows to the so-called pseudoflows, which allow for a violation of flow balance. We introduce what are called 'pseudoflow polyhedra', in which slack variables are used to quantify this violation, and characterize their circuits. This enables us to study various network flows algorithms in view of the walks that they trace in these polyhedra, and in view of the pivot rules used to choose the steps. |
| Location: | Palenske 227 |
| Date: | 3/21/2024 |
| Time: | 3:30 PM |
@abstract{MCS:Colloquium:AngelaMorrison:2024:3:21,
author = "{Angela Morrison}",
title = "{Fake It Till You Make It: Circuits of Pseudoflow Polyhedra}",
address = "{Albion College Mathematics and Computer Science Colloquium}",
month = "{21 March}",
year = "{2024}"
}