Roof duality, complementation and persistency in quadratic 0–1 optimization

By Peter Ladislaw Hammer, Pierre Hansen, B. Simeone. 1984

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Learning human activities and object affordances from RGB-D videos (2012, background): “elaxing the variables zlk ij and yl i to the interval [0;1] results in a linear program that can be shown to always have half-integral solutions (i.e. yl i only take values f0;0:5;1gat the solution) (Hammer et al., 1984). Since every node in our experiments has exactly one class label, we also consi”
Anticipating Human Activities Using Object Affordances for Reactive Robotic Response (2013, background): “Relaxing the variables z lk ij and y l i to the interval ½0; 1 results in a linear program that can be shown to always have half-integral solutions (i.e. y l i only take values f0; 0:5; 1g at the solution) [80].”
Minimizing Nonsubmodular Functions with Graph Cuts-A Review (2007, methodology): “Algorithms in [19] and [10] compute the same answer, but the latter is more efficient.”
A Linear Programming Approach to Max-Sum Problem: A Review (2007, background): “In addition, both noticed that, for Boolean variables, at least one relaxed labeling is half-integral; an analogical observation was made in pseudo-Boolean optimization [18], referring to [58].”
Contextually Guided Semantic Labeling and Search for 3D Point Clouds (2011, background): “The relaxation solution ˆ y cut has an interesting property called Persistence (Boros and Hammer, 2002; Hammer et al., 1984).”
Pseudo-Boolean optimization (2002, methodology): “There are several examples for persistency observed in the literature, including both weak and strong persistency for quadratic pseudo-Boolean functions [79], weak persistency in an integer programming formulation of vertex covering [129], etc.”
Semantic Labeling of 3D Point Clouds for Indoor Scenes (2011, background): “The relaxation solution ŷcut has an interesting property called Persistence [2, 10].”
Graph cut based image segmentation with connectivity priors (2008, background): “Instead of restricting function E to be submodular, one could use the roof duality approach [8] to get a lower bound on E(x | θ).”
Contextually guided semantic labeling and search for three-dimensional point clouds (2013, background): “Persistence says that any segment for which the value of yli is integral in ŷcut (i.e., does not take value 0.5) is labeled just like it would be in the optimal mixed-integer solution.”
Predicting Failures of Vision Systems (2014, background): “Predicting failures: Optimization algorithms can often detect when they have found the global optimum [52] or can indicate for which variables they are failing to find optimal assignments [22] [44].”
Handbook of Semidefinite Programming (2000, background): “[351], where many bounds obtained from various linearizations have been shown to be equal and, in fact, they have been shown to be equal to the Lagrangian dual of a linearized problem, see [4].”
Human Activity Learning using Object Affordances from RGB-D Videos (2012, unknown): “5 , 1 } at the solution) [28].”
A convex relaxation approach for computing minimal partitions (2009, background): “They can only be solved approximately either by transforming the problem to a sequence of binary labeling problems [5, 28], via various linear programming relaxations [3, 29] or via roof duality relaxation [16] which has recently attracted renewed interest in the MRF community (cf.”
Higher-order clique reduction in binary graph cut (2009, methodology): “Although it is not a solution to every problem, the QPBO technique often allows solving a non-submodular problem approximately by giving a large enough part of the globally optimal move to iteratively improve the solution.”