کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420449 683939 2009 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Analyzing quadratic unconstrained binary optimization problems via multicommodity flows
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Analyzing quadratic unconstrained binary optimization problems via multicommodity flows
چکیده انگلیسی

Quadratic Unconstrained Binary Optimization (QUBO) problems concern the minimization of quadratic polynomials in n{0,1}n{0,1}-valued variables. These problems are NP-complete, but prior work has identified a sequence of polynomial-time computable lower bounds on the minimum value, denoted by C2,C3,C4,…C2,C3,C4,…. It is known that C2C2 can be computed by solving a maximum flow problem, whereas the only previously known algorithms for computing Ck(k>2) require solving a linear program. In this paper we prove that C3C3 can be computed by solving a maximum multicommodity flow problem in a graph constructed from the quadratic function. In addition to providing a lower bound on the minimum value of the quadratic function on {0,1}n{0,1}n, this multicommodity flow problem also provides some information about the coordinates of the point where this minimum is achieved. By looking at the edges that are never saturated in any maximum multicommodity flow, we can identify relational persistencies: pairs of variables that must have the same or different values in any minimizing assignment. We furthermore show that all of these persistencies can be detected by solving single-commodity flow problems in the same network.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 18, 28 November 2009, Pages 3746–3753
نویسندگان
, ,