A Comparison of Approximation Algorithms for the MaxCut-Problem

A Comparison of Approximation Algorithms for the MaxCut-Problem
复制标题

MaxCut问题的逼近算法比较

DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
H. Lefmann
H. Lefmann
中科院分区：
--
文献类型：
--
作者：
Oliver Dolezal;T. Hofmeister;H. Lefmann

文献摘要

被引文献

相似文献

在本文中，我们比较，从实用的角度来看，近似算法的问题MaxCut。对于这个问题，我们给出一个具有顶点集V和边集E的无向图G =（V;E），并且我们正在寻找顶点集的一个划分V = V1 [ V2]，其中V1 V2 = ;，该划分使一个端点在V1中而另一个端点在V2中的边e2 E的数量最大化。所研究的算法包括半夜场规划、一种随机策略、遗传算法、两种组合算法和一种分治策略。
In this paper we compare, from a practical point of view, approximation algorithms for the problem MaxCut. For this problem, we are given an undirected graph G = (V;E) with vertex set V and edge set E, and we are looking for a partition V = V1 [ V2 with V1 V2 = ; of the vertex set which maximizes the number of edges e 2 E which have one endpoint in V1 and the other in V2. The investigated algorithms include semide nite programming, a random strategy, genetic algorithms, two combinatorial algorithms and a divide{and{conquer strategy.