Parallel Unconstrained Local Search for Partitioning Irregular Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908357847154688 |
|---|---|
| author | Maas, Nikolai Gottesbüren, Lars Seemaier, Daniel |
| author_facet | Maas, Nikolai Gottesbüren, Lars Seemaier, Daniel |
| contents | We present new refinement heuristics for the balanced graph partitioning problem that break with an age-old rule. Traditionally, local search only permits moves that keep the block sizes balanced (below a size constraint). In this work, we demonstrate that admitting large temporary balance violations drastically improves solution quality. The effects are particularly strong on irregular instances such as social networks. Designing efficient implementations of this general idea involves both careful selection of candidates for unconstrained moves as well as algorithms for rebalancing the solution later on. We explore a wide array of design choices to achieve this, in addition to our third goal of high parallel scalability. We present compelling experimental results, demonstrating that our parallel unconstrained local search techniques outperform the prior state of the art by a substantial margin. Compared with four state-of-the-art solvers, our new technique finds 75\% of the best solutions on irregular graphs. We achieve a 9.6\% improvement in edge cut over the next best competitor, while being only 7.7\% slower in the geometric mean. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_15494 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Parallel Unconstrained Local Search for Partitioning Irregular Graphs Maas, Nikolai Gottesbüren, Lars Seemaier, Daniel Social and Information Networks Distributed, Parallel, and Cluster Computing We present new refinement heuristics for the balanced graph partitioning problem that break with an age-old rule. Traditionally, local search only permits moves that keep the block sizes balanced (below a size constraint). In this work, we demonstrate that admitting large temporary balance violations drastically improves solution quality. The effects are particularly strong on irregular instances such as social networks. Designing efficient implementations of this general idea involves both careful selection of candidates for unconstrained moves as well as algorithms for rebalancing the solution later on. We explore a wide array of design choices to achieve this, in addition to our third goal of high parallel scalability. We present compelling experimental results, demonstrating that our parallel unconstrained local search techniques outperform the prior state of the art by a substantial margin. Compared with four state-of-the-art solvers, our new technique finds 75\% of the best solutions on irregular graphs. We achieve a 9.6\% improvement in edge cut over the next best competitor, while being only 7.7\% slower in the geometric mean. |
| title | Parallel Unconstrained Local Search for Partitioning Irregular Graphs |
| topic | Social and Information Networks Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2308.15494 |