首页> 外文会议>International Workshop on Experimental and Efficient Algorithms >Experimental Evaluation of the Greedy and Random Algorithms for Finding Independent Sets in Random Graphs
【24h】

Experimental Evaluation of the Greedy and Random Algorithms for Finding Independent Sets in Random Graphs

机译:在随机图中查找独立集的贪婪和随机算法的实验评价

获取原文

摘要

This work is motivated by the long-standing open problem of designing a polynomial-time algorithm that with high probability constructs an asymptotically maximum independent set in a random graph. We present the results of an experimental investigation of the comparative performance of several efficient heuristics for constructing maximal independent sets. Among the algorithms that we evaluate are the well known randomized heuristic, the greedy heuristic, and a modification of the latter which breaks ties in a novel way. All algorithms deliver online upper bounds on the size of the maximum independent set for the specific input-graph. In our experiments, we consider random graphs parameterized by the number of vertices n and the average vertex degree d. Our results provide strong experimental evidence in support of the following conjectures: 1. for d = c·n (c is a constant), the greedy and random algorithms are asymptotically equivalent; 2. for fixed d, the greedy algorithms are asymptotically superior to the random algorithm; 3. for graphs with d ≤ 3, the approximation ratio of the modified greedy algorithm is asymptotically < 1.005. We also consider random 3-regular graphs, for which non-trivial lower and upper bounds on the size of a maximum independent set are known. Our experiments suggest that the lower bound is asymptotically tight.
机译:这项工作是通过设计多项式算法的长期开放问题,高概率构造了随机图中的渐近最大独立集合。我们介绍了对构建最大独立集的几种高效启发式的比较表现的实验研究结果。在我们评估的算法中,我们评估是众所周知的随机启发式,贪婪启发式,以及以新颖的方式破坏关系的后者的修改。所有算法都在特定输入图的最大独立集的大小上提供在线上限。在我们的实验中,我们考虑由顶点N和平均顶点D的数量参数化的随机图。我们的结果提供了强有力的实验证据,支持以下猜想:1。对于D = C·N(C是常数),贪婪和随机算法是渐近的等价物; 2.对于固定D,贪婪算法渐近算法优于随机算法; 3.对于D≤3的图表,修改的贪婪算法的近似比是渐近的<1.005。我们还考虑随机的3常规图形,其中有哪些非平凡的下限和上限在最大独立集的大小上是已知的。我们的实验表明,下限是渐近的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号