Approximate MAP Estimation for Pairwise Potentials via Baker's Technique

2014/12/01 by Wang, Yi-Kai
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1412.0340

Abstract

The theoretical models providing mathematical abstractions for several significant optimization problems in machine learning, combinatorial optimization, computer vision and statistical physics have intrinsic similarities. We propose a unified framework to model these computation tasks where the structures of these optimization problems are encoded by functions attached on the vertices and edges of a graph. We show that computing MAX 2-CSP admits polynomial-time approximation scheme (PTAS) on planar graphs, graphs with bounded local treewidth, H-minor-free graphs, geometric graphs with bounded density and graphs embeddable with bounded number of crossings per edge. This implies computing MAX-CUT, MAX-DICUT and MAX k-CUT admits PTASs on all these classes of graphs. Our method also gives the first PTAS for computing the ground state of ferromagnetic Edwards-Anderson model without external magnetic field on d-dimensional lattice graphs. These results are widely applicable in vision, graphics and machine learning.

Related

• Graph cuts always find a global optimum for Potts models (with a catch)
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Baker game and polynomial-time approximation schemes
• Improved Combinatorial Approximation Algorithms for MAX CUT in Sparse Graphs
• A Max-Cut approximation using a graph based MBO scheme