ProV Logo
0
Approximate MAP Estimation for Pairwise ...
Wang, Yi-Kai...

Free

Approximate MAP Estimation for Pairwise Potentials via Baker's Technique by Wang, Yi-Kai ( Author )
Lemonjar Open Access
Australian National University
06-09-2023
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.
-
Article
pdf
29.34 KB
English
-
MYR 0.01
-
http://arxiv.org/abs/1412.0340
Share this eBook