The maximum cut problem on blow-ups of multiprojective spaces

DOI10.1007/s10801-013-0426-0zbMath1290.14034arXiv1207.4027MaRDI QIDQ2435039

Mauricio Velasco, Mauricio Junca

Publication date: 3 February 2014

Published in: Journal of Algebraic Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1207.4027

zbMATH Keywords

Goemans-Williamson algorithm; maximum cut problem; blow-ups of multiprojective space

Mathematics Subject Classification ID

14C17: Intersection theory, characteristic classes, intersection multiplicities in algebraic geometry

05C85: Graph algorithms (graph-theoretic aspects)

14N05: Projective techniques in algebraic geometry

05C22: Signed and weighted graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Blow-ups of \(\mathbb{P}^{n-3}\) at \(n\) points and spinor varieties
• Sagbi bases of Cox-Nagata rings
• Del Pezzo surfaces and representation theory
• Strongly regular graphs with smallest eigenvalue -m
• Coxeter matroids. With illustrations by Anna Borovik
• Hilbert's 14th problem and Cox rings
• On the equations for universal torsors over del Pezzo surfaces
• How Good is the Goemans--Williamson MAX CUT Algorithm?
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?