An Algebraic Approach to Network Optimization

Algebra Seminar
Monday, November 11, 2013 - 16:00
1 hour (actually 50 minutes)
Skiles 005
University of Pennsylvania

This talk assumes no familiarity with directed topology, flow-cut dualities, or sheaf (co)homology.  

Flow-cut dualities in network optimization bear a resemblance to topological dualities.  Flows are homological in nature, cuts are cohomological in nature, constraints are sheaf-theoretic in nature, and the duality between max flow-values and min cut-values (MFMC) resembles a Poincare Duality.  In this talk, we formalize that resemblance by generalizing Abelian sheaf (co)homology for sheaves of semimodules on directed spaces (e.g. directed graphs).  Such directed (co)homology theories generalize constrained flows, characterize cuts, and lift MFMC dualities to a directed Poincare Duality.  In the process, we can relate the tractability and decomposability of generalized flows to local and global flatness conditions on the sheaf, extending previous work on monoid-valued flows in the literature [Freize].