On a generalization of iterated and randomized rounding
On a generalization of iterated and randomized rounding
复制标题
关于迭代和随机舍入的推广
DOI：
10.1145/3313276.3316313
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
N. Bansal
中科院分区：
文献类型：
--
作者：
N. Bansal
我们给出了一个通用的方法舍入线性规划，结合常用的迭代舍入和随机舍入技术。特别是，我们表明，每当迭代舍入可以应用到一个问题，有一些松弛，有一个随机过程，返回一个完整的解决方案，满足迭代舍入的保证，也有浓度属性。我们用它来给几个经典的问题，迭代舍入是有用的新的结果。
We give a general method for rounding linear programs that combines the commonly used iterated rounding and randomized rounding techniques. In particular, we show that whenever iterated rounding can be applied to a problem with some slack, there is a randomized procedure that returns an integral solution that satisfies the guarantees of iterated rounding and also has concentration properties. We use this to give new results for several classic problems where iterated rounding has been useful.
非对称旅行商问题的常因子逼近算法
DOI：
10.1145/3188745.3188824
发表时间：
2018
期刊：
--
影响因子：
--
作者：
Svensson O
通讯作者：
Svensson O