imported>Etone |
imported>Etone |
| Line 1: |
Line 1: |
| *作业电子版于2019/11/26 23:59 之前提交到邮箱 <font color=blue>njuadvalg@163.com</font>
| | 学号（研究生） 姓名 |
| *每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。
| |
|
| |
|
| == Problem 1==
| | DZ1928004 刘尹成 |
| Let <math>G(V,E)</math> be an undirected graph with positive edge weights <math>w:E\to\mathbb{Z}^+</math>. Given a partition of <math>V</math> into <math>k</math> disjoint subsets <math>S_1,S_2,\ldots,S_k</math>, we define
| |
| :<math>w(S_1,S_2,\ldots,S_k)=\sum_{uv\in E\atop \exists i\neq j: u\in S_i,v\in S_j}w(uv)</math>
| |
| as the cost of the '''<math>k</math>-cut''' <math>\{S_1,S_2,\ldots,S_k\}</math>. Our goal is to find a <math>k</math>-cut with maximum cost.
| |
| # Give a poly-time greedy algorithm for finding the weighted max <math>k</math>-cut. Prove that the approximation ratio is <math>(1-1/k)</math>.
| |
| # Consider the following local search algorithm for the weighted max cut (max 2-cut).
| |
| ::Fill in the blank parenthesis. Give an analysis of the running time of the algorithm. And prove that the approximation ratio is 0.5.
| |
| start with an arbitrary bipartition of <math>V</math> into disjoint <math>S_0,S_1</math>;
| |
| while (true) do
| |
| if <math>\exists i\in\{0,1\}</math> and <math>v\in S_i</math> such that <font color=red>(______________)</font>
| |
| then <math>v</math> leaves <math>S_i</math> and joins <math>S_{1-i}</math>;
| |
| continue;
| |
| end if
| |
| break;
| |
| end
| |
|
| |
|
| == Problem 2==
| | MG1928002 陈旭 |
| Given <math>m</math> subsets <math>S_1,S_2,\ldots, S_m\subseteq U</math> of a universe <math>U</math> of size <math>n</math>, we want to find a <math>C\subseteq\{1,2,\ldots, {m}\}</math> of fixed size <math>k=|C|</math> with the maximum '''coverage''' <math>\left|\bigcup_{i\in C}S_i\right|</math>.
| | |
| | MG1928003 邓煜恒 |
| | |
| | MG1928005 龚丹毅 |
| | |
| | MG1928006 冀雅琴 |
| | |
| | MG1928007 康志杰 |
| | |
| | MG1928008 李敏 |
| | |
| | MG1928009 李同新 |
| | |
| | MG1928012 蔺惠娟 |
|
| |
|
| * Give a poly-time greedy algorithm for the problem. Prove that the approximation ratio is <math>1-(1-1/k)^k>1-1/e</math>.
| | MG1928013 令狐飘 |
|
| |
|
| | MG1928016 刘姝君 |
| | |
| | MG1928018 卢昱彤 |
| | |
| | MG1928019 陆晓娟 |
| | |
| | MG1928020 马晨明 |
| | |
| | MG1928026 石天润 |
|
| |
|
| == Problem 3==
| | MG1928027 谭洁 |
| In the ''maximum directed cut'' (MAX-DICUT) problem, we are given as input a directed graph <math>G(V,E)</math>. The goal is to partition <math>V</math> into disjoint <math>S</math> and <math>T</math> so that the number of edges in <math>E(S,T)=\{(u,v)\in E\mid u\in S, v\in T\}</math> is maximized. The following is the integer program for MAX-DICUT:
| | |
| :::<math>
| | MG1928029 陶智 |
| \begin{align}
| | |
| \text{maximize} &&& \sum_{(u,v)\in E}y_{u,v}\\
| | MG1928030 肖成龙 |
| \text{subject to} && y_{u,v} &\le x_u, & \forall (u,v)&\in E,\\
| |
| && y_{u,v} &\le 1-x_v, & \forall (u,v)&\in E,\\
| |
| && x_v &\in\{0,1\}, & \forall v&\in V,\\
| |
| && y_{u,v} &\in\{0,1\}, & \forall (u,v)&\in E.
| |
| \end{align}
| |
| </math>
| |
| Let <math>x_v^*,y_{u,v}^*</math> denote the optimal solution to the '''LP-relaxation''' of the above integer program.
| |
| * Apply the randomized rounding such that for every <math>v\in V</math>, <math>\hat{x}_v=1</math> independently with probability <math>x_v^*</math>. Analyze the approximation ratio (between the expected size of the random cut and OPT).
| |
| * Apply another randomized rounding such that for every <math>v\in V</math>, <math>\hat{x}_v=1</math> independently with probability <math>1/4+x_v^*/2</math>. Analyze the approximation ratio for this algorithm.
| |
|
| |
|
| == Problem 4==
| | MG1928032 徐梓添 |
| Recall the MAX-SAT problem and its integer program:
| |
| :::<math>
| |
| \begin{align}
| |
| \text{maximize} &&& \sum_{j=1}^my_j\\
| |
| \text{subject to} &&& \sum_{i\in S_j^+}x_i+\sum_{i\in S_j^-}(1-x_i)\ge y_j, && 1\le j\le m,\\
| |
| &&& x_i\in\{0,1\}, && 1\le i\le n,\\
| |
| &&& y_j\in\{0,1\}, && 1\le j\le m.
| |
| \end{align}
| |
| </math>
| |
| Recall that <math>S_j^+,S_j^-\subseteq\{1,2,\ldots,n\}</math> are the respective sets of variables appearing positively and negatively in clause <math>j</math>.
| |
|
| |
|
| Let <math>x_i^*,y_j^*</math> denote the optimal solution to the '''LP-relaxation''' of the above integer program. In our class we learnt that if <math>\hat{x}_i</math> is round to 1 independently with probability <math>x_i^*</math>, we have approximation ratio <math>1-1/\mathrm{e}</math>.
| | MG1928037 赵驿航 |
|
| |
|
| We consider a generalized rounding scheme such that every <math>\hat{x}_i</math> is round to 1 independently with probability <math>f(x_i^*)</math> for some function <math>f:[0,1]\to[0,1]</math> to be specified.
| | MG1928038 陈喆 |
| * Suppose <math>f(x)</math> is an arbitrary function satisfying that <math>1-4^{-x}\le f(x)\le 4^{x-1}</math> for any <math>x\in[0,1]</math>. Show that with this rounding scheme, the approximation ratio (between the expected number of satisfied clauses and OPT) is at least <math>3/4</math>.
| | |
| * Derandomize this algorithm through conditional expectation and give a deterministic polynomial time algorithm with approximation ratio <math>3/4</math>.
| | MG1928039 都昊 |
| * Is it possible that for some more clever <math>f</math> we can do better than this? Try to justify your argument.
| |
|
| |
|
| ==Problem 5 ==
| | MG1928045 彭蔚然 |
| The following is the weighted version of set cover problem:
| | |
| | MG1928046 邱子键 |
|
| |
|
| Given <math>m</math> subsets <math>S_1,S_2,\ldots,S_m\subseteq U</math>, where <math>U</math> is a universe of size <math>n=|U|</math>, and each subset <math>S_i</math> is assigned a positive weight <math>w_i>0</math>, the goal is to find a <math>C\subseteq\{1,2,\ldots,m\}</math> such that <math>U=\bigcup_{i\in C}S_i</math> and the total weight <math>\sum_{I\in C}w_i</math> is minimized.
| | MG1928053 姚靖心 |
| * Give an integer program for the problem and its LP relaxation.
| | |
| * Consider the following idea of randomized rounding: independently round each fractional value to <math>\{0,1\}</math> with the probability of the fractional value itself; and repeatedly apply this process to the variables rounded to 0 in previous iterations until <math>U</math> is fully covered. Show that this can return a set cover with <math>O(\log n)</math> approximation ratio with probability at least <math>0.99</math>.
| | MG1928054 战杨志豪 |
| | |
| | 学号（本科生） 姓名 |
| | |
| | 161200070 赵志展 |
| | |
| | 161158085 张昱培 |
| | |
| | 161170043 王雅媛 |
| | |
| | 161170054 游振宇 |
| | |
| | 161158084 王译铭 |
| | |
| | 161158040 马梦楠 |
| | |
| | 161158029 栗卓 |
| | |
| | 161170026 刘世淦 |
| | |
| | 学号（交换生） 姓名 |
| | |
| | 198354018 張沁全 |