A reactive self-tuning scheme for multilevel graph partitioning
| Autor: | Tahir Emre Kalayci, Roberto Battiti |
|---|---|
| Přispěvatelé: | Department of Information Engineering and Computer Science, University of Trento, Trento, 38123, Italy, Lobachevsky State University of Nizhni Novgorod, Nizhni Novgorod, 603950, Russian Federation, Department of Computer Engineering, Manisa Celal Bayar University, Manisa, 45140, Turkey |
| Rok vydání: | 2018 |
| Předmět: |
021103 operations research
Theoretical computer science Applied Mathematics 0211 other engineering and technologies Self-tuning Graph partition 02 engineering and technology Tabu search Graph Computational Mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Metaheuristic Algorithm Mathematics |
| Zdroj: | Applied Mathematics and Computation. 318:227-244 |
| ISSN: | 0096-3003 |
| Popis: | We propose a new multilevel graph bi-partitioning approach (M-RRTS) using greedy construction and reactive-randomized tabu search (RRTS). RRTS builds upon local search by adding prohibitions (to enforce diversification) and self-tuning mechanisms to adapt meta-parameters in an online manner to the instance being solved. The novel M-RRTS approach adds a multi-scale structure to the previous method. The original graph is summarized through a hierarchy of coarser graphs. At each step, more densely-interconnected nodes at a given level of the hierarchy are coalesced together. The coarsest graph is then partitioned, and uncoarsening phases followed by refinement steps build solutions at finer levels until the original graph is partitioned. A variation of RRTS is applied for the refinement of partitions after each uncoarsening phase. We investigate various building blocks of the proposed multilevel scheme, such as different initial greedy constructions, different tie-breaking options and various matching mechanisms to build the coarser levels. Detailed experimental results are presented on the benchmark graphs from Walshaw's graph partitioning repository and potentially hard graphs. The proposed approach produces the record results for 14 of 34 graphs from the repository in lower CPU times with respect to competing approaches. These results confirm the value of the new self-tuning and multilevel strategy to rapidly adapt to new instances. © 2017 Elsevier Inc. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect