随机四舍五入

在计算机科学和运筹学中，许多组合优化问题在计算上是难以精确解决的（达到最优）。许多这样的问题确实存在快速（多项式时间）的近似算法，即保证在任何输入下都能返回一个近似的最优解。随机四舍五入（Raghavan&Tompson1987）是一种广泛使用的设计和分析这种近似算法的方法。其基本思想是使用概率方法将问题的松弛的最优解转换成原始问题的近似最优解。

基本方法有三个步骤。将要解决的问题表述为一个整数线性程序（ILP）。计算一个最优的分数解x(虽然这种方法最常用于线性程序，但有时也会使用其他类型的放宽。例如，见Goemans和Williamson的基于半无限编程的Max-Cut近似算法)。xxx步的挑战是选择一个合适的整数线性程序。需要熟悉线性程序，特别是使用线性程序和整数线性程序的建模。对于许多问题，有一个自然的整数线性程序可以很好地工作，例如下面的SetCover例子。(整数线性程序应该有一个小的积分差距；事实上，随机四舍五入经常被用来证明积分差距的界限）。在第二步中，通常可以使用任何标准的线性编程算法在多项式时间内计算出最优的分数解。在第三步中，必须将分数解转化为整数解（因此也是原问题的解）。这被称为分数解的舍入。由此产生的整数解应该（可以证明）具有不比分数解的成本大得多的成本。这将确保整数解的成本不比最优整数解的成本大得多。用于第三步（四舍五入）的主要技术是使用随机化，然后使用概率论证来约束四舍五入导致的成本增加（遵循组合学的概率论方法）。其中，概率论证被用来证明具有所需属性的离散结构的存在。在这种情况下，人们用这种论证来表明以下情况。给出任何分数解{displaystylex}，LP的任何分数解的任何分数解，随机化舍入过程以正概率产生一个整数解最后，为了使第三步在计算上有效，我们可以表明{displaystylex}的概率很高后一种方法将随机舍入过程转换为有效的确定性过程，保证达到一个好的结果。

与概率方法的其他应用比较随机取舍步骤在两个方面与概率方法的大多数应用不同。舍入步骤的计算复杂性很重要。它应该可以由快速（如多项式时间）算法实现。随机实验的基础概率分布是解x的一个函数{displaystylex}的函数。的放宽的函数。这一事实对于证明近似算法的性能保证至关重要---即对于任何问题实例，该算法都会返回一个近似于该特定实例的最优解的解。相比之下，概率方法在组合学中的应用通常显示了结构的存在，其特征取决于输入的其他参数。