anti-ferromagnetic:B 1 bounded△or△=o Ju(x)= (》 d<△，f(元d)川<1 3FPTAS for graphs of max-degree A [Sly-Sun'12][Galanis-Stefankovic-Vigoda'12] 3d<△，fa(td)川>1 assuming NP≠RP 肀FPRAS for graphs of max--degree△anti-ferromagnetic: ￾￾ < 1 ∃ FPTAS for graphs of max-degree Δ ∄ FPRAS for graphs of max-degree Δ assuming NP ≠RP [Sly-Sun’12] [Galanis-Stefankovic-Vigoda’12]: bounded Δ or Δ=∞ ￾d < ￾, |f￾ d(ˆxd)| < 1 ￾d < ￾, |f￾ d(ˆxd)| > 1 fd(x) = ￾ ￾￾x + 1 x + ￾ ￾d