tag:blogger.com,1999:blog-6942493516775094341.post3725217895611664979..comments2013-02-12T08:29:18.505-05:00Comments on 15-854B: Advanced Approximation Algorithms: Notes on the group Steiner tree proofRyan O'Donnellhttp://www.blogger.com/profile/01760886084136827344noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-6942493516775094341.post-89251973161014873462008-02-18T12:45:00.000-05:002008-02-18T12:45:00.000-05:00fixed, thanks!fixed, thanks!Anupamhttps://www.blogger.com/profile/16810841145280011482noreply@blogger.comtag:blogger.com,1999:blog-6942493516775094341.post-89685602636784818852008-02-17T17:17:00.000-05:002008-02-17T17:17:00.000-05:00A minor typo:$Pr[ E_w | E_u ] = x'_w/x'_e$and not ...A minor typo:<BR/><BR/>$Pr[ E_w | E_u ] = x'_w/x'_e$<BR/><BR/>and not <BR/><BR/>$Pr[ E_w | E_u ] = x'_u/x'_e$Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6942493516775094341.post-58695834939570725552008-02-17T10:54:00.000-05:002008-02-17T10:54:00.000-05:00thanks, Aravind!Another point I forgot to mention ...thanks, Aravind!<BR/><BR/>Another point I forgot to mention in class was that the analysis showing that each group gets connected with probability $1/\log |g|$ is tight. (The original paper of Garg et al points this out as well.) <BR/><BR/>Here's the example: take a complete binary tree with $g$ leaves, where the $x_e$ values on edges go down by a factor of $2$ at every level. A simple calculation shows that we will hit at least one of the leaves with probability $\approx 1/height$.Anupamhttps://www.blogger.com/profile/16810841145280011482noreply@blogger.comtag:blogger.com,1999:blog-6942493516775094341.post-15808531927904275862008-02-14T22:57:00.000-05:002008-02-14T22:57:00.000-05:00Hi folks, looks like an interesting course! I'd ju...Hi folks, looks like an interesting course! I'd just like to comment that the maximum possible value of Delta can be determined without altering the edges' LP values -- see the <A HREF="http://www.cs.umd.edu/~srin/PS/covstei-jou.ps" REL="nofollow">paper</A> <BR/>of Goran Konjevod, R. Ravi and myself. (See Thm. 3.2 and Sec. 3.1.) That paper deals with Covering Steiner, a generalization of Group Steiner where each group i has a requirement k_i. In particular, for Group Steiner, we get that Delta <= ln N.<BR/><BR/>aravindAnonymousnoreply@blogger.com