Breakout Local Search for the Vertex Separator Problem
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 461-466.
Abstract
In this paper, we propose the first heuristic approach for the vertex separator problem (VSP), based on Breakout Local Search (BLS). BLS is a recent meta-heuristic that follows the general framework of the popular Iterated Local Search (ILS) with a particular focus on the perturbation strategy. Based on some relevant information on search history, it tries to introduce the most suitable degree of diversification by determining adaptively the number and type of moves for the next perturbation phase. The proposed heuristic is highly competitive with the exact state-of-art approaches from the literature on the current VSP benchmark. Moreover, we present for the first time computational results for a set of large graphs with up to 3000 vertices, which constitutes a new challenging benchmark for VSP approaches.
@inproceedings{ijcai2013p76,
title = {Breakout Local Search for the Vertex Separator Problem},
author = {Benlic, Una and Hao, Jin-Kao},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {461--466},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/76},
}
TY - CPAPER TI - Breakout Local Search for the Vertex Separator Problem AU - Benlic, Una AU - Hao, Jin-Kao T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 461 EP - 466 UR - https://ijcai.org/proceedings/2013/76 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
