Quadratic unconstrained binary optimization (QUBO)
Quadratic unconstrained binary optimization (QUBO) is a pattern matching technique, common in machine learning applications. QUBO is an NP hard problem. QUBO problems are particularly well suited for processing on quantum computers.

 QUBO is given by the formula: E(X_1, X_2, ... , X_N) = \sum_{i<j=1}^N Q_{ij} \times X_i \times X_j

Abstract

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 C2,C3,C4,…. It is known that C2 can be computed by solving a maximum flow problem, whereas the only previously known algorithms for computing View the MathML source require solving a linear program. In this paper we prove that C3 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.

Keywords

  • Quadratic unconstrained binary optimization
  • Multicommodity flow
  • Network flow
  • Persistency
  • Roof duality

1. Introduction

In this paper, we study the problem of Quadratic Unconstrained Binary Optimization (QUBO), which determines the minimum over {0,1}n of quadratic pseudo-Boolean functions of the form

 

Quadratic pseudo-Boolean functions are a common class of energy functions that are widely useful, and which have been strikingly successful in computer vision (see [7] for a recent survey). Even in cases when the QUBO problem cannot be fully solved by an efficient algorithm, one can often extract useful information for the computer vision applications by discovering persistencies, i.e. partial assignments of the variables that must occur in an assignment that minimizes the function. Persistencies have proved to be particularly useful for medical imaging applications [9].

Although the QUBO problem is NP-hard, several approaches have been proposed to give good lower bounds on the minimum value. Many of these approaches involve rewriting the quadratic pseudo-Boolean function using posiforms, which we now define.

 

Let V={x1,x2,…,xn} be the set of variables, and let View the MathML source denote the set of negated variables, where View the MathML source. The elements of View the MathML source are called literals.

We can represent non-negative pseudo-Boolean functions as posiforms, i.e. multilinear polynomial expressions over all the literals with positive term coefficients

where Ω is a collection of subsets of L, and aT>0 for all TΩ. Every posiform ϕ defines a unique pseudo-Boolean function f on substituting View the MathML source, but a pseudo-Boolean function can have multiple posiform representations.

 

A particular lower bound called the roof-dual, denoted by C2, is introduced in [8]. If f is a quadratic pseudo-Boolean function, then C2 is the maximum c such that f=c+ϕ, where ϕ is a posiform of degree 2. It is shown in [6] that we can compute C2 by solving a maximum flow problem on a special graph called an implication network. The roof-dual value is then generalized to a family of lower bounds Ck. (See [2] for definitions.)

 

In this paper we will focus on the bound C3. Let P3 be the cone of non-negative quadratic pseudo-Boolean functions having a posiform of degree 3. Then as defined in [3]

C3=max{cR|f=c+ϕ,ϕP3}.
It is proved in [3] that C3 can be computed by solving an odd cycle packing problem, but due to the fact that C2 can be computed using maximum flow, we are interested in formulating C3 as the solution of a flow problem.

 

 

Among the set of all possible posiforms of a quadratic pseudo-Boolean function, we will work with the bi-formin particular, which is introduced in [4]. For variables x and y, we call View the MathML source a positive bi-term, and View the MathML source a negative bi-term. If E denotes a collection of bi-terms such that no pair of variables is involved in more than one element of E, and αe>0 for all eE, then we call ϕ=∑eEαee a bi-form. By introducing variable x0, we can write any quadratic pseudo-Boolean function f in variables x1,…,xn uniquely as f(x1,…,xn)=cf+ϕf(1,x1,…,xn), where ϕf is a bi-form in the variables x0,x1,…,xn. (See [5].)

 

Given a quadratic pseudo-Boolean function f=cf+ϕf, where ϕf is a bi-form, we define an undirected graphGϕf=(Vϕf,Eϕf) as follows. Vϕf=L, where L is the set of literals of f. We associate two edges with each bi-term. For positive bi-term View the MathML source, we have edges (xi,xj) and View the MathML source, with weight View the MathML source. For negative bi-term View the MathML source, we have edges View the MathML source and View the MathML source, with weight View the MathML source. Conversely, edge (u,v) with capacity δ in Gϕf corresponds to the bi-term View the MathML source.

