Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Integer Optimization And Computational Algebraic Topology, Bala Krishnamoorthy
Integer Optimization And Computational Algebraic Topology, Bala Krishnamoorthy
Systems Science Friday Noon Seminar Series
We present recently discovered connections between integer optimization, or integer programming (IP), and homology. Under reasonable assumptions, these results lead to efficient solutions of several otherwise hard-to-solve problems from computational topology and geometric analysis. The main result equates the total unimodularity of the boundary matrix of a simplicial complex to an algebraic topological condition on the complex (absence of relative torsion), which is often satisfied in real-life applications . When the boundary matrix is totally unimodular, the problem of finding the shortest chain homologous under Z (ring of integers) to a given chain, which is inherently an integer program, can …