Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Generalized Roof Duality for Pseudo-Boolean Optimization

Kahl, Fredrik LU and Strandmark, Petter LU (2011) IEEE International Conference on Computer Vision (ICCV), 2011 p.255-262
Abstract
The number of applications in computer vision that model higher-order interactions has exploded over the last few years. The standard technique for solving such problems is to reduce the higher-order objective function to a quadratic pseudo-boolean function, and then use roof duality for obtaining a lower bound. Roof duality works by constructing the tightest possible lower-bounding submodular function, and instead of optimizing the original objective function, the relaxation is minimized.

We generalize this idea to polynomials of higher degree, where quadratic roof duality appears as a special case. Optimal relaxations are defined to be the ones that give the maximum lower bound. We demonstrate that important properties such as... (More)
The number of applications in computer vision that model higher-order interactions has exploded over the last few years. The standard technique for solving such problems is to reduce the higher-order objective function to a quadratic pseudo-boolean function, and then use roof duality for obtaining a lower bound. Roof duality works by constructing the tightest possible lower-bounding submodular function, and instead of optimizing the original objective function, the relaxation is minimized.

We generalize this idea to polynomials of higher degree, where quadratic roof duality appears as a special case. Optimal relaxations are defined to be the ones that give the maximum lower bound. We demonstrate that important properties such as persistency still hold and how the relaxations can be efficiently constructed for general cubic and quartic pseudo-boolean functions. From a practical point of view, we show that our relaxations perform better than state-of-the-art for a wide range of problems, both in terms of lower bounds and in the number of assigned variables. (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
IEEE International Conference on Computer Vision (ICCV)
pages
8 pages
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
conference name
IEEE International Conference on Computer Vision (ICCV), 2011
conference location
Barcelona, Spain
conference dates
2011-11-06 - 2011-11-13
external identifiers
  • wos:000300061900033
  • scopus:84856686367
DOI
10.1109/ICCV.2011.6126250
language
English
LU publication?
yes
id
edc225e6-2f9b-41f9-b0c9-630389f1491b (old id 2225996)
date added to LUP
2016-04-04 10:51:23
date last changed
2022-01-29 20:58:30
@inproceedings{edc225e6-2f9b-41f9-b0c9-630389f1491b,
  abstract     = {{The number of applications in computer vision that model higher-order interactions has exploded over the last few years. The standard technique for solving such problems is to reduce the higher-order objective function to a quadratic pseudo-boolean function, and then use roof duality for obtaining a lower bound. Roof duality works by constructing the tightest possible lower-bounding submodular function, and instead of optimizing the original objective function, the relaxation is minimized. <br/><br>
We generalize this idea to polynomials of higher degree, where quadratic roof duality appears as a special case. Optimal relaxations are defined to be the ones that give the maximum lower bound. We demonstrate that important properties such as persistency still hold and how the relaxations can be efficiently constructed for general cubic and quartic pseudo-boolean functions. From a practical point of view, we show that our relaxations perform better than state-of-the-art for a wide range of problems, both in terms of lower bounds and in the number of assigned variables.}},
  author       = {{Kahl, Fredrik and Strandmark, Petter}},
  booktitle    = {{IEEE International Conference on Computer Vision (ICCV)}},
  language     = {{eng}},
  pages        = {{255--262}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  title        = {{Generalized Roof Duality for Pseudo-Boolean Optimization}},
  url          = {{http://dx.doi.org/10.1109/ICCV.2011.6126250}},
  doi          = {{10.1109/ICCV.2011.6126250}},
  year         = {{2011}},
}