We prove in Section 3 that for any quadratic pseudo-Boolean function fC3 is the sum of cf and the maximum multicommodity flow value of network Gϕf with source–sink pairs View the MathML source. (See Section 2 for definitions related to multicommodity flow.)

Besides being helpful to have the numerical lower bound on the minimum value, it is also useful to obtain partial optimal assignments. The concepts of persistency and autarky are defined in [6], and we can generalize the idea of persistency and autarky to relational persistency and relational autarky. Call a set of literals valid if it contains at most one of xi and View the MathML source for all i. Consider a valid subset UL. We will say U is astrong (resp., weak) relational persistency if literals in U have the same value in all (resp., some) optimal assignment.

 

For any assignment x=(x1,…,xn) and Boolean value b∈{0,1}, let x[Ub] denote the assignmenty=(y1,…,yn) specified by

We will call U a strong (resp., weak) relational autarky if for all Boolean assignments x, there exists a value b∈{0,1} such that f(x[Ub])<f(x) (resp., f(x[Ub])≤f(x)), or x[Ub]=x. Relational persistencies and relational autarkies allow us to reduce the size of the optimization problem, since we can rewrite a posiform with a smaller variable set, while maintaining the same minimum value.

 

 

In Section 4, we focus on finding strong relational persistencies. When we push flow along a path in Gϕf fromxi to View the MathML source, it is equivalent to rewriting the bi-terms associated with edges on the path into a cubic posiform, and it turns out that we can derive strong relational persistencies from the residual graph. In Theorem 2, we prove that if an edge (u,v) can never be saturated in a solution of our maximum multicommodity flow problem, literals u and v must have the same value in any minimizer of f. Then in Theorem 3, we consider the maximum flow problem on Gϕf with single source–sink pair View the MathML source, and we show that in the residual graph, the set of literals in the connected component containing xi is a strong relational persistency. Furthermore, we show that if U is a strong relational persistency, and xiU, then there must be a maximum flow assignment for source–sink pair View the MathML source such that U is a connected component in the residual graph.

Unsurprisingly, many techniques used in studying C3 generalize those used in studying C2. We introduce the variable x0 simply to make the posiform homogeneously quadratic, and we don’t treat x0 differently in computing C3 and deriving relational persistencies. Various known facts about C2 and its associated persistencies can be interpreted as a special case of the facts derived here, when we enforce the constraintx0=1. For example, [6] obtains strong relational autarkies from the residual graph of running a maximum flow computation for the source–sink pair View the MathML source. In Theorem 3, we use the same technique over all source–sink pairs View the MathML source.

2. Definitions and notation

In this section, we summarize some definitions and notation involving multicommodity flow problems and their relationship to quadratic Boolean formulas.

 

2.1. Weighted signed graphs, odd cycles

A weighted signed graph G is an undirected graph (V,E) together with a set of positive weights {αe|eE}and a partition {E+,E} of the edge set E. The edges in E+ are called positive, and those in E are called negative. A cycle of G is called odd if it contains an odd number of negative edges. The set of odd cycles is denoted by C.

2.2. Odd cycle packing

Given weighted signed graph G, the odd cycle packing problem (CP) is

 

 

2.3. Multicommodity flow

Given undirected graph G=(V,E) with edge capacities ce≥0, and source–sink pairs (s1,t1),…,(sk,tk), let View the MathML source3The maximum multicommodity flow problem on G is

Any vector (ζp) satisfying the constraints in (2) is called a multicommodity flow, or simply a flow, regardless of whether it maximizes the objective function. For a thorough introduction to multicommodity flow theory, we refer the reader to [1].

 

