AF:Small:Optimization in surface-embedded graphs

AF:Small:曲面嵌入图中的优化

• 批准号: 0915519
• 负责人: Jeff Erickson
• 金额: $ 50万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-01 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0915519&HistoricalAwards=false
• 关键词: AF; Small; Optimization; surface; embedded

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.

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