高级算法 (Fall 2023)/Problem Set 2: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
Newer edit →
VisualWikitext
Zouzongrui (talk | contribs)
439 edits
Created page with "*每道题目的解答都要有完整的解题过程，中英文不限。 *我们推荐大家使用LaTeX, markdown等对作业进行排版。 == 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...."
 
Zouzongrui (talk | contribs)
439 edits
Line 3: Line 3:
*我们推荐大家使用LaTeX, markdown等对作业进行排版。
*我们推荐大家使用LaTeX, markdown等对作业进行排版。


== Problem 1 (Min-cut/Max-cut) ==
== Problem 1 (Adjacency matrix) ==


* ['''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?)
Let <math>A</math> be the adjacency matrix of an undirected connected graph <math>G</math>, and <math>\alpha_1</math> be its largest eigenvalue.  
* ['''Weighted min-cut problem'''] Modify the Karger's Contraction algorithm so that it works for the ''weighted min-cut problem''. Prove that the modified algorithm returns a weighted minimum cut with probability at least <math>{2}/{n(n-1)}</math>. The weighted min-cut problem is defined as follows.
* ['''Lowerbounding <math>\alpha_1</math>'''] We proved <math>\alpha_1 \le d_{\mathrm{max}}</math> in class. Show that <math>\alpha_1 \ge d_{\mathrm{avg}}</math> where <math>d_{\mathrm{avg}}:=\frac{2|E|}{|V|}</math> is the average degree of the graph.
** '''Input''': an undirected weighted graph <math>G(V, E)</math>, where every edge <math>e \in E</math> is associated with a positive real weight <math>w_e</math>
** '''Output''': a cut <math>C</math> in <math>G</math> such that <math>\sum_{e \in C} w_e</math> is minimized.
 
* ['''Max directed-cut'''] In the ''maximum directed cut'' (MAX-DICUT) problem, we are given as input a directed graph <math>G(V,E)</math>. Each directed arc <math>(i, j) \in E</math> has nonnegative weight <math>w_{ij} \ge 0</math>.  The goal is to partition <math>V</math> into disjoint sets <math>U</math> and <math>W=V\setminus U</math>  so as to maximize the total weight of the arcs going from <math>U</math> to <math>W</math>. Give a randomized <math>1/4</math>-approximation algorithm for this problem.

Revision as of 07:25, 24 November 2023

  • 每道题目的解答都要有完整的解题过程，中英文不限。
  • 我们推荐大家使用LaTeX, markdown等对作业进行排版。

Problem 1 (Adjacency matrix)

Let [math]\displaystyle{ A }[/math] be the adjacency matrix of an undirected connected graph [math]\displaystyle{ G }[/math], and [math]\displaystyle{ \alpha_1 }[/math] be its largest eigenvalue.

  • [Lowerbounding [math]\displaystyle{ \alpha_1 }[/math]] We proved [math]\displaystyle{ \alpha_1 \le d_{\mathrm{max}} }[/math] in class. Show that [math]\displaystyle{ \alpha_1 \ge d_{\mathrm{avg}} }[/math] where [math]\displaystyle{ d_{\mathrm{avg}}:=\frac{2|E|}{|V|} }[/math] is the average degree of the graph.
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=高级算法_(Fall_2023)/Problem_Set_2&oldid=11902"