nips nips2010 nips2010-102 nips2010-102-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Vladimir Kolmogorov
Abstract: ˆ Consider a convex relaxation f of a pseudo-boolean function f . We say that ˆ the relaxation is totally half-integral if f (x) is a polyhedral function with halfintegral extreme points x, and this property is preserved after adding an arbitrary combination of constraints of the form xi = xj , xi = 1 − xj , and xi = γ where 1 γ ∈ {0, 1, 2 } is a constant. A well-known example is the roof duality relaxation for quadratic pseudo-boolean functions f . We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-boolean functions. Our contributions are as follows. First, we provide a complete characterization ˆ of totally half-integral relaxations f by establishing a one-to-one correspondence with bisubmodular functions. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality. 1
[1] Asem M. Ali, Aly A. Farag, and Georgy L. Gimel’Farb. Optimizing binary MRFs with higher order cliques. In ECCV, 2008.
[2] Kazutoshi Ando, Satoru Fujishige, and Takeshi Naitoh. A characterization of bisubmodular functions. Discrete Mathematics, 148:299–303, 1996.
[3] M. L. Balinski. Integer programming: Methods, uses, computation. Management Science, 12(3):253– 313, 1965. 8
[4] E. Boros and P. L. Hammer. Pseudo-boolean optimization. Discrete Applied Mathematics, 123(1-3):155 – 225, November 2002.
[5] E. Boros, P. L. Hammer, and X. Sun. Network flows and minimization of quadratic pseudo-Boolean functions. Technical Report RRR 17-1991, RUTCOR, May 1991.
[6] E. Boros, P. L. Hammer, and G. Tavares. Preprocessing of unconstrained quadratic binary optimization. Technical Report RRR 10-2006, RUTCOR, 2006.
[7] A. Bouchet. Greedy algorithm and symmetric matroids. Math. Programming, 38:147–159, 1987.
[8] A. Bouchet and W. H. Cunningham. Delta-matroids, jump systems and bisubmodular polyhedra. SIAM J. Discrete Math., 8:17–32, 1995.
[9] Y. Boykov, O. Veksler, and R. Zabih. Fast approximate energy minimization via graph cuts. PAMI, 23(11), November 2001.
[10] R. Chandrasekaran and Santosh N. Kabadi. Pseudomatroids. Discrete Math., 71:205–217, 1988.
[11] S Fujishige. Submodular Functions and Optimization. North-Holland, 1991.
[12] Satoru Fujishige and Satoru Iwata. Bisubmodular function minimization. SIAM J. Discrete Math., 19(4):1065–1073, 2006.
[13] P. L. Hammer, P. Hansen, and B. Simeone. Roof duality, complementation and persistency in quadratic 0-1 optimization. Mathematical Programming, 28:121–155, 1984.
[14] D. Hochbaum. Instant recognition of half integrality and 2-approximations. In 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization, 1998.
[15] D. Hochbaum. Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations. European Journal of Operational Research, 140(2):291–321, 2002.
[16] H. Ishikawa. Higher-order clique reduction in binary graph cut. In CVPR, 2009.
[17] H. Ishikawa. Higher-order gradient descent by fusion-move graph cut. In ICCV, 2009.
[18] Satoru Iwata and Kiyohito Nagano. Submodular function minimization under covering constraints. In FOCS, October 2009.
[19] Santosh N. Kabadi and R. Chandrasekaran. On totally dual integral systems. Discrete Appl. Math., 26:87–104, 1990.
[20] V. Kolmogorov. Generalized roof duality and bisubmodular functions. Technical Report arXiv:1005.2305v2, September 2010.
[21] V. Kolmogorov. Minimizing a sum of submodular functions. Technical Report arXiv:1006.1990v1, June 2010.
[22] V. Kolmogorov. Submodularity on a tree: Unifying L -convex and bisubmodular functions. Technical Report arXiv:1007.1229v2, July 2010.
[23] Victor Lempitsky, Carsten Rother, and Andrew Blake. LogCut - efficient graph cut optimization for Markov random fields. In ICCV, 2007.
[24] Victor Lempitsky, Carsten Rother, Stefan Roth, and Andrew Blake. Fusion moves for Markov random field optimization. PAMI, July 2009.
[25] S. H. Lu and A. C. Williams. Roof duality for polynomial 0-1 optimization. Math. Programming, 37(3):357–360, 1987.
[26] S. Thomas McCormick and Satoru Fujishige. Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization. Math. Program., Ser. A, 122:87–120, 2010.
[27] M. Nakamura. A characterization of greedy sets: universal polymatroids (I). In Scientific Papers of the College of Arts and Sciences, volume 38(2), pages 155–167. The University of Tokyo, 1998.
[28] G. L. Nemhauser and L. E. Trotter. Vertex packings: Structural properties and algorithms. Mathematical Programming, 8:232–248, 1975.
[29] Liqun Qi. Directed submodularity, ditroids and directed submodular flows. Mathematical Programming, 42:579–599, 1988.
[30] A. Raj, G. Singh, and R. Zabih. MRF’s for MRI’s: Bayesian reconstruction of MR images via graph cuts. In CVPR, 2006.
[31] Stefan Roth and Michael J. Black. Fields of experts. IJCV, 82(2):205–229, 2009.
[32] C. Rother, V. Kolmogorov, V. Lempitsky, and M. Szummer. Optimizing binary MRFs via extended roof duality. In CVPR, June 2007.
[33] O. Woodford, P. Torr, I. Reid, and A. Fitzgibbon. Global stereo reconstruction under second order smoothness priors. In CVPR, 2008. 9