Randomized Algorithms for Matricies, Graphs, and Convex Sets

矩阵、图和凸集的随机算法

• 批准号: 9820850
• 负责人: Ravindran Kannan
• 金额: $ 33.07万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-08-01 至 2003-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9820850&HistoricalAwards=false
• 关键词: Randomized; Algorithms; Matricies; Graphs; Convex

This project is focused on two areas. The first is applying techniques developed for randomized algorithms to traditional matrix problems that have to be solved for very large matrices. In particular, the problem of finding an approximation to a given matrix having a fixed rank. If the matrix is the adjacency matrix of a graph, connection has been developed between such approximations and certain partitions of the vertex set of the graph. The second area is approximation algorithms for convex sets.

该项目侧重于两个领域。 首先是应用技术开发的随机算法，以传统的矩阵问题，必须解决非常大的矩阵。 特别地，找到具有固定秩的给定矩阵的近似的问题。 如果矩阵是图的邻接矩阵，则这种近似与图的顶点集的某些划分之间已经建立了联系。 第二个领域是凸集的近似算法。