Combinatorial Optimization Over Two Random Point Sets
Combinatorial Optimization Over Two Random Point Sets
复制标题
两个随机点集的组合优化
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
C. Bordenave
中科院分区：
文献类型：
--
作者：
F. Barthe;C. Bordenave
设((Mathcal{X}，Mathcal{Y}))是({mathbb{R}}^{d})中相等基数的一对随机点集，通过从公共概率分布μ中独立地抽样2n个点而得到。本文对组合优化中出现的函数((数学{X}，数学{Y}))的L函数感兴趣。典型的例子包括(数学{X})和(数学{Y})的匹配的最小长度，被约束为在每个集合的点之间交替的旅行推销员环游的长度，或者具有顶点集的连通二部r-正则图的最小长度((数学{X}，数学{Y}))。当点集的大小n趋于无穷大时，我们给出了保证(L(数学{X}，数学{Y}))在适当尺度下收敛的函数L和概率测度μ的充分条件。在最小长度匹配的情况下，我们推广了Dobric和Yukich，Boutet de Monvel和Martin的结果。
Let ((mathcal{X},mathcal{Y})) be a pair of random point sets in ({mathbb{R}}^{d}) of equal cardinal obtained by sampling independently 2n points from a common probability distribution μ. In this paper, we are interested by functions L of ((mathcal{X},mathcal{Y})) which appear in combinatorial optimization. Typical examples include the minimal length of a matching of (mathcal{X}) and (mathcal{Y}), the length of a traveling salesperson tour constrained to alternate between points of each set, or the minimal length of a connected bipartite r-regular graph with vertex set ((mathcal{X},mathcal{Y})). As the size n of the point sets goes to infinity, we give sufficient conditions on the function L and the probability measure μ which guarantee the convergence of (L(mathcal{X},mathcal{Y})) under a suitable scaling. In the case of the minimal length matching, we extend results of Dobric and Yukich, and Boutet de Monvel and Martin.