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.