@Article{Flach:TPAMI2013, IS = { zkontrolovano 16 Aug 2013 }, UPDATE = { 2013-08-16 }, author = {Boris Flach}, title = {A Class of Random Fields on Complete Graphs with Tractable Partition Function}, year = {2013}, month = {September}, pages = {2304-2306}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA 90720, USA}, issn = {0162-8828}, volume = {35}, number = {9}, annote = {The aim of this short note is to draw attention to a method by which the partition function and marginal probabilities for a certain class of random fields on complete graphs can be computed in polynomial time. This class includes Ising models with homogeneous pairwise potentials but arbitrary (inhomogeneous) unary potentials. Similarly, the partition function and marginal probabilities can be computed in polynomial time for random fields on complete bipartite graphs, provided they have homogeneous pairwise potentials. We expect that these tractable classes of large scale random fields can be very useful for the evaluation of approximation algorithms by providing exact error estimates.}, keywords = {approximation theory;computational complexity;graph theory;probability;approximation algorithm;complete bipartite graph;error estimation;homogeneous pairwise potential;marginal probability;polynomial time complexity;random field;tractable partition function;Markov random fields}, project = {GAP202/12/2071}, doi = {10.1109/TPAMI.2013.99}, }