

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 polynomialtime 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



FORMULA

alpha_GW = min_{1/2 < rho < 1} 1/Pi * arccos(12*rho)/rho.


EXAMPLE

0.878567205784851604217301...


MAPLE

nmax:= 105: Digits:= nmax+15:
f:= rho> arccos(12*rho)/(Pi*rho):
s:= convert(evalf(f(fsolve(D(f)(x), x=1/2..1))), string):


MATHEMATICA

digits = 105; FindMinimum[1/Pi*ArcCos[12*rho]/rho, {rho, 4/5}, WorkingPrecision > digits+1] // First // RealDigits[#, 10, digits]& // First (* JeanFrançois Alcover, Feb 20 2014 *)


PROG



CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



