کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4959001 | 1445461 | 2017 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A Variable Neighborhood Search heuristic for the maximum ratio clique problem
ترجمه فارسی عنوان
محدوده متغیر جستجوی اکتشافی برای حداکثر مشکل کلید نسبت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
جستجوی محدوده متغیر ابتکاری، فراماسونری، حداکثر مشکل کلید نسبت، کلیدهای حداکثر
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
Consider a graph in which every vertex has two non-negative weights. In this graph, the maximum ratio clique problem (MRCP) searches for a maximal clique that maximizes a fractional function defined by the ratio of the sums of vertex weights. It has been proved that MRCP is NP-hard and, consequently, it is difficult to solve MRCP by exact methods. Due to this fact, we present the first heuristic approach, i.e., a multi-start Variable Neighborhood Search (MS-VNS) algorithm. In order to verify the performance of our MS-VNS, we use standard instances and according to our observations, our MS-VNS approach provides high-quality solutions in a short computation time. Furthermore, on most of the instances, our algorithm outperforms the classical methods that have already been used for solving MRCP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 87, November 2017, Pages 283-291
Journal: Computers & Operations Research - Volume 87, November 2017, Pages 283-291
نویسندگان
Dominik Goeke, Mahdi Moeini, David Poganiuch,