Generalized Roof Duality: Experiments

This is a follow-up to the previous post about generalized roof duality and will contain some experimental results.

We have performed experiments with polynomials of degree 3 and 4. While these two cases are very similar in concept, implementing the degree 3 case is considerably easier.

ICCV 2011: Generalized Roof Duality

Fredrik Kahl and I have a paper accepted to ICCV titled Generalized Roof Duality for Pseudo-Boolean Optimization.

Just as in the previous post, the problem of interest is to minimize degree- polynomials of the form:

The previous post showed that many different reductions to the quadratic case are possible. Our paper describes a generalization of roof duality which does not rely on reductions and is in a suitable sense optimal.

Reductions in Pseudo-Boolean Optimization

This post is about reduction methods in pseudo-Boolean optimization and a recent paper to appear at CVPR 2011.