A203914 Decimal expansion of alpha_GW, a constant arising in Max Cut algorithm of Goemans and Williamson.

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

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