کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9663700 | 1446239 | 2005 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We address the weighted max-cut problem, or equivalently the problem of maximizing a quadratic form in n binary variables. If the underlying (symmetric) matrix is positive semidefinite of fixed rank d, then the problem can be reduced to searching the extreme points of a zonotope, thus becoming of polynomial complexity in O(nd â 1). Reverse search is an efficient and practical means for enumerating the cells of a regular hyperplane arrangement, or equivalently, the extreme points of a zonotope. We present an enhanced version of reverse search of significantly reduced computational complexity that uses ray shooting and is well suited for parallel computation. Furthermore, a neighborhood zonotope edge following descent heuristic can be devised. We report preliminary computational experiments of a parallel implementation of our algorithms.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 166, Issue 1, 1 October 2005, Pages 35-50
Journal: European Journal of Operational Research - Volume 166, Issue 1, 1 October 2005, Pages 35-50
نویسندگان
J.-A. Ferrez, K. Fukuda, Th.M. Liebling,