| Analyzing Quadratic Unconstrained Binary Optimization Problems Via Multicommodity Flows. | |
| | |
MedLine Citation:
|
PMID: 20161596 Owner: NLM Status: Publisher |
Abstract/OtherAbstract:
|
Quadratic Unconstrained Binary Optimization (QUBO) problems concern the minimization of quadratic polynomials in 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 C(2), C(3), C(4),.... It is known that C(2) can be computed by solving a maximum-flow problem, whereas the only previously known algorithms for computing C(k) (k > 2) require solving a linear program. In this paper we prove that C(3) 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), 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. |
| | |
Authors:
|
Di Wang; Robert D Kleinberg |
Related Documents
:
|
12139196 - Math and numeracy in young adults with spina bifida and hydrocephalus. 19802366 - Compensated optimal grids for elliptic boundary-value problems. 18451436 - Nature reserve selection problem: a tight approximation algorithm. 2721166 - On the optimal choice of the electrode number and locations in body surface mapping. 7902536 - Clinical manifestations of aids in the era of pneumocystis prophylaxis. multicenter aid... 18266026 - Impacts of off-road vehicles (orvs) on macrobenthic assemblages on sandy beaches. |
Publication Detail:
|
Type: JOURNAL ARTICLE |
Journal Detail:
|
Title: Discrete applied mathematics (Amsterdam, Netherlands : 1988) Volume: 157 ISSN: 0166-218X ISO Abbreviation: - Publication Date: 2009 Nov |
Date Detail:
|
Created Date: 2010-7-13 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101511577 Medline TA: Discrete Appl Math Country: - |
Other Details:
|
Languages: ENG Pagination: 3746-3753 Citation Subset: - |
Affiliation:
|
Department of Computer Science Cornell University Ithaca, NY 14853 Telephone: 607-379-1538 Email: dw236@cornell.edu. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
| Grant Support | |
ID/Acronym/Agency:
|
P41 RR023953-01A1//NCRR NIH HHS |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Indentation of an elastic half space with material properties varying with depth.
Next Document: Biochemically responsive smart surface.