Graph partitioning using tabu search

Present anothers approach to the balanced minimum cut graph partitioning problem. This approach is based on the meta-heuristic known as tabu search. The experimental results indicate that the algorithm consistently outperformed the KLFM algorithm. Improvements in the quality of solutions can be as high as 33%. The speed of the algorithm is also comparable. Improvements on random graphs are small, but improvements on geometric graphs are very significant. The algorithm is also less erratic. When compared with the simulated annealing algorithm, the algorithm did not perform as well in terms of quality of solutions on random graphs, even though in most cases the results are close. However, the algorithm outperformed the annealing algorithm in almost all the test cases on geometric graphs. The algorithm is also faster by two to three orders of magnitude