Random Walks, Parametric Integer Programming

随机游走、参数整数规划

• 批准号: 9208597
• 负责人: Ravindran Kannan
• 金额: $ 26万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-08-15 至 1996-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9208597&HistoricalAwards=false
• 关键词: Random; Walks; Parametric; Integer; Programming

This project will have four parts. The first part seeks to improve the running time of algorithms to compute the volumes of convex sets, to do multivariate sampling and integration. Randomized polynomial time algorithms for these problems using rapidly mixing Markov Chains have been used; some new ones will be designed that are ultimately intended to render these theoretically polynomial time bounded algorithms usable in practice. The second part considers some general results on log-concave functions that will reduce the running time of sampling according to such functions; most statistical distributions belong to this class. The third section considers some problems arising in Manufacturing where, one has to optimize (minimize)the cost of components (raw materials) subject to the (chance) constraint that one has enough components to make the probability of our being able to meet the stochastic demands high enough. The last part considers Parametric Integer Programming which arises in contexts where the constraint matrix of an integer program remains fixed and one wishes to solve the problem for various right hand side vectors. Algorithms to preprocess the constraint matrix with a parallel algorithm will be considered.

该项目将有四个部分。 第一部分力求 提高算法的运行时间，以计算体积 凸集，做多变量抽样和积分。 这些问题的随机多项式时间算法， 快速混合马尔可夫链已被使用;一些新的 将被设计为最终旨在使这些 理论上，多项式时间有界算法可用于 实践 第二部分考虑一些一般性结果 对数凹函数，这将减少运行时间 根据这些函数抽样;大多数统计学的 分布属于这一类。 第三部分 考虑了制造业中出现的一些问题， 必须优化（最小化）组件（原始）的成本 材料）受制于（机会）约束， 足够的成分来使我们能够 满足足够高的随机需求。 最后一部分 考虑参数化可编程， 整数规划的约束矩阵 仍然是固定的，人们希望解决各种问题 右手边的向量。 预处理的算法 约束矩阵与并行算法将是 考虑了