AF:Small:Optimization in surface-embedded graphs

点击翻译按钮获取中文摘要

This project aims to expand the boundaries of computational topology to include fundamental problems in combinatorial optimization, by developing efficient, practical, combinatorial algorithms to compute maximum flows, minimum cuts, and related structures in graphs embedded on topological surfaces. Preliminary results reveal intimate connections between the linear-programming duality between flows and cuts, the combinatorial duality between graph embeddings, the equivalence between flows in the primal graph and shortest-path distances in the dual graph, and Poincare-Lefschetz duality between (relative) homology and cohomology. These connections allow maximum flows to be computed in near-linear time in graphs of any fixed genus, by optimizing the relative homology class of the flow rather than directly optimizing the flow itself. However, the running time of these algorithms depends exponentially on the genus of the surface; a major goal of the project is to bring this dependence down to a small polynomial.The project aims to advance knowledge and understanding across multiple research areas, by developing novel connections between fundamental techniques in combinatorial and algebraic topology, algorithm design, and combinatorial optimization. This research will lead to faster algorithms for several basic optimization problems, develop new applications of topological methods, and potentially settle several long-standing open algorithmic questions. The project will support two PhD students at the beginning of their graduate careers. A broader goal of the research is to strengthen ties between the computer science and mathematics research communities; results will be disseminated broadly in venues visible to both communities.