AF:Small:Optimization in surface-embedded graphs

该项目旨在通过开发高效、实用的组合算法来计算嵌入在拓扑表面上的图中的最大流量、最小切割和相关结构，从而扩展计算拓扑的边界，包括组合优化中的基本问题。初步结果揭示了流与切之间的线性规划对偶性、图嵌入之间的组合对偶性、原始图中流与对偶图中最短路径距离之间的等价性以及（相对）同调与上同调之间的Poincare-Lefschetz对偶性之间的密切联系。通过优化流的相对同源类，而不是直接优化流本身，这些连接允许在任何固定属图的近线性时间内计算出最大流量。然而，这些算法的运行时间指数依赖于曲面的属；该项目的一个主要目标是将这种依赖性降低到一个小多项式。该项目旨在通过开发组合和代数拓扑、算法设计和组合优化等基本技术之间的新联系，促进多个研究领域的知识和理解。这项研究将为一些基本优化问题带来更快的算法，开发拓扑方法的新应用，并有可能解决几个长期存在的开放性算法问题。该项目将支持两名刚开始研究生生涯的博士生。这项研究的一个更广泛的目标是加强计算机科学和数学研究界之间的联系；结果将在两族都能看到的场所广泛传播。

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.