Mathematical Sciences: Stochastic Matching and Empirical Discrepancy Problems

数学科学：随机匹配和经验差异问题

• 批准号: 9200656
• 负责人: Joseph Yukich
• 金额: $ 5.19万
• 依托单位: Lehigh University
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-07-01 至 1994-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9200656&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Stochastic; Matching; Empirical

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.

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