Combining Two Local Search Approaches to Hypergraph Partitioning
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1546--1.
Abstract
We study leading-edge local search heuristics for balanced hypergraph partitioning and Boolean satisfiability, intending the generalization of such heuristics beyond their original domains. We adapt the Fiduccia Mattheyses (FM) hypergraph partitioning heuristic to Boolean Satisfiability (SAT), and the WalkSAT SAT solver to hypergraph partitioning. Focusing on balanced hypergraph partitioning, we propose a combination of the classical FM heuristic and our "cross-over" heuristic WalkPart, and empirically show that it is more powerful than each component alone. Empirically, we show a 15 % improvement in net cut and a 7% improvement in runtime over a leading-edge implementation of the FM heuristic.
@inproceedings{ijcai2003p267,
title = {Combining Two Local Search Approaches to Hypergraph Partitioning},
author = {Ramani, Arathi and Markov, Igor L.},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob},
pages = {1546---1},
year = {2003},
url = {https://ijcai.org/proceedings/2003/267},
}
TY - CPAPER TI - Combining Two Local Search Approaches to Hypergraph Partitioning AU - Ramani, Arathi AU - Markov, Igor L. T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 1546 EP - -1 UR - https://ijcai.org/proceedings/2003/267 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
