Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs.

Alistair Sinclair Piyush Srivastava Marc Thurley

Published in: SODA (2012)

Keyphrases

approximation algorithms
np hard
special case
minimum cost
vertex cover
undirected graph
open shop
randomized algorithms
graph theoretic
weighted graph
set cover
facility location problem
worst case
computational complexity
graph theory
incomplete information
linear programming
state space