2.4. The graphs Gf and Gϕ

Given quadratic pseudo-Boolean function f, we can write f uniquely as the sum of a constant and a bi-form:

We can construct a weighted signed graph Gf=(Vf,Ef) corresponding to bi-form ϕf as follows. The vertex set Vf is equal to {x0,…,xn}, the set of variables of ϕf. We associate an edge with each bi-term in ϕf. Edges have the same sign as their associated bi-terms, and the weights αe are the same as the coefficients of their associated bi-terms.

 

 

Recall that there is another graph associated with ϕf, namely the graph Gϕf with vertex set View the MathML source defined in Section 1. Henceforth we will use the notation Gϕ rather than Gϕf for convenience. In Section 3 we will relate the maximum multicommodity flow problem in Gϕ to the odd cycle packing problem in Gf.

 

2.5. Symmetric flow

The graph Gϕ has a twofold symmetry given by a permutation ι:VϕVϕ. This permutation is defined by setting View the MathML source and View the MathML source. We can extend ι to edges in the obvious way: if u,v are literals and e=(u,v) is an edge of Gϕ, then the definition of Gϕ ensures that View the MathML source is also an edge of Gϕ and we can define View the MathML source. Similarly we can extend ι to sets of vertices — ι(S)={u|ι(u)∈S} — and to paths: for a path p in Gϕ, if p=v1→⋯→vk then ι(p)=ι(vk)→⋯→ι(v1). (Note that ι reverses the direction of the path.) Finally we can extend ι to flows: if ζ is any flow, then ι(ζ) is defined by setting ι(ζ)p=ζι(p) for all paths p. Note that ι(ζ) is also a flow because the edge capacities are preserved by ι. A flow ζ is calledsymmetric if it satisfies ι(ζ)=ζ. Note that if ζ is any maximum multicommodity flow, then View the MathML source is also a maximum multicommodity flow, and it is symmetric. Thus, there is always at least one symmetric flow that optimizes (2).

 

3. Computing C3 reduces to multicommodity flow

Give quadratic pseudo-Boolean function f, we can find its unique bi-form representation, f=cf+ϕf, then construct Gf and Gϕ according to ϕf. Denote by v(CP) the optimal value of the cycle packing problem onGf, and by v(PP) the optimal value of the multicommodity flow problem on Gϕ with source–sink pairs View the MathML source.

 

Lemma 1. For any quadratic pseudo-Boolean functionf,C3=cf+v(CP).

 

 

Proof. See [3]. □

 

 

Lemma 2. For any quadratic pseudo-Boolean functionf,v(PP)=v(CP).

 

 

 

Proof. To prove Lemma 2, we will show that for every feasible solution ξ of the cycle packing problem, we can construct a feasible symmetric solution ζ of the multicommodity flow problem with the same objective function value, and vice versa.ξζ:Given odd cycle CC, starting from the variable with the lowest index, we can derive two paths pC and View the MathML source in Gf where

