The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A203914 Decimal expansion of alpha_GW, a constant arising in Max Cut algorithm of Goemans and Williamson. 0
 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, 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, 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 (list; constant; graph; refs; listen; history; text; internal format)
 OFFSET 0,1 COMMENTS 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). 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 LINKS M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, JACM 42 (1995), no. 6, 1115-1145. L. Trevisan, On Khot's unique games conjecture, Bull. Amer. Math. Soc. 49 (2012), 91-111. FORMULA alpha_GW = min_{1/2 < rho < 1} 1/Pi * arccos(1-2*rho)/rho. EXAMPLE 0.878567205784851604217301... MAPLE nmax:= 105: Digits:= nmax+15: f:= rho-> arccos(1-2*rho)/(Pi*rho): s:= convert(evalf(f(fsolve(D(f)(x), x=1/2..1))), string): seq(parse(s[n+1]), n=1..nmax);  # Alois P. Heinz, Jan 08 2012 MATHEMATICA 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 *) PROG (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 CROSSREFS Sequence in context: A180311 A289913 A103984 * A037077 A094106 A277064 Adjacent sequences:  A203911 A203912 A203913 * A203915 A203916 A203917 KEYWORD nonn,cons AUTHOR Jonathan Vos Post, Jan 07 2012 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 26 20:11 EST 2020. Contains 331288 sequences. (Running on oeis4.)