The OEIS is supported by the many generous donors to the OEIS 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 Table of n, a(n) for n=0..104. 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified February 25 02:17 EST 2024. Contains 370308 sequences. (Running on oeis4.)