For every path p in Gf, there is a unique path λ(p)=u0→⋯→uk+1 in Gϕ satisfying u0=xc0, and View the MathML source for all i>0. In fact λ(p) can be defined by letting p[1..i] denote the initial segment of pstarting at xc0 and ending at xci, and settingNote that View the MathML source when p is an odd cycle.Given feasible CP solution ξ, we can construct solution ζ of the multicommodity flow problem:It is clear that ξ and ζ have the same objective function value, and ζ is symmetric. The flow ζ is also feasible, because if ζ violates the capacity constraint of edge (u,v) in PP, ξ must violate the corresponding constraint of the edge View the MathML source in CP. Here and henceforth, var denotes the function from literals to variables defined by View the MathML source.ζξ:Given path pPi in Gϕ, we can write pasExtending the function var to paths, we get paths in Gf:Consider Vϕ as the union of two sets Vf and View the MathML source. An easy observation is that if an edge’s two endpoints are in the same set, its associated bi-term is positive, and if its endpoints are in different sets, it is associated with a negative bi-term. Since p goes from xi to View the MathML source, we know that there are an odd number of edges in p that are associated with negative bi-terms, so View the MathML source. Given a feasible solution ζ of the multicommodity flow problem, we can construct a solution ξ of the cycle packing problem:ξ has the same objective function value as ζ. We can prove that ξ is feasible by contradiction.Suppose ξviolates the constraintEach edge in Ef is associated with a bi-term, which corresponds to two edges in Eϕ, so for edge e0 there are two corresponding edges e1,e2Eϕ, whereFrom the correspondence between paths in Gϕ and odd cycles in Gf, we know that every path p with View the MathML source must use one of e1 and e2, soWe know that at least one of the two constraints in multicommodity flow is violated, i.e.,which contradicts the feasibility of ζ. Thus we know that ξ must be feasible.Since for every feasible solution ξ of cycle packing problem, we can construct a feasible solution ζ of the multicommodity flow problem with the same objective function value, and vice versa, v(CP)=v(PP). □

 

 

 

 

Theorem 1. For any quadratic pseudo-Boolean functionf,C3=cf+v(PP).

 

 

Proof. Theorem 1 is a direct result of Lemma 1 and Lemma 2. □

 

4. Persistency and autarky results

 

Theorem 2. Ife=(u,v)is an edge ofGϕsuch thateis not saturated in any symmetric maximum multicommodity flow, then{u,v}is a strong relational persistency for the corresponding pseudo-Boolean functionf.

 

 

 

Proof. Notice that given a feasible solution ζ for the multicommodity flow problem on Gϕ, we can express the graph’s edge capacity vector as the sum of two non-negative vectors, one for the flow value on edges, and the other for the remaining edge capacities. We refer to these vectors as “the flow layer” and “the remaining graph layer”. The flow layer can be directly derived from the flow assignments, and the remaining graph layer,Gϕ,ζ=(Vϕ,ζ,Eϕ,ζ), where:

Vϕ,ζ=Vϕ.

Eϕ,ζ={eEϕce>∑ipPi,Peζp}.

For all eEϕ,ζ, the capacity is ce,ζ=ce−∑ipPi|Peζp.

We will make use of the following lemma from [3].

Lemma 3.View the MathML source.

Proof. Lemma 3 can be easily proven by induction. See [3] for a proof. □

Using Lemma 3, we can transform a flow along path View the MathML source with value δ to the sum of a constant and a cubic posiform:It follows that the flow layer can be written as the sum of a constant — which is equal to the flow value — and a homogeneous cubic Boolean function, while the remaining graph layer corresponds to a homogeneous quadratic Boolean function.Suppose e=(u,v) is never saturated in any optimal symmetric multicommodity flow solution. Among all optimal solutions, consider those with the maximum number of vertices in the component containing v in the graph Gϕ,ζ, and among these solutions, let ζ be the one with the minimum ce,ζ. By our assumption on ζ, if we maintain the same total flow value, it will be impossible to expand the connected component containing v, and it is also impossible to decrease ce,ζwithout making the component containing v smaller. Suppose there exists an optimal assignment x withuv. Without loss of generality, we can assume that x assigns u=0 and v=1.Define S to be the set of vertices of the connected component containing v in the subgraph induced by vertices with value 1 according to x in Gϕ,ζ. We will show that changing the values of literals in S to 0, and their negations to 1, will give an assignment x such that View the MathML source, thus contradicting the hypothesis that x is an optimal assignment.Write the pseudo-Boolean function f as the sum of constant, cubic terms corresponding to the flow solution ζ, and quadratic terms corresponding to Gϕ,ζ. An easy observation is that setting the two endpoints of an edge to the same value will give the corresponding bi-term value 0. It is then easy to see that x will decrease the value of quadratic terms by at least ce,ζ. Now if we can show that changing from x to x will not increase the value of cubic terms, then we know that View the MathML source will be strictly less than View the MathML source.

