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的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

项目成果

Graph coloring and semidefinite rank

图着色和半定秩

• DOI: 10.1007/978-3-031-06901-7_29
• 发表时间: 2022
• 期刊: 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
• 期刊: Proceedings of the 2023 Symposium on Simplicity in Algorithms
• 作者: Breen, Emmett;Mirka, Renee;Wang, Zichen;Williamson, David P.
• 通讯作者: Williamson, David P.

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

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

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

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

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

• 发表时间: 2023
• 期刊: 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
• 期刊: Leibniz international proceedings in informatics
• 作者: Henzinger, Monika;Jin, Billy;Peng, Richard;Williamson, David P.
• 通讯作者: Williamson, David P.