|
| |
|
|
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).
|
|
|
REFERENCES
|
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.
|
|
|
LINKS
|
Table of n, a(n) for n=0..104.
|
|
|
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
|
|
|
CROSSREFS
|
Sequence in context: A086911 A180311 A103984 * A037077 A094106 A021536
Adjacent sequences: A203911 A203912 A203913 * A203915 A203916 A203917
|
|
|
KEYWORD
|
nonn,cons
|
|
|
AUTHOR
|
Jonathan Vos Post, Jan 07 2012
|
|
|
STATUS
|
approved
|
| |
|
|