Lemma 4. Given symmetric flow assignmentζ1, for pathpfromxitoView the MathML sourcewith flow value(ζ1)p>0, and vertexxjxi, ifxjorView the MathML sourceis onp, or there exists a simple pathpinGϕ,ζ1fromxjorView the MathML sourceto any vertex onp, we can get a flow assignmentζ2such that:

1.

ζ1andζ2have the same flow value,

2.

Eϕ,ζ1Eϕ,ζ2,

3.

ife=(u,v)belongs topbut notp,ζ2puts more flow onethanζ1does, andce,ζ2<ce,ζ1,

4.

ife=(u,v)is not inp,ce,ζ2ce,ζ1.

 

Proof. Since ζ1 is symmetric, a flow along path View the MathML source implies a flow along path View the MathML source with the same value. The two paths together will then form a generalized cycle, which we define to be a walk that starts and ends at the same vertex, but may traverse an edge more than once. If xj or View the MathML source is on p, we can cut the cycle into two possibly non-simple paths at xj and View the MathML source, then take some shortcuts to make the two paths simple. For example, consider

Then redistributing the flow as from u2 to View the MathML source will giveNotice that the redistribution operation may increase some edges’ remaining capacities. In the above example, the remaining capacities of c(xi,u1),ζ and View the MathML source are increased. If an edge is not on p, then its remaining capacity will not be increased.If there exists a simple path from xj or View the MathML source to some v on p, we only need to consider the first case, since by symmetry the second case will be equivalent to the first one if we switch p and ι(p). Without loss of generality, assume that the path pe from xj to v uses no edge on p or ι(p); otherwise we can take a different v and get a shorter pe. We can first redistribute the flow as from v to View the MathML source without increasing the remaining capacity of any edge on pe, then extend a small portion of the flow δ as from xj to View the MathML source using pe and ι(pe). If we make δ small enough, the redistribution will not saturate any edge on pe and ι(pe). □

 

Lemma 5. All paths involving vertices inSwith positive flow value must use the edge(u,v)orView the MathML source.

Proof. Suppose there is flow along p passing vS without using (u,v) and View the MathML source. Since there exist pathsuvv and View the MathML source in Gϕ,ζ, we know from Lemma 4 that we can get another optimal flow assignment without shrinking the connected component containing v, but decrease c(u,v),ζ, which contradicts our assumption about ζ. □

Lemma 5 implies that all flows involving the literals with different values in x and x are along paths using the (undirected) edge (u,v) or View the MathML source. Since p and ι(p) yield the same function terms, and p uses View the MathML sourceimplies ι(p) uses (u,v), we only need to prove that x will not increase the value of the cubic terms corresponding to the flow along paths using (u,v). Since all such paths use vertex u, we can redistribute the flows as from u to View the MathML source. We will no longer assume the minimality of c(u,v),ζ, since the redistribution may increase c(u,v),ζ.By Lemma 3, we know that the cubic terms corresponding to these flow paths all have the formwhich can be further reduced to quadratic terms by the assumption u=0:Consider any specific flow path. When we change x to x, there are only two cases in which the value of the above expression can be increased:The first case is v=1 in x, and v+1S. Then the term View the MathML source has value 0 according to x, but value 1 according to x. The second case is the symmetric counterpart of the first case, namely vι(S), and v+1=0 in x. If we can prove that the first case is impossible, by symmetry the second case is also impossible.Suppose we have the first case in the flow along path p. By the fact that v=1 in x, we know that vS. If vι(S), the edge (v,v+1) must be saturated, since otherwise there exists a path from u to View the MathML source in Gϕ,ζ, contradicting our assumption that ζis a maximum flow. If vι(S)v=1 in x, and by the definition of SvS implies that the edge(v,v+1) is saturated. Either way, (v,v+1) is saturated. Furthermore, since v+1 is in S, there exists a path from v to v+1 in Gϕ,ζ that does not use edge (v,v+1). Hence we can reroute some small enough portion of the original flow to use the alternative path from v to v+1, thus making the edge(v,v+1) unsaturated without changing the value of the flow solution. This will enlarge S to S∪{v}, contradicting the maximality of S.By the above discussion, we know that x won’t increase the value of the cubic terms, and will decrease the value of the quadratic terms by at least c(u,v),ζ. This contradicts the optimality of x, so u and v must have the same value in any optimal assignment. □

 

 

 

