Skip to main content
Computer Science

Return to Question

added 194 characters in body
Source Link
Bob
Bob
  • 61
  • 1
  • 5

I'm completely stuck on Problem 4.10 of the Motwani-Raghavan Randomized Algorithms textbook. I don't want an answer, but hints may be helpful here. I understand the general Valiant scheme for the boolean hypercube but am unable to generalize to an arbitrary regular graph:

"Suppose we run Valiant’s scheme on an N-node network in which every node is of degree d; each packet first goes to a random destination chosen uniformly from all the nodes and then on to its final destination. Show that the expected number of steps for the completion of the first phase is $ \Omega\left(\frac{\log N}{d \log \log N} + \frac{\log N}{\log d}\right) $."

I understand that the diameter of any $d$-regular graph is always $O(N/d)$, but am not sure how the analysis would still work in this case as for the hypercube.

I have a feeling that the first term relates to the coupon collector's problem, but am completely unaware of how to get the second term.

Edit: Yuval in the comments essentially has a "workaround" proof that works, but isn't related to the scheme itself, and seems very unintended by the book authors. Is there another solution?

I'm completely stuck on Problem 4.10 of the Motwani-Raghavan Randomized Algorithms textbook. I don't want an answer, but hints may be helpful here. I understand the general Valiant scheme for the boolean hypercube but am unable to generalize to an arbitrary regular graph:

"Suppose we run Valiant’s scheme on an N-node network in which every node is of degree d; each packet first goes to a random destination chosen uniformly from all the nodes and then on to its final destination. Show that the expected number of steps for the completion of the first phase is $ \Omega\left(\frac{\log N}{d \log \log N} + \frac{\log N}{\log d}\right) $."

I understand that the diameter of any $d$-regular graph is always $O(N/d)$, but am not sure how the analysis would still work in this case as for the hypercube.

I have a feeling that the first term relates to the coupon collector's problem, but am completely unaware of how to get the second term.

I'm completely stuck on Problem 4.10 of the Motwani-Raghavan Randomized Algorithms textbook. I don't want an answer, but hints may be helpful here. I understand the general Valiant scheme for the boolean hypercube but am unable to generalize to an arbitrary regular graph:

"Suppose we run Valiant’s scheme on an N-node network in which every node is of degree d; each packet first goes to a random destination chosen uniformly from all the nodes and then on to its final destination. Show that the expected number of steps for the completion of the first phase is $ \Omega\left(\frac{\log N}{d \log \log N} + \frac{\log N}{\log d}\right) $."

I understand that the diameter of any $d$-regular graph is always $O(N/d)$, but am not sure how the analysis would still work in this case as for the hypercube.

I have a feeling that the first term relates to the coupon collector's problem, but am completely unaware of how to get the second term.

Edit: Yuval in the comments essentially has a "workaround" proof that works, but isn't related to the scheme itself, and seems very unintended by the book authors. Is there another solution?

Source Link
Bob
Bob
  • 61
  • 1
  • 5

Motwani-Raghavan 4.10 Ideas

I'm completely stuck on Problem 4.10 of the Motwani-Raghavan Randomized Algorithms textbook. I don't want an answer, but hints may be helpful here. I understand the general Valiant scheme for the boolean hypercube but am unable to generalize to an arbitrary regular graph:

"Suppose we run Valiant’s scheme on an N-node network in which every node is of degree d; each packet first goes to a random destination chosen uniformly from all the nodes and then on to its final destination. Show that the expected number of steps for the completion of the first phase is $ \Omega\left(\frac{\log N}{d \log \log N} + \frac{\log N}{\log d}\right) $."

I understand that the diameter of any $d$-regular graph is always $O(N/d)$, but am not sure how the analysis would still work in this case as for the hypercube.

I have a feeling that the first term relates to the coupon collector's problem, but am completely unaware of how to get the second term.