Generalized Roof Duality for Pseudo-Boolean Optimization
Författare
Summary, in English
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.
Avdelning/ar
- Matematik LTH
- Mathematical Imaging Group
- ELLIIT: the Linköping-Lund initiative on IT and mobile communication
Publiceringsår
2011
Språk
Engelska
Sidor
255-262
Publikation/Tidskrift/Serie
IEEE International Conference on Computer Vision (ICCV)
Dokumenttyp
Konferensbidrag
Förlag
IEEE - Institute of Electrical and Electronics Engineers Inc.
Ämne
- Computer Vision and Robotics (Autonomous Systems)
- Mathematics
Conference name
IEEE International Conference on Computer Vision (ICCV), 2011
Conference date
2011-11-06 - 2011-11-13
Conference place
Barcelona, Spain
Status
Published
Forskningsgrupp
- Mathematical Imaging Group