高级算法 (Fall 2024)/Problem Set 1: Difference between revisions
Zhangyiyao (talk | contribs) Tag: Manual revert |
|||
| Line 4: | Line 4: | ||
== Problem 1 (Min-cut/Max-cut) == | == Problem 1 (Min-cut/Max-cut) == | ||
['''Counting <math>\alpha</math>-approximate min-cut'''] For any '''<math>\alpha \ge 1</math>''', a cut is called an '''<math>\alpha</math>'''-approximate min-cut in a multigraph '''<math>G</math>''' if the number of edges in it is at most '''<math>\alpha</math>''' times that of the min-cut. Prove that the number of '''<math>\alpha</math>'''-approximate min-cuts in a multigraph '''<math>G</math>''' is at most '''<math>n^{2\alpha} / 2</math>'''. ('''''Hint''''': Run Karger's algorithm until it has '''<math>\lceil 2\alpha \rceil</math>''' supernodes. What is the chance that a particular '''<math>\alpha</math>'''-approximate min-cut is still available? How many possible cuts does this collapsed graph have?) | |||
== Problem 2 (Fingerprinting) == | == Problem 2 (Fingerprinting) == | ||
Revision as of 02:08, 28 September 2024
- 每道题目的解答都要有完整的解题过程，中英文不限。
- 我们推荐大家使用LaTeX, markdown等对作业进行排版。
Problem 1 (Min-cut/Max-cut)
[Counting [math]\displaystyle{ \alpha }[/math]-approximate min-cut] For any [math]\displaystyle{ \alpha \ge 1 }[/math], a cut is called an [math]\displaystyle{ \alpha }[/math]-approximate min-cut in a multigraph [math]\displaystyle{ G }[/math] if the number of edges in it is at most [math]\displaystyle{ \alpha }[/math] times that of the min-cut. Prove that the number of [math]\displaystyle{ \alpha }[/math]-approximate min-cuts in a multigraph [math]\displaystyle{ G }[/math] is at most [math]\displaystyle{ n^{2\alpha} / 2 }[/math]. (Hint: Run Karger's algorithm until it has [math]\displaystyle{ \lceil 2\alpha \rceil }[/math] supernodes. What is the chance that a particular [math]\displaystyle{ \alpha }[/math]-approximate min-cut is still available? How many possible cuts does this collapsed graph have?)