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.