From TCS Wiki
(Difference between pages)
imported>TCSseminar |
|
| Line 1: |
Line 1: |
| *每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。
| | == Summary == |
| | | Importing file |
| == Problem 1 ==
| |
| Recall that in class we show by the probabilistic method how to deduce a <math>\frac{n(n-1)}{2}</math> upper bound on the number of distinct min-cuts in any multigraph <math>G</math> with <math>n</math> vertices from the <math>\frac{2}{n(n-1)}</math> lower bound for success probability of Karger's min-cut algorithm.
| |
| | |
| Also recall that the <math>FastCut</math> algorithm taught in class guarantees to return a min-cut with probability at least <math>\Omega(1/\log n)</math>. Does this imply a much tighter <math>O(\log n)</math> upper bound on the number of distinct min-cuts in any multigraph <math>G</math> with <math>n</math> vertices? Prove your improved upper bound if your answer is "yes", and give a satisfactory explanation if your answer is "no".
| |
| | |
| == Problem 2 ==
| |
Latest revision as of 12:42, 30 August 2022
