ORIE Colloquium: Dorit Hochbaum (UC Berkeley)  Combinatorial algorithms for the Markov Random Fields problem and implications for ranking, clustering, group decision making and image segmentation
Tuesday, December 4, 2012 at 12:00pm
Frank H. T. Rhodes Hall, 253
One of the classical optimization models for image segmentation is the well known Markov Random Fields (MRF) model. The MRF problem involves minimizing pairwiseseparation and singletondeviation terms. This model is shown here to be powerful in representing classical problems of ranking, group decision making and clustering. The techniques presented are stronger than continuous techniques used in image segmentation, such as total variations, denoising, level sets and some classes of MumfordShah functionals. This is manifested both in terms of running time and in terms of quality of solution for the prescribed optimization problem
We present the first known efficient and flowbased, algorithms for the convex MRF (the nonconvex is shown to be NPhard). We then discuss the power of the MRF model and algorithms in the context of aggregate ranking. The aggregate ranking problem is to obtain a ranking that is fair and representative of the individual decision makers' rankings. We argue here that using cardinal pairwise comparisons provides several advantages over scorewise or ordinal models. The aggregate group ranking problem is formalized as the MRF model and is linked to the inverse equal paths problem. This combinatorial approach is shown to have advantages over other pairwisebased methods for ranking, such as PageRank and the principal eigenvector technique.
 Tags
