Algorithms for Convex Sets

凸集算法

• 批准号: 9007602
• 负责人: Ravindran Kannan
• 金额: $ 14.1万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-08-15 至 1993-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9007602&HistoricalAwards=false
• 关键词: Algorithms; Convex; Sets

The project has three parts: Efficient algorithms for random sampling from convex sets in Euclidean space using the theory of rapidly mixing Markov chains and the applications of such algorithms. Lattice relaxations of Integer Programming problems that produce better bounding procedures and related lattice questions. Strongly polynomial time algorithms for the greatest common divisor and genealizations.

本项目分为三部分：利用快速混合马尔可夫链理论的欧几里得空间凸集随机抽样的高效算法及其应用。整数规划问题的格松弛，产生更好的边界程序和相关的格问题。最大公约数的强多项式时间算法及其推广。