Linear Algebraic Techniques in Algorithmic Graph Theory

算法图论中的线性代数技术

• 批准号: RGPIN-2015-04318
• 负责人: Lau, LapChi
• 金额: $ 3.13万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=688658
• 关键词: Linear; Algebraic; Techniques; Algorithmic; Graph

Algorithms for fundamental graph problems are important tools in computer science and engineering.  Extensive research has been done in the past decades to develop efficient algorithms, most of them based on combinatorial techniques.  In recent years, new linear algebraic techniques have been developed to make surprising and significant progress in these fundamental problems.  My previous research develops linear algebraic techniques to design both better approximation algorithms and faster exact algorithms for graph problems.  I plan to continue this line of ongoing research and have identified three promising directions to investigate.****Spectral graph theory: The application of spectral techniques to study combinatorial graph properties has a long history.  The classical result relates the second eigenvalue to the edge expansion of the graph, and it has been used to develop efficient algorithms for graph partitioning problems and to analyze the mixing time of random walks.  Recently, there have been exciting new results relating other eigenvalues to combinatorial graph properties.  This new connection opens up ways to do better analysis of existing algorithms, to design better approximation algorithms and to design faster algorithms for various graph problems.  I believe that this approach will bring new insights into some outstanding open problems including the small-set expansion conjecture, the bipartite matching problem, and the log-rank conjecture.****Random walks: Random walks are simple stochastic processes on graphs that have a wide range of algorithmic applications.  One classical application of random walks is in designing random sampling algorithms.  Recently, random walks have been used to design sublinear time graph algorithms.  I plan to do a systematic study of the random walks method, to design exact and approximation algorithms and to prove hardness of approximation results.  Also, with our new knowledge about random walks and graph expansion, I would like to revisit the outstanding open problems in random sampling, including the matroid expansion conjecture and the mixing time of the Glauber dynamics for graph coloring.***Linear algebraic algorithms: Recently, there has been significant progress in designing fast algorithms for fundamental graph problems using linear algebraic algorithms.  A major open problem in this area is to design fast algebraic algorithms for weighted problems.  I also plan to develop this approach to solve additional graph problems and linear algebraic problems, and to study the interplay between graph theory and linear algebra.***I believe that achieving the goals in this proposal would have major impacts in the theory of computing, as well as in other areas such as machine learning, applied probability, and symbolic computation.  I also expect to have significant contributions to the training of HQPs by acquiring these emerging techniques with my students. **

基本图问题的算法是计算机科学和工程中的重要工具。在过去的几十年里，人们进行了广泛的研究来开发有效的算法，其中大多数是基于组合技术的。近年来，新的线性代数技术已经被开发出来，在这些基本问题上取得了令人惊讶的重大进展。我以前的研究开发了线性代数技术，以更好地设计这两个问题图问题的近似算法和更快的精确算法。我计划继续这条正在进行的研究路线，并确定了三个有希望的研究方向。*谱图理论：谱技术应用于研究组合图的性质有着悠久的历史，经典的结果将图的第二特征值与边的扩张联系起来，并被用来发展图划分问题的有效算法和分析随机游动的混合时间。最近，已经有令人兴奋的新结果将其他特征值与组合图属性联系起来。2这种新的联系开辟了更好地分析现有算法的方法，设计更好的近似算法，并为各种图问题设计更快的算法。我相信这种方法将为一些悬而未决的开放问题带来新的见解，包括小集扩张猜想，二分匹配问题和对数秩猜想。*随机漫步：随机游动是图上的简单随机过程，在算法上有着广泛的应用。随机游动的一个经典应用是设计随机抽样算法。最近，随机游动被用来设计次线性时间图算法。我计划对随机游动方法进行系统的研究，设计精确算法和近似算法，并证明近似结果的困难性。此外，随着我们对随机游动和图扩张的新知识，我想重新回顾一下随机抽样中悬而未决的开放问题，包括拟阵扩张猜想和图着色的Glauber动力学的混合时间。线性代数算法：最近，使用线性代数算法设计基本图问题的快速算法取得了重大进展。该领域的一个主要开放问题是设计加权问题的快速代数算法。我还计划开发这种方法来解决其他图问题和线性代数问题，并研究图论和线性代数之间的相互作用。*我相信，实现这一建议中的目标将对计算理论以及机器学习、应用概率和符号计算等其他领域产生重大影响。我还希望通过与我的学生一起学习这些新兴技术，为HQP的培训做出重大贡献。**