Random Structures and Algorithms

随机结构和算法

基本信息

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

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

项目摘要

This award supports foundational research into the concept of randomness in mathematical structures. While the use of randomness in computer science is ubiquitous, many important computational and algorithmic problems remain to be studied using this foundational concept. Despite the complexity of many theoretic as well as practical modern algorithms, randomness is frequently able to remedy the worst-case examples focusing on the average case examples and randomized algorithms which make use of local information. This includes such intensively studied problems as the so-called Travelling Salesperson problem, by concentrating on geometric versions where efficient algorithms are feasible. An important aspect of the project is the involvement of students in the research, which is expected to have a broad impact on mathematics and on computer science beyond the theoretical foundations of the project.A special focus of this project is to identify problems that involve random walks on graphs and digraphs. Based on significant recent progress, a thorough investigation of so-called hashing schemes will be undertaken, examining search algorithms on graphs that employ only local information. The classical random walk is a prime example of such an algorithm. The current available analysis for preferential attachment graphs, which are connected to random models of the world-wide web, will be extended to more general models of graphs. A statistical test has been devised for detecting bias in a sample claiming to be from the steady state of a Markov chain. Another line of research is on-line purchasing problems. In such problems, the edges of a graph are given random costs and are presented sequentially and they must be selected or rejected. The accepted edges are used to build a structure, and the goal is to build this structure as economically as possible.

该奖项支持对数学结构中随机性概念的基础研究。虽然随机性在计算机科学中的使用无处不在，但许多重要的计算和算法问题仍有待使用这一基本概念进行研究。尽管许多理论和实用的现代算法都很复杂，但随机性通常能够弥补最坏情况的例子，重点关注平均情况示例和利用局部信息的随机算法。这包括通过集中研究有效算法可行的几何版本来深入研究的问题，例如所谓的旅行推销员问题。该项目的一个重要方面是学生参与研究，预计这将对数学和计算机科学产生超出该项目理论基础的广泛影响。该项目的一个特别重点是识别涉及随机的问题在图和有向图上行走。基于最近的重大进展，将对所谓的哈希方案进行彻底的研究，检查仅使用本地信息的图搜索算法。经典的随机游走是这种算法的一个主要例子。当前可用的优先附件图分析（与万维网的随机模型相关）将扩展到更通用的图模型。设计了一种统计测试来检测声称来自马尔可夫链稳态的样本中的偏差。另一个研究方向是在线购买问题。在此类问题中，图的边被赋予随机成本并按顺序呈现，并且必须选择或拒绝它们。接受的边用于构建结构，目标是尽可能经济地构建该结构。