4.1. Persistencies and autarkies from single-commodity flows

 

Lemma 6. Any subset of a strong relational autarky is a strong relational persistency.

 

 

Proof. Suppose S is a subset of some strong relational autarky S. Consider any optimal assignment x. Since it is not possible to have f(x[Sb])<f(x), it must be the case that x assigns the same value to all literals in S. Since SS, all literals in S have the same value in all optimal assignments, which makes S a strong relational persistency. □

Consider any symmetric optimal solution ζ of the single-commodity maximum flow problem with source xsand sink View the MathML source on Gϕ. Using the same definition of Gϕ,ζ as in the proof of Theorem 2, let S denote the connected component containing xs in Gϕ,ζ.

 

 

 

Theorem 3. Sis a strong relational persistency of the corresponding pseudo-Boolean functionf. Conversely, ifUis a strong relational persistency containingxi, then there exists a symmetric optimal assignmentζof the single-commodity flow problem with source–sink pairView the MathML source, such thatUis completely contained in the connected component containingxiinGϕ,ζ.

 

 

 

Proof. We will start with the first part of the theorem. Notice that S contains at most one of xi and View the MathML source for all i, since otherwise symmetry implies a path from xs to View the MathML source in Gϕ,ζ.First consider the case when ζ is a maximum flow assignment such that the set S is maximal. If S has at most one element, then S is a strong relational autarky by definition. Otherwise, consider any assignment x, and assume that two literals in S have different values according to x. Let b=0. We shall prove f(x[Sb])<f(x), from which it follows that S is a strong relational autarky.Let K=Sι(S). Write f as the sum of a constant, cubic terms corresponding to flow solution ζ, and quadratic terms corresponding to Gϕ,ζ. We will show that in this expression for f, all terms involving literals in K will have value 0 according to x[Sb]. Consider any quadratic term involving literals inK. The term must correspond to edges in Gϕ,ζ whose endpoints are both in S or both in ι(S), since there is no edge between S and Vϕ,ζS. The term will vanish, since the endpoints of its corresponding edge are set to the same value in x[Sb].For the cubic terms, since all flows are from xs to View the MathML source, using Lemma 3, we know that the cubic terms all have the form

We have xs=b=0 in x[Sb], so the cubic terms can be reduced toConsider any term in the above formula involving variables in K. Like for the proof of Theorem 2, there are only two cases such that the term will not vanish. The first case is v=1, and v+1S. Then the term View the MathML source has value 1 according to x[Sb]. The second case is the symmetric counterpart of the first case, namely vι(S), and v+1=0. If we can prove that the first case is impossible, by symmetry the second case is also impossible. Using the same argument as in proof of Theorem 2, if the first case happens, we can expand S without changing the total flow value, thus contradicting the maximality of S. So all terms involving literals in K will vanish.S is a strong relational autarky for the following reason. Terms not using literals in K will have the same value with respect to x and x[Sb], and all terms using literals in K will vanish under x[Sb]. Moreover, since there exist two literals in S that are assigned different values by x, and the two literals are connected in Gϕ,ζ, at least one term using literals in K will not vanish under x, implying f(x[Sb])<f(x).Now consider an arbitrary maximum flow solution ζ without assuming S to be maximal. The only difference from the above case is that we can expand S by rerouting flows. It is clear that the new value of S after the expansion will be a superset of the former value of S. Thus starting from an arbitrary ζ and S, we can always get another maximum flow assignment ζ with a maximal S, and SS, where S is a strong relational autarky. By Lemma 6, we know that S is a strong relational persistency.Now we prove the second part of the theorem. Let ζ be the maximum single-commodity flow assignment with a maximal connected component containing xi, and denote the connected component by S. Recall that we assume U to be a strong relational persistency containingxi.The proof is by contradiction. Assuming US, we get a partition {U1,U2} of U where U2=US, and U1=USU2 is non-empty since US, and U1 is also non-empty since xiU1. By definition of strong relational persistency, literals in U1 and U2 must have the same value in all optimal assignments. Consider an optimal assignment x. We can assume that all literals in U1 and U2 have value 1 in x, since the bi-form will have the same function value if we negate all variables’ values. By the discussion from the first part of the proof, we know that x[S→0] must also be an optimal assignment, where literals inU1 have value 0, and literals in U2 have value 1. The optimality of x[S→0] contradicts the assumption that U is a strong relational persistency; thus US. □

 

