کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8901592 1631738 2018 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A reactive self-tuning scheme for multilevel graph partitioning
ترجمه فارسی عنوان
یک طرح تنظیم خودکار واکنشی برای پارتیشن بندی چند سطحی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 318, 1 February 2018, Pages 227-244
نویسندگان
, ,