solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看113次
Algorithms for #BIS-hard problems on expander graphs. (arXiv:1807.04804v1 [cs.DS])
来源于:arXiv
We give an FPTAS and an efficient sampling algorithm for the high-fugacity
hard-core model on bounded-degree bipartite expander graphs and the
low-temperature ferromagnetic Potts model on bounded-degree expander graphs.
The results apply, for example, to random (bipartite) $\Delta$-regular graphs,
for which no efficient algorithms were known for these problems (with the
exception of the Ising model) in the non-uniqueness regime of the infinite
$\Delta$-regular tree. 查看全文>>