Notice that if U is a strong relational persistency, then ι(U) is also a strong relational persistency, and they are semantically equivalent, so a strong relational persistency containing View the MathML source implies an equivalent strong relational persistency containing xiTheorem 3 then suggests that we can derive all strong relational persistencies by computing single-commodity maximum flows in Gϕ. The reverse direction ofTheorem 3 also suggests that if S={u,v} is derived from Theorem 2 as a strong relational persistency, then it can also be derived from Theorem 3 as a subset of a strong relational autarky.

 

 

 

Remark. The forward direction of Theorem 3 follows from remarks in [4], and the preprocessing code in [6]also applied the idea. The reverse direction is new, and guarantees that we can derive all strong relational persistencies using single-commodity maximum flows.

 

Acknowledgments

The authors wish to thank Ramin Zabih for introducing us to this topic and for providing valuable guidance along the way. We also thank Endre Boros for many valuable discussions and observations about our research and related work.

References

    • [1]
    • R.K. Ahuja, T.L. Magnanti, J.B. Orlin
    • Network Flows: Theory, Algorithms, and Applications

    • Prentice Hall (1993)

    • [3]
    • E. Boros, Y. Crama, P.L. Hammer
    • Chvatal cuts and odd cycle inequalities in quadratic 0-1 optimization

    • SIAM Journal on Discrete Mathematics, 5 (2) (1992), pp. 163–177

    • [4]
    • E. Boros, P.L. Hammer, A max-flow approach to improved roof-duality in quadratic 0-1 minimization, Research Report 15, Rutgers Center for Operations Research, Rutgers University, New Brunswick, NJ, 1989
    • [6]
    • E. Boros, P.L. Hammer, G. Tavares, Preprocessing of unconstrained quadratic binary optimization, Research Report 10, Rutgers Center for Operations Research, Rutgers University, New Brunswick, NJ, 2006
    • [7]
    • P. Felzenszwalb, R. Zabih, An overview of graph algorithms and dynamic programming in computer vision, IEEE Transactions in Pattern Analysis and Machine Intelligence, in press
Corresponding author contact information
Corresponding author. Tel.: +1 607 379 1538; fax: +1 607 255 4428.
1

Partially supported by NSF Grant IIS-0803705 and NIH Grant P41RR023953.

2

Supported by the National Science Foundation (grants CCF-0643934 and CCF-0729102), the Air Force Office of Scientific Research, an Alfred P. Sloan Foundation Fellowship, and a Microsoft Research New Faculty Fellowship.

3

Throughout this paper, we work with undirected graphs and make no distinction between a path and its reverse. In particular, a path from s to t is also a path from t to s.

Immediately related elementsHow this works
-
Machine Learning Methods & Algorithms »Machine Learning Methods & Algorithms
Others »Others
Quadratic unconstrained binary optimization (QUBO)
+Commentaires (0)
+Citations (0)
+About