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

 

Logo


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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

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