Generalized roof duality

DOI10.1016/J.DAM.2012.06.009MaRDI QIDQ714031zbMATHOpenAlexFDO

Authors Fredrik Kahl, Petter Strandmark

Publication date 19 October 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2012.06.009

zbMATH Keywords

computer visionhigher-orderroof dualityMRF

Mathematics Subject Classification ID

Nonlinear programming (90C30) Boolean programming (90C09)

Recommendations

• A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Generalized roof duality and bisubmodular functions
• On the equivalence between roof duality and Lagrangian duality for unconstrained \(0\)-\(1\) quadratic programming problems
• Persistency in quadratic 0-1 optimization

Cites work

• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
• A linear framework for region-based image segmentation and inpainting involving curvature penalization
• Bisubmodular Function Minimization
• Classes of submodular constraints expressible by graph cuts
• Generalized roof duality
• Generalized roof duality and bisubmodular functions
• Global interactions in random field models: a potential function ensuring connectedness
• Inference methods for CRFs with co-occurrence statistics
• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
• One-pass heuristics for large-scale unconstrained binary quadratic problems
• Persistency in quadratic 0-1 optimization
• Pseudo-Boolean optimization
• Recognition problems for special classes of polynomials in 0-1 variables
• Roof duality for polynomial 0–1 optimization
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• SATLIB: An online resource for research on SAT
• Supermodular functions on finite lattices
• The expressive power of binary submodular functions

Cited in

(4)

• Generalized roof duality
• Generalized roof duality and bisubmodular functions
• Quadratic reformulations of nonlinear binary optimization problems
• scientific article; zbMATH DE number 4114373 (Why is no real title available?)

Describes a project that uses

Uses Software

• SATLIB

This page was built for publication: Generalized roof duality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714031)