Random Structures and Algorithms

随机结构和算法

基本信息

批准号：
1952285
负责人：
ALAN FRIEZE
金额：
$ 33万
依托单位：
Carnegie-Mellon University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-06-01 至 2024-05-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1952285&HistoricalAwards=false
关键词：
Random Structures Algorithms

项目摘要

The project deals with the likely properties of randomly chosen discrete mathematical objects. It deals with them from an aesthetic and a computational angle. In many cases the objects are networks and the project aims to learn the typical values of various associated parameters. One particular example of this concerns the length of the largest cycle in a randomly chosen graph. One question the PI hopes to resolve is the following: suppose we only sample from networks where each vertex is incident with at least three edges. How many random edges are needed so that with high probability there is a cycle that goes through each vertex once and only once i.e. a Hamilton cycle. As a typical example of a computational problem consider the following: the edges of a network are given random weights and one wishes to find a minimum weight spanning tree i.e. a set of edges that connects the vertices of the network. Suppose that in addition, the edges have random costs and there is a budget for the tree that cannot be exceeded. The PI provides an algorithm for this problem that with high probability finds a near optimal solution very quickly. The PI notes that with an infinite budget, the problem is easily solved, but for a finite budget, the problem is hard in the worst-case. In addition this project provides research training opportunities for graduate students.The project deals with structural and algorithmic questions associated with random graphs, hypergraphs and matrices over a finite field. The PI will try to show that a random graph with cn, c3/2 random edges and conditioned to have minimum degree at least three, is Hamiltonian with high probability. The PI will try to simplify our asymptotic expression for the length of the longest path in a sparse random graph. the PI will attempt to answer these questions in relation to random digraphs. The PI will continue his work on analyzing minimum weighted structures in randomly edge weighted graphs, subject to constraints on a cost budget. The PI will continue his work on random walks. the PI will also try to improve his results on deterministic estimates of the covertime of dense graphs. The PI will study the rank of random matrices over finite fields, trying to explain combinatorially why the actual field does not seem to be important. The PI will also consider the binary case as an example of a random matroid. Finally, the PI will try to extend his analysis of a simple particle dispersion process from one to more than one dimension.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.

该项目涉及随机选择的离散数学对象的可能属性。它从美学和计算的角度来处理它们。在许多情况下，对象是网络，该项目旨在学习各种相关参数的典型值。一个具体的例子涉及随机选择的图中最大循环的长度。 PI 希望解决的一个问题如下：假设我们仅从每个顶点与至少三个边关联的网络中进行采样。需要多少条随机边，以便很有可能存在一个循环通过每个顶点一次且仅一次，即汉密尔顿循环。作为计算问题的典型示例，请考虑以下情况：网络的边被赋予随机权重，并且希望找到最小权重生成树，即连接网络顶点的一组边。此外，假设边具有随机成本，并且树有一个不能超出的预算。 PI 为这个问题提供了一种算法，该算法很有可能很快找到接近最优的解决方案。 PI 指出，如果预算无限，问题很容易解决，但如果预算有限，在最坏的情况下问题会很困难。此外，该项目还为研究生提供研究培训机会。该项目处理与有限域上的随机图、超图和矩阵相关的结构和算法问题。 PI 将尝试证明具有 cn、c3/2 随机边且条件为最小度至少为 3 的随机图是哈密顿量的概率很高。 PI 将尝试简化稀疏随机图中最长路径长度的渐近表达式。 PI 将尝试回答这些与随机有向图相关的问题。 PI 将继续研究随机边缘加权图中的最小加权结构，但受到成本预算的限制。 PI 将继续他的随机游走工作。 PI 还将尝试改进密集图覆盖时间的确定性估计结果。 PI 将研究有限域上随机矩阵的秩，尝试组合地解释为什么实际域似乎并不重要。 PI 还将考虑二进制情况作为随机拟阵的示例。最后，PI 将尝试将他对简单粒子分散过程的分析从一个维度扩展到多个维度。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。