RANDOMIZED ROUNDING - A TECHNIQUE FOR PROVABLY GOOD ALGORITHMS AND ALGORITHMIC PROOFS
RANDOMIZED ROUNDING - A TECHNIQUE FOR PROVABLY GOOD ALGORITHMS AND ALGORITHMIC PROOFS
复制标题
DOI：
10.1007/bf02579324
复制
发表时间：
1987-01-01
期刊：
影响因子：
1.1
通讯作者：
THOMPSON, CD
中科院分区：
文献类型：
--
作者：
RAGHAVAN, P;THOMPSON, CD
研究了一类0-1整数线性规划与其有理松弛的关系。我们给出了一个随机化算法，用于将松弛问题的最优解转换为0-1问题的可证明的好解。我们的技术可以扩展到为给定的问题实例提供理性和0-1最优之间的差距的界限。
We study the relation between a class of 0–1 integer linear programs and their rational relaxations. We give a randomized algorithm for transforming an optimal solution of a relaxed problem into a provably good solution for the 0–1 problem. Our technique can be a of extended to provide bounds on the disparity between the rational and 0–1 optima for a given problem instance.