NeTS: Small: Distributed and Efficient Randomized Algorithms for Large Networks

NeTS：小型：大型网络的分布式高效随机算法

• 批准号: 1217341
• 负责人: Do Young Eun
• 金额: $ 36.69万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1217341&HistoricalAwards=false
• 关键词: NeTS; Small; Distributed; Efficient; Randomized

At the heart of most algorithms for distributed and randomized algorithms is a Markov chain that 'visits and samples' a subset of the nodes in the graph and which satisfies the following three properties: the answer derived from walking the graph converges, the transition probabilities for next state only depend on locally available information and the convergence is 'fast-mixing' or efficient. The proposal will develop approaches for improving the mixing time of Markov Chain Monte Carlo (MCMC) algorithms. These approaches are then to be applied as a building block for algorithms in three distinct areas -- (1) sampling large graphs (2) wireless multihop scheduling and (3) duty cycling in wireless sensor networks.Broader Impact: MCMC-like approaches underly algorithms for a wide range of socially and economically important problems and that progress in improving the mixing time will have significant impacts. Additionally, the proposal highlights student mentorship and interdisciplinary course development.

在大多数分布式和随机化算法的核心是一个马尔可夫链，它“访问和采样”图中节点的子集，并满足以下三个属性：从遍历图中得出的答案收敛，下一个状态的转移概率仅取决于本地可用信息，收敛是“快速混合”或有效的。 该提案将开发用于改进马尔可夫链蒙特卡罗（MCMC）算法的混合时间的方法。然后，这些方法将被应用作为一个积木的算法在三个不同的领域-（1）采样大型图形（2）无线多跳调度和（3）在无线传感器networks.Broader影响的责任循环：MCMC样的方法基本算法的广泛的社会和经济上的重要问题，并在改善混合时间的进展将产生重大影响。 此外，该提案还强调了学生辅导和跨学科课程开发。