Probabilistic Analysis of a Relaxation for the k-Median Problem
Probabilistic Analysis of a Relaxation for the k-Median Problem
复制标题
k 中值问题松弛的概率分析
DOI：
10.1287/moor.13.1.1
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
A. Frieze
中科院分区：
文献类型：
--
作者：
Sang;C. Cooper;G. Cornuéjols;A. Frieze
摘要：本文提供了 k 中值问题的所谓“强”线性规划松弛的概率分析。该分析是在区位理论中的四种经典模型、欧几里得模型、网络模型、树模型和统一成本模型下进行的。例如，结果表明，对于欧几里得模型和 log or = k or = n/(log n) 平方，松弛值几乎肯定在最佳 k 中值的 0.3% 范围内。对其他模型也进行了类似的分析。它还表明，在各种假设下，使用这种松弛作为界限的分支定界算法几乎肯定必须扩展非多项式数量的节点才能最优地解决 k 中值问题。最后，报告了广泛的计算实验。正如概率分析所预测的那样，对于从统一成本模型得出的问题实例，松弛并不像其他模型那样严格。
Abstract : This paper provides a probabilistic analysis of the so-called 'strong' linear programming relaxation of the k-median problem. The analysis is performed under four classical models in location theory, the Euclidean, network, tree and uniform cost models. For example, it is shown that, for the Euclidean model and log or = k or = n/(log n) squared, the value of the relaxation is almost surely within .3 percent of the optimum k-median value. A similar analysis is perfromed for the other models. It is also shown that, under various assumption, branch and bound algorithms that use this relaxation as a bound must almost surely expand a non-polynomial number of nodes to solve the k-median problem to optimality. Finally, extensive computational experiments are reported. As predicted by the probabilistic analysis, the relaxation was not as tight for the problem instances drawn from the uniform cost model as for the other models.