|
%I #29 Aug 22 2015 20:13:01
%S 8,7,8,5,6,7,2,0,5,7,8,4,8,5,1,6,0,4,2,1,7,3,0,1,0,3,3,6,7,7,6,2,0,8,
%T 8,8,8,2,0,9,9,0,4,7,1,0,8,1,5,5,9,0,8,4,6,5,6,1,9,7,1,0,3,1,6,8,2,2,
%U 8,3,7,0,8,7,7,4,8,4,4,9,0,1,9,8,5,9,3,7,9,7,0,6,2,5,9,2,8,7,7,0,6,3,6,8,2
%N Decimal expansion of alpha_GW, a constant arising in Max Cut algorithm of Goemans and Williamson.
%C Goemans and Williamson: There is a polynomial-time algorithm that, given as input a graph G=(V,E), finds a bipartition that cuts at least alpha_GW*opt edges, where opt is the number of edges cut by an optimal bipartition of G (from p. 97 of Trevisan).
%C On the Unique Games Conjecture, a Turing machine can approximate the Max Cut problem in polynomial time with a better approximation ratio if and only if P = NP. - _Charles R Greathouse IV_, Mar 06 2014
%H M. X. Goemans and D. P. Williamson, <a href="http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf">Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming</a>, JACM 42 (1995), no. 6, 1115-1145.
%H L. Trevisan, <a href="http://dx.doi.org/10.1090/S0273-0979-2011-01361-1">On Khot's unique games conjecture</a>, Bull. Amer. Math. Soc. 49 (2012), 91-111.
%F alpha_GW = min_{1/2 < rho < 1} 1/Pi * arccos(1-2*rho)/rho.
%e 0.878567205784851604217301...
%p nmax:= 105: Digits:= nmax+15:
%p f:= rho-> arccos(1-2*rho)/(Pi*rho):
%p s:= convert(evalf(f(fsolve(D(f)(x), x=1/2..1))), string):
%p seq(parse(s[n+1]), n=1..nmax); # _Alois P. Heinz_, Jan 08 2012
%t digits = 105; FindMinimum[1/Pi*ArcCos[1-2*rho]/rho, {rho, 4/5}, WorkingPrecision -> digits+1] // First // RealDigits[#, 10, digits]& // First (* _Jean-François Alcover_, Feb 20 2014 *)
%o (PARI) (x->2*x/(Pi*(1-cos(x))))(solve(x=2,3,x*sin(x)+cos(x)-1)) \\ _Charles R Greathouse IV_, Mar 06 2014
%K nonn,cons
%O 0,1
%A _Jonathan Vos Post_, Jan 07 2012
|
