Approximating vertex cover using edge-based representations
Approximating vertex cover using edge-based representations
复制标题
DOI：
10.1145/2460239.2460248
复制
发表时间：
2013-01
期刊：
影响因子：
--
通讯作者：
T. Jansen;P. S. Oliveto;C. Zarges
中科院分区：
文献类型：
--
作者：
T. Jansen;P. S. Oliveto;C. Zarges
在文献中，只有下界是可用的近似比随机搜索算法的顶点覆盖在单目标问题设置。这些分析是基于自然的基于顶点的表示。受一个著名的问题特定的近似算法的启发，我们提出了一个随机搜索算法的分析，使用基于边缘的表示。对于规范的目标函数，我们证明了性能仍然可以任意坏的（1+1）EA和RLS，即使使用大搜索邻域。向目标函数添加稍微多一点的信息，将RLS和（1+1）EA变成有效的2-近似算法，需要O（mlog m）步，其中m是边的数量。虽然在最坏的情况下是等价的，这样的运行时间上的上限至少是一个线性因子优于稀疏图和具有大的最优顶点覆盖的图的多目标情况。此外，RLS算法，改进后不翻转测试位之前，尝试以前未经测试的，保证2-近似O（m）的步骤。
In the literature only lower bounds are available on the approximation ratio of randomised search heuristics for vertex cover in the single-objective problem setting. These analyses are based on the natural vertex-based representation. Inspired by a well-known problem-specific approximation algorithm, we present an analysis of randomised search heuristics using edge-based representations. For the canonical objective function we prove that the performance can still be arbitrarily bad for the (1+1) EA and also RLS, even when using large search neighbourhoods. Adding slightly more information to the objective function turns RLS and the (1+1) EA into efficient 2-approximation algorithms requiring O(m log m) steps where m is the number of edges. Although equivalent in the worst case, such an upper bound on the runtime is at least a linear factor better than that of the multi-objective case for sparse graphs and for graphs with large optimal vertex covers. Furthermore RLS algorithms, that after an improvement do not flip tested bits before trying previously untested ones, guarantee 2-approximations in O(m) steps.