AF: SMALL: Topics in Bridging Continuous and Discrete Optimization

AF：SMALL：桥接连续优化和离散优化的主题

• 批准号: 2007009
• 负责人: David Williamson
• 金额: $ 42.97万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-08-01 至 2024-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007009&HistoricalAwards=false
• 关键词: AF; SMALL; Topics; Bridging; Continuous

One well-known result in discrete mathematics is that the countries for any map can be given one of four colors so that any two countries sharing a border will have different colors. In mathematics, this result is usually stated as saying that any planar graph is four-colorable. The proofs of this result that are known involve checking hundreds of individual cases; the first proof of this result (given in 1976) was one of the first well-known mathematical proofs to involve computers in doing the checking. This project attempts a different route to obtain this proof, one that involves using the optimization of continuous functions to obtain a result that at first glance appears not to involve continuous quantities at all (since in the end one only wants to use one of four colors per country). The goal is to eliminate all the case-checking that went into the original proof. Such a proof would give further confidence to mathematicians that the original proofs did not miss any important cases. The project includes other problems that have this flavor of using continuous optimization to obtain results in optimizing discrete quantities. These include other results in trying to minimize the number of colors used in coloring general (non-planar) graphs, and finding practical algorithms to solve certain types of linear systems of equations. The research will be used as a means of outreach to undergraduates, and involve them in their project. In particular, this project explores several new directions for progress on the interface of discrete and continuous optimization. The first returns to the technique of using semidefinite programming, an extension of linear programming, over the complex numbers to break through a nearly 20-year old barrier in coloring 3-colorable graphs. The second considers finding a direct proof of the famous theorem about four-coloring planar graphs via semidefinite programming. The third considers an eigenvector-based approximation algorithm for the maximum-cut problem due to Trevisan and looks for possible improvements and extensions. The fourth looks at an algorithm for solving Laplacian systems of equations due to Kelner, Orrechia, Sidford, and Zhu, and considers possible directions that might make the algorithm competitive with current linear-system solvers. These directions include batching updates and looking at a dual version of the algorithm. The fifth and final direction looks at an early result in spectral graph theory due to Hoffman and Singleton, and considers whether one remaining open issue in that paper can be resolved.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

离散数学的一个众所周知的结果是，任何地图上的国家都可以指定四种颜色中的一种，这样共享边界的任何两个国家都会有不同的颜色。 在数学中，这个结果通常被表述为任何平面图都是四色的。 已知的这一结果的证明需要检查数百个个案；这个结果的第一个证明（1976 年给出）是最早使用计算机进行检查的著名数学证明之一。 该项目尝试了一种不同的途径来获得这个证明，其中涉及使用连续函数的优化来获得乍一看似乎根本不涉及连续量的结果（因为最终只想使用四种颜色中的一种）每个国家）。 目标是消除原始证明中的所有案例检查。 这样的证明将使数学家更加确信原始证明没有遗漏任何重要的情况。 该项目包括其他具有使用连续优化来获得优化离散量结果的问题。 其中包括尝试最小化一般（非平面）图形着色中使用的颜色数量以及寻找实用算法来求解某些类型的线性方程组的其他结果。 该研究将用作向本科生进行推广的一种手段，并让他们参与到他们的项目中。特别是，该项目探索了离散和连续优化接口进展的几个新方向。 第一个回到了在复数上使用半定规划（线性规划的扩展）的技术，以突破近 20 年来为 3 色图着色的障碍。 第二个考虑通过半定规划找到关于四色平面图的著名定理的直接证明。 第三个考虑基于 Trevisan 的最大割问题的基于特征向量的近似算法，并寻找可能的改进和扩展。 第四个研究了由 Kelner、Orrechia、Sidford 和 Zhu 提出的用于求解拉普拉斯方程组的算法，并考虑了可能使该算法与当前线性系统求解器竞争的可能方向。这些方向包括批量更新和查看算法的双版本。 第五个也是最后一个方向着眼于霍夫曼和辛格尔顿在谱图理论方面的早期成果，并考虑该论文中剩余的未决问题是否可以得到解决。该奖项反映了 NSF 的法定使命，并通过使用评估结果被认为值得支持。基金会的智力价值和更广泛的影响审查标准。

项目成果

An Experimental Evaluation of Semidefinite Programming and Spectral Algorithms for Max Cut

半定规划和最大割谱算法的实验评估

• DOI: 10.4230/lipics.sea.2022.19
• 发表时间: 2022-07
• 期刊: Leibniz international proceedings in informatics
• 作者: Mirka, Renee;Williamson, David P.
• 通讯作者: Williamson, David P.

Graph coloring and semidefinite rank

图着色和半定秩

• DOI: 10.1007/978-3-031-06901-7_29
• 发表时间: 2022-05
• 期刊: Lecture notes in computer science
• 作者: Mirka, Renee;Smedira, Devin;Williamson, David P.
• 通讯作者: Williamson, David P.

Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem in Graphs

重温 Garg 针对图中 k-MST 问题的 2 近似算法

• 发表时间: 2023-01
• 期刊: Proceedings of the 2023 Symposium on Simplicity in Algorithms
• 作者: Breen, Emmett;Mirka, Renee;Wang, Zichen;Williamson, David P.
• 通讯作者: Williamson, David P.

A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP

TSP 半积分循环割实例的 4/3 近似算法

• 发表时间: 2023-06
• 期刊: Lecture notes in computer science
• 作者: Jin, Billy;Klein, Nathan;Williamson, David P.
• 通讯作者: Williamson, David P.

A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Systems

求解拉普拉斯系统的组合切换切换算法

• 发表时间: 2023-01
• 期刊: Leibniz international proceedings in informatics
• 作者: Henzinger, Monika;Jin, Billy;Peng, Richard;Williamson, David P.
• 通讯作者: Williamson, David P.