imported>TCSseminar |
|
| Line 1: |
Line 1: |
| *每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。
| | == Summary == |
| | | Importing file |
| == Problem 1 ==
| |
| (Primal-Dual)
| |
| | |
| == Problem 2 ==
| |
| A ''<math>k</math>-uniform hypergraph'' is an ordered pair <math>G=(V,E)</math>, where <math>V</math> denotes the set of vertices and <math>E</math> denotes the set of edges. Moreover, each edge in <math>E</math> now contains <math>k</math> distinct vertices, instead of <math>2</math> (so a <math>2</math>-uniform hypergraph is just what we normally call a graph).
| |
| A hypergraph is <math>k</math>-regular if all vertices have degree <math>k</math>; that is, each vertex is exactly contained within <math>k</math> hypergraph edges.
| |
| | |
| Show that for sufficiently large <math>k</math>, the vertices of a <math>k</math>-uniform, <math>k</math>-regular hypergraph can be <math>2</math>-colored so that no edge is monochromatic.
| |
| What's the smallest value of <math>k</math> you can achieve?
| |
| | |
| == Problem 3 ==
| |
| Suppose we have graphs <math>G=(V,E)</math> and <math>H=(V,F)</math> on the same vertex set.
| |
| We wish to partition <math>V</math> into clusters <math>V_1,V_2,\cdots</math> so as to maximise:
| |
| :<math>(\#\text{ of edges in }E\text{ that lie within clusters})+(\#\text{ of edges in }F\text{ that lie between clusters}).</math>
| |
| | |
| * Show that the following SDP is an upperbound on this.
| |
| :::<math>
| |
| \text{maximize}\qquad\sum_{(u,v)\in E}\langle x_u,x_v\rangle+\sum_{(u,v)\in F}(1-\langle x_u,x_v\rangle) \\
| |
| \begin{align}
| |
| \text{subject to} && \langle x_u,x_u\rangle & =1, & \forall u & \in V, \\
| |
| && \langle x_u,x_v\rangle & \ge0, & \forall u,v & \in V, \\
| |
| && x_u & \in\mathbb R^{|V|}, & \forall u & \in V.
| |
| \end{align}
| |
| </math>
| |
| | |
| * Describe a clustering into <math>4</math> clusters that achieves an objective value <math>0.75</math> times the SDP value. (Hint: Use Goemans-Williamson style rounding but with two random hyperplanes instead of one. You may need a quick matlab calculation just like GW.)
| |
| | |
| == Problem 4 ==
| |
| (MCMC)
| |
