

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

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, 11151145.
L. Trevisan, On Khot's unique games conjecture, Bull. Amer. Math. Soc. 49 (2012), 91111.


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):
seq(parse(s[n+1]), n=1..nmax); # Alois P. Heinz, Jan 08 2012


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

(PARI) (x>2*x/(Pi*(1cos(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



