TY - JOUR
T1 - The maximum cut problem on blow-ups of multiprojective spaces
AU - Junca, Mauricio
AU - Velasco, Mauricio
PY - 2013/12
Y1 - 2013/12
N2 - The maximum cut problem for a quintic del Pezzo surface Bl 4(â FOR VERIFICATION ™2) asks: Among all partitions of the 10 exceptional curves into two disjoint sets, what is the largest possible number of pairwise intersections? In this article we show that the answer is 12. More generally, we obtain bounds for the maximum cut problem for the minuscule varieties X a,b,c :=Bl b+c ((™ c-1) a-1) studied by Mukai and Castravet-Tevelev and show that these bounds are asymptotically sharp for infinite families and exact in some cases. The key to our results is the fact that certain natural embeddings of the classes of (-1)-divisors on these varieties are optimal for the semidefinite relaxation of the maximum cut problem on graphs proposed by Goemans and Williamson. These results are a new optimality property of Weyl orbits of root systems of type A,D and E. Motivated by our results on the varieties X a,b,c we show that the Goemans-Williamson maxcut stochastic approximation algorithm has provably optimal asymptotic performance in symmetric strongly regular graphs of bounded spectra, in marked contrast with its worst-case behavior.
AB - The maximum cut problem for a quintic del Pezzo surface Bl 4(â FOR VERIFICATION ™2) asks: Among all partitions of the 10 exceptional curves into two disjoint sets, what is the largest possible number of pairwise intersections? In this article we show that the answer is 12. More generally, we obtain bounds for the maximum cut problem for the minuscule varieties X a,b,c :=Bl b+c ((™ c-1) a-1) studied by Mukai and Castravet-Tevelev and show that these bounds are asymptotically sharp for infinite families and exact in some cases. The key to our results is the fact that certain natural embeddings of the classes of (-1)-divisors on these varieties are optimal for the semidefinite relaxation of the maximum cut problem on graphs proposed by Goemans and Williamson. These results are a new optimality property of Weyl orbits of root systems of type A,D and E. Motivated by our results on the varieties X a,b,c we show that the Goemans-Williamson maxcut stochastic approximation algorithm has provably optimal asymptotic performance in symmetric strongly regular graphs of bounded spectra, in marked contrast with its worst-case behavior.
KW - Blow-ups of multiprojective space
KW - Goemans-Williamson algorithm
KW - Maximum cut problem
UR - http://www.scopus.com/inward/record.url?scp=84887249034&partnerID=8YFLogxK
U2 - 10.1007/s10801-013-0426-0
DO - 10.1007/s10801-013-0426-0
M3 - Artículo
AN - SCOPUS:84887249034
SN - 0925-9899
VL - 38
SP - 797
EP - 827
JO - Journal of Algebraic Combinatorics
JF - Journal of Algebraic Combinatorics
IS - 4
ER -