@conference {Tourani2020,
	title = {Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy Minimization},
	booktitle = {AISTATS 2020},
	year = {2020},
	abstract = {We consider the maximum-a-posteriori inference problem in discrete graphical models and study solvers based on the dual block-coordinate ascent rule. We map all existing solvers in a single framework, allowing for a better understanding of their design principles. We theoretically show that some block-optimizing updates are sub-optimal and how to strictly improve them. On a wide range of problem instances of varying graph connec-tivity, we study the performance of existing solvers as well as new variants that can be obtained within the framework. As a result of this exploration we build a new state-of-the art solver, performing uniformly better on the whole range of test instances.},
	url = {https://gitlab.com/},
	author = {Tourani, Siddharth and Shekhovtsov, Alexander and Carsten Rother and Savchynskyy, Bogdan}
}
@article {Shekhovtsov2018,
	title = {Maximum Persistency via Iterative Relaxed Inference in Graphical Models},
	journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
	volume = {40},
	number = {7},
	year = {2018},
	pages = {1668{\textendash}1682},
	abstract = {We consider the NP-hard problem of MAP-inference for undirected discrete graphical models. We propose a polynomial time and practically efficient algorithm for finding a part of its optimal solution. Specifically, our algorithm marks some labels of the considered graphical model either as (i) optimal, meaning that they belong to all optimal solutions of the inference problem; (ii) non-optimal if they provably do not belong to any solution. With access to an exact solver of a linear programming relaxation to the MAP-inference problem, our algorithm marks the maximal possible (in a specified sense) number of labels. We also present a version of the algorithm, which has access to a suboptimal dual solver only and still can ensure the (non-)optimality for the marked labels, although the overall number of the marked labels may decrease. We propose an efficient implementation, which runs in time comparable to a single run of a suboptimal dual solver. Our method is well-scalable and shows state-of-the-art results on computational benchmarks from machine learning and computer vision.},
	keywords = {discrete optimization, energy minimization, graphical models, LP relaxation, partial optimality, persistency, WCSP},
	issn = {01628828},
	doi = {10.1109/TPAMI.2017.2730884},
	url = {http://www.icg.tugraz.at/},
	author = {Shekhovtsov, Alexander and Swoboda, Paul and Savchynskyy, Bogdan}
}
@conference {Tourani2018,
	title = {MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models},
	booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
	volume = {11208 LNCS},
	year = {2018},
	pages = {264{\textendash}281},
	abstract = {Dense, discrete Graphical Models with pairwise potentials are a powerful class of models which are employed in state-of-the-art computer vision and bio-imaging applications. This work introduces a new MAP-solver, based on the popular Dual Block-Coordinate Ascent principle. Surprisingly, by making a small change to a low-performing solver, the Max Product Linear Programming (MPLP) algorithm [7], we derive the new solver MPLP++ that significantly outperforms all existing solvers by a large margin, including the state-of-the-art solver Tree-Reweighted Sequential (TRW-S) message-passing algorithm [17]. Additionally, our solver is highly parallel, in contrast to TRW-S, which gives a further boost in performance with the proposed GPU and multi-thread CPU implementations. We verify the superiority of our algorithm on dense problems from publicly available benchmarks as well as a new benchmark for 6D Object Pose estimation. We also provide an ablation study with respect to graph density.},
	keywords = {Block-Coordinate-Ascent, graphical models, Message passing algorithms},
	isbn = {9783030012243},
	issn = {16113349},
	doi = {10.1007/978-3-030-01225-0_16},
	author = {Tourani, Siddharth and Shekhovtsov, Alexander and Carsten Rother and Savchynskyy, Bogdan}
}
@article {Swoboda2016,
	title = {Partial Optimality by Pruning for MAP-Inference with General Graphical Models},
	journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
	volume = {38},
	number = {7},
	year = {2016},
	month = {jul},
	pages = {1370{\textendash}1382},
	publisher = {IEEE Computer Society},
	abstract = {We consider the energy minimization problem for undirected graphical models, also known as MAP-inference problem for Markov random fields which is NP-hard in general. We propose a novel polynomial time algorithm to obtain a part of its optimal non-relaxed integral solution. Our algorithm is initialized with variables taking integral values in the solution of a convex relaxation of the MAP-inference problem and iteratively prunes those, which do not satisfy our criterion for partial optimality. We show that our pruning strategy is in a certain sense theoretically optimal. Also empirically our method outperforms previous approaches in terms of the number of persistently labelled variables. The method is very general, as it is applicable to models with arbitrary factors of an arbitrary order and can employ any solver for the considered relaxed problem. Our method{\textquoteright}s runtime is determined by the runtime of the convex relaxation solver for the MAP-inference problem.},
	keywords = {energy minimization, Local polytope, MAP-inference, Markov random fields, partial optimality, persistency},
	issn = {01628828},
	doi = {10.1109/TPAMI.2015.2484327},
	author = {Swoboda, Paul and Shekhovtsov, Alexander and Kappes, Jorg Hendrik and Christoph Schn{\"o}rr and Savchynskyy, Bogdan}
}
@conference {Shekhovtsov2012,
	title = {Curvature prior for MRF-based segmentation and shape inpainting},
	booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
	volume = {7476 LNCS},
	year = {2012},
	pages = {41{\textendash}51},
	abstract = {Most image labeling problems such as segmentation and image reconstruction are fundamentally ill-posed and suffer from ambiguities and noise. Higher-order image priors encode high-level structural dependencies between pixels and are key to overcoming these problems. However, in general these priors lead to computationally intractable models. This paper addresses the problem of discovering compact representations of higher-order priors which allow efficient inference. We propose a framework for solving this problem that uses a recently proposed representation of higher-order functions which are encoded as lower envelopes of linear functions. Maximum a Posterior inference on our learned models reduces to minimizing a pairwise function of discrete variables. We show that our framework can learn a compact representation that approximates a low curvature shape prior and demonstrate its effectiveness in solving shape inpainting and image segmentation problems. {\textcopyright} 2012 Springer-Verlag.},
	isbn = {9783642327162},
	issn = {03029743},
	doi = {10.1007/978-3-642-32717-9_5},
	author = {Shekhovtsov, Alexander and Kohli, Pushmeet and Carsten Rother}
}
@conference {Shekhovtsov2012a,
	title = {Curvature prior for MRF-based segmentation and shape inpainting},
	booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
	volume = {7476 LNCS},
	year = {2012},
	pages = {41{\textendash}51},
	abstract = {Most image labeling problems such as segmentation and image reconstruction are fundamentally ill-posed and suffer from ambiguities and noise. Higher-order image priors encode high-level structural dependencies between pixels and are key to overcoming these problems. However, in general these priors lead to computationally intractable models. This paper addresses the problem of discovering compact representations of higher-order priors which allow efficient inference. We propose a framework for solving this problem that uses a recently proposed representation of higher-order functions which are encoded as lower envelopes of linear functions. Maximum a Posterior inference on our learned models reduces to minimizing a pairwise function of discrete variables. We show that our framework can learn a compact representation that approximates a low curvature shape prior and demonstrate its effectiveness in solving shape inpainting and image segmentation problems. {\textcopyright} 2012 Springer-Verlag.},
	isbn = {9783642327162},
	issn = {03029743},
	doi = {10.1007/978-3-642-32717-9_5},
	url = {www.research.microsoft.com/vision/cambridge http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/papers/StereoSegmentation_PAMI06.pdf\%5Cnpapers3://publication/uuid/F008E9F4-510D-4478-A3C0-1BFB22F6AEA0},
	author = {Shekhovtsov, Alexander and Kohli, Pushmeet and Carsten Rother}
}
@conference {Shekhovtsov2012b,
	title = {Curvature prior for MRF-based segmentation and shape inpainting},
	booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
	volume = {7476 LNCS},
	year = {2012},
	month = {sep},
	pages = {41{\textendash}51},
	abstract = {Most image labeling problems such as segmentation and image reconstruction are fundamentally ill-posed and suffer from ambiguities and noise. Higher-order image priors encode high-level structural dependencies between pixels and are key to overcoming these problems. However, in general these priors lead to computationally intractable models. This paper addresses the problem of discovering compact representations of higher-order priors which allow efficient inference. We propose a framework for solving this problem that uses a recently proposed representation of higher-order functions which are encoded as lower envelopes of linear functions. Maximum a Posterior inference on our learned models reduces to minimizing a pairwise function of discrete variables. We show that our framework can learn a compact representation that approximates a low curvature shape prior and demonstrate its effectiveness in solving shape inpainting and image segmentation problems. {\textcopyright} 2012 Springer-Verlag.},
	isbn = {9783642327162},
	issn = {03029743},
	doi = {10.1007/978-3-642-32717-9_5},
	url = {http://arxiv.org/abs/1109.1480},
	author = {Shekhovtsov, Alexander and Kohli, Pushmeet and Carsten Rother}
}
@conference {Kohli2008,
	title = {On partial optimality in multi-label MRFs},
	booktitle = {Proceedings of the 25th International Conference on Machine Learning},
	year = {2008},
	pages = {480{\textendash}487},
	abstract = {We consider the problem of optimizing multilabel MRFs, which is in general NP-hard and ubiquitous in low-level computer vision. One approach for its solution is to formulate it as an integer linear programming and relax the integrality constraints. The approach we consider in this paper is to first convert the multi-label MRF into an equivalent binary-label MRF and then to relax it. The resulting relaxation can be efficiently solved using a maximum flow algorithm. Its solution provides us with a partially optimal labelling of the binary variables. This partial labelling is then easily transferred to the multi-label problem. We study the theoretical properties of the new relaxation and compare it with the standard one. Specifically, we compare tightness, and characterize a subclass of problems where the two relaxations coincide. We propose several combined algorithms based on the technique and demonstrate their performance on challenging computer vision problems. Copyright 2008 by the author(s)/owner(s).},
	isbn = {9781605582054},
	doi = {10.1145/1390156.1390217},
	author = {Kohli, Pushmeet and Shekhovtsov, Alexander and Carsten Rother and Kolmogorov, Vladimir and Torr, Philip}
}
