Mathematical Sciences: Stochastic Matching and Empirical Discrepancy Problems

研究者计划继续研究欧几里得空间和一般度量空间中的随机匹配和经验差异问题。目前的研究方向是理解匹配函数的随机行为。这涉及到寻找紧的非渐近边界，极限分布和指数型矩界。这将增加对几个组合优化问题以及经验差异问题的理解，特别是发现经验到真实分布的收敛速度。这类结果在随机装箱和统计物理中都很有用。关于数理统计中的差异问题，研究也指向进一步扩大已知Vapnik-Chervonenkis （VC）类集合的集合。这涉及到在VC类的正集、量词消去定理和半代数几何之间建立一般的联系。拟议的研究将主要集中在众所周知的交通问题的理论和数学方面，以及它的一些概括。这个问题多年来受到了广泛的关注，人们认识到，充分理解它的数学复杂性将导致更有效，也许更简单的方法来解决从货物运输到飞机路线和统计力学研究的优化问题。用最简单和最基本的形式，这个问题可以表述如下。假设给定n口油井和n家炼油厂，并希望有效地将油井和炼油厂配对，以最小化匹配距离的总和。很容易看出有n到100种不同的可能匹配。运输问题是确定最有效的匹配，即确定将距离总和最小化的匹配。拟议的研究将考虑这方面的变化和相关问题。

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.