图的最大二等分问题的一种离散填充函数算法  

Discrete filled function method for max-bisection problem

作　　者：林耿[1] 徐梅琴 

机构地区：[1]闽江学院数学系,福州350108 [2]闽江学院人事处,福州350108

出　　处：《计算机工程与应用》2016年第5期27-32,共6页Computer Engineering and Applications

基　　金：国家自然科学基金(No.11226236;No.11301255);福建省自然科学基金(No.2012J05007);福建省中青年教师教育科研项目(No.JA13246;No.JK2012037)

摘　　要：图的最大二等分问题是一个经典的NP困难问题,有着广泛的应用背景。提出了一类求解最大二等分问题的离散填充函数算法。该算法采用快速的、基于迭代改进的算法作为局部搜索算法。构造了最大二等分问题的填充函数和辅助问题,并研究了该辅助问题的相关性质。利用局部搜索算法极大化辅助问题来寻找更好的解。用顶点数为800到10 000的大规模标准测试例子测试提出的算法。实验结果表明,该算法是有效的。The max-bisection problem is one of classical NP-hard problems, and has lots of applications. This paper presents a discrete filled function method for solving the max-bisection problem. It adopts a quickly iterative improvement algorithm as local search method. A filled function and an auxiliary problem of the max-bisection problem are constructed,and some properties of the auxiliary problem are studied. Maximization of the auxiliary problem uses the local search method to find better solutions. The experiments are done on a number of large scale benchmarks with 800 to 10, 000 vertices from the literature. The experimental results show that the proposed algorithm is efficient.

关 键 词：最大二等分 填充函数 启发式 局部搜索 

分 类 号：O221.4[理学—运筹学与控制论]