Abstract: 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.

Key words: max-bisection, filled function, heuristic, local search

摘要： 图的最大二等分问题是一个经典的NP困难问题，有着广泛的应用背景。提出了一类求解最大二等分问题的离散填充函数算法。该算法采用快速的、基于迭代改进的算法作为局部搜索算法。构造了最大二等分问题的填充函数和辅助问题，并研究了该辅助问题的相关性质。利用局部搜索算法极大化辅助问题来寻找更好的解。用顶点数为800到10 000的大规模标准测试例子测试提出的算法。实验结果表明，该算法是有效的。

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