权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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，是具有高概率的Hamilton图。PI将尝试简化稀疏随机图中最长路径长度的渐近表达式。PI将尝试回答与随机有向图相关的这些问题。PI将继续他的工作，分析随机边加权图中的最小加权结构，受成本预算的约束。PI将继续他在随机漫步方面的工作。 PI还将尝试改进他关于稠密图的覆盖时间的确定性估计的结果。PI将研究有限域上随机矩阵的秩，试图组合地解释为什么实际的域似乎并不重要。PI还将考虑二进制情况作为随机拟阵的一个例子。最后，PI将尝试将他对一个简单的颗粒分散过程的分析从一维扩展到多维。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。