Mathematical Sciences: Stochastic Matching and Empirical Discrepancy Problems

点击翻译按钮获取中文摘要

The investigator plans to continue research on stochastic matching and empirical discrepancy problems in Euclidean and general metric spaces. Current research is directed towards understanding the stochastic behavior of matching functionals. This involves finding tight non-asymptotic bounds, limiting distributions, and exponential type moment bounds. This would add to the understanding of several combinatorial optimization problems as well as empirical discrepancy problems, notably finding the rate of convergence of the empirical to the true distribution. Results of this type are useful in stochastic bin-packing as well as statistical physics. Concerning discrepancy problems in mathematical statistics, research is also directed towards further enlarging the collection of known Vapnik-Chervonenkis (VC) classes of sets. This involves establishing general connections between VC classes of positivity sets, quantifier elimination theorems, and semi-algebraic geometry. The proposed research will focus heavily on the theoretical and mathematical aspects of the well-known transportation problem as well as some of its generalizations. This problem has received wide attention over the years and it is recognized that a full understanding of its mathematical complexities will lead to more efficient and perhaps simpler ways to solve optimization problems ranging from the shipping of goods, to the routing of airplanes and the study of statistical mechanics. In its simplest and most elementary form the problem may be stated as follows. Suppose that one is given n oil wells and n refineries and wishes to efficiently pair off wells and refineries, so as to minimize the sum of the matching distances. It is easy to see that there are n| different possible matchings. The transportation problem is to determine the most efficient matching, i.e., to determine that matching which will minimize the sum of the distances. The proposed research will consider variations on this and related problems.