Linear-programming design and analysis of fast algorithms for Max 2-CSP

DOI10.1016/j.disopt.2007.08.001zbMath1153.90505MaRDI QIDQ2427689

Gregory B. Sorkin, Alexander D. Scott

Publication date: 14 May 2008

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2007.08.001

zbMATH Keywords

exact algorithms; measure and conquer; Max 2-CSP; Max cut; linear-programming duality; Max 2-sat

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

90C05: Linear programming

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Uses Software

• MAX-2-SAT