BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Angela Morrison (UBCO-hosted) (University of Colorado - Denver) DTSTART:20230216T233000Z DTEND:20230217T003000Z DTSTAMP:20260513T201715Z UID:SFUOR/14 DESCRIPTION:Title: O n Combinatorial Algorithms and Circuit Augmentation for Pseudoflows\nb y Angela Morrison (UBCO-hosted) (University of Colorado - Denver) as part of PIMS-CORDS SFU Operations Research Seminar\n\nLecture held in ASB 10908 .\n\nAbstract\nThere is a wealth of combinatorial algorithms for classical min-cost flow\nproblems and their simpler variants like max flow or short est-path problems. It is wellknown\nthat several of these algorithms are i ntimately related to the Simplex method\nand the more general circuit augm entation schemes. Prime examples are the network\nSimplex method\, a refin ement of the primal Simplex method\, and (min-mean) cycle\ncanceling\, whi ch corresponds to a (steepest-descent) circuit augmentation scheme over\nt he underlying polyhedron.\n\nWe are interested in deepening and expanding the understanding of the close relationship\nbetween circuit augmentation and combinatorial network flows algorithms. To this end\,\nwe generalize f rom the consideration of primal or dual feasible flows to the so-called\np seudoflows\, which allow for a violation of flow balance. We introduce wha t are called\n‘pseudoflow polyhedra’\, in which slack variables are us ed to quantify this violation\, and\ncharacterize their circuits. This ena bles us to study various network flows algorithms in\nview of the walks th at they trace in these polyhedra\, and in view of the pivot rules used\nto choose the steps.\n\nIn particular\, we show that the Successive Shortest Path Algorithm and the Shortest/\nGeneric Augmenting Path Algorithm form general\, non-edge circuit walks. We also\nprovide a proof outline showing that the aforementioned algorithms correspond to a\nDantzig Rule and Stee pest-ascent circuit augmentation scheme respectively.\n LOCATION:https://researchseminars.org/talk/SFUOR/14/ END:VEVENT END:VCALENDAR