@inproceedings{2275, abstract = {Energies with high-order non-submodular interactions have been shown to be very useful in vision due to their high modeling power. Optimization of such energies, however, is generally NP-hard. A naive approach that works for small problem instances is exhaustive search, that is, enumeration of all possible labelings of the underlying graph. We propose a general minimization approach for large graphs based on enumeration of labelings of certain small patches. This partial enumeration technique reduces complex high-order energy formulations to pairwise Constraint Satisfaction Problems with unary costs (uCSP), which can be efficiently solved using standard methods like TRW-S. Our approach outperforms a number of existing state-of-the-art algorithms on well known difficult problems (e.g. curvature regularization, stereo, deconvolution); it gives near global minimum and better speed. Our main application of interest is curvature regularization. In the context of segmentation, our partial enumeration technique allows to evaluate curvature directly on small patches using a novel integral geometry approach. }, author = {Olsson, Carl and Ulen, Johannes and Boykov, Yuri and Kolmogorov, Vladimir}, location = {Sydney, Australia}, pages = {2936 -- 2943}, publisher = {IEEE}, title = {{Partial enumeration and curvature regularization}}, doi = {10.1109/ICCV.2013.365}, year = {2014}, } @techreport{7038, author = {Huszár, Kristóf and Rolinek, Michal}, pages = {5}, publisher = {IST Austria}, title = {{Playful Math - An introduction to mathematical games}}, year = {2014}, } @inproceedings{2270, abstract = {Representation languages for coalitional games are a key research area in algorithmic game theory. There is an inher- ent tradeoff between how general a language is, allowing it to capture more elaborate games, and how hard it is computationally to optimize and solve such games. One prominent such language is the simple yet expressive Weighted Graph Games (WGGs) representation (Deng and Papadimitriou 1994), which maintains knowledge about synergies between agents in the form of an edge weighted graph. We consider the problem of finding the optimal coalition structure in WGGs. The agents in such games are vertices in a graph, and the value of a coalition is the sum of the weights of the edges present between coalition members. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that finding the optimal coalition structure is not only hard for general graphs, but is also intractable for restricted families such as planar graphs which are amenable for many other combinatorial problems. We then provide algorithms with constant factor approximations for planar, minorfree and bounded degree graphs.}, author = {Bachrach, Yoram and Kohli, Pushmeet and Kolmogorov, Vladimir and Zadimoghaddam, Morteza}, location = {Bellevue, WA, United States}, pages = {81--87}, publisher = {AAAI Press}, title = {{Optimal Coalition Structures in Cooperative Graph Games}}, year = {2013}, } @techreport{2273, abstract = {We propose a new family of message passing techniques for MAP estimation in graphical models which we call Sequential Reweighted Message Passing (SRMP). Special cases include well-known techniques such as Min-Sum Diusion (MSD) and a faster Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not involve a decomposition into trees. This allows easy generalizations. We present such a generalization for the case of higher-order graphical models, and test it on several real-world problems with promising results.}, author = {Vladimir Kolmogorov}, publisher = {IST Austria}, title = {{Reweighted message passing revisited}}, year = {2013}, } @inproceedings{2276, abstract = {The problem of minimizing the Potts energy function frequently occurs in computer vision applications. One way to tackle this NP-hard problem was proposed by Kovtun [19, 20]. It identifies a part of an optimal solution by running k maxflow computations, where k is the number of labels. The number of “labeled” pixels can be significant in some applications, e.g. 50-93% in our tests for stereo. We show how to reduce the runtime to O (log k) maxflow computations (or one parametric maxflow computation). Furthermore, the output of our algorithm allows to speed-up the subsequent alpha expansion for the unlabeled part, or can be used as it is for time-critical applications. To derive our technique, we generalize the algorithm of Felzenszwalb et al. [7] for Tree Metrics . We also show a connection to k-submodular functions from combinatorial optimization, and discuss k-submodular relaxations for general energy functions.}, author = {Gridchyn, Igor and Kolmogorov, Vladimir}, location = {Sydney, Australia}, pages = {2320 -- 2327}, publisher = {IEEE}, title = {{Potts model, parametric maxflow and k-submodular functions}}, doi = {10.1109/ICCV.2013.288}, year = {2013}, }