View source for 高级算法 (Fall 2022)/Problem Set 4

== Problem 1 ==
Suppose there is a coin <math> C </math>. 
During each query, it outputs HEAD with probability <math>p</math> and TAIL with probability <math>1-p</math>, where <math> p \in (0, 1) </math> is a real number.
* Let <math> q \in (0, 1) </math> be another real number. Design an algorithm that outputs HEAD with probability <math>q</math> and TAIL with probability <math>1-q</math>. There is no other random sources for your algorithm except the coin <math>C</math>. Make sure that your algorithm halts with probability <math>1</math>.
* What is the expected number of queries for the coin <math>C</math> that your algorithm use before it halts?

==Problem 2==
A '''boolean code''' is a mapping <math>C:\{0,1\}^k\rightarrow\{0,1\}^n</math>. Each <math>x\in\{0,1\}^k</math> is called a '''message''' and <math>y=C(x)</math> is called a '''codeword'''. The '''code rate''' <math>r</math> of a code <math>C</math> is <math>r=\frac{k}{n}</math>. A boolean code <math>C:\{0,1\}^k\rightarrow\{0,1\}^n</math> is a '''linear code''' if it is a linear transformation, i.e. there is a matrix <math>A\in\{0,1\}^{n\times k}</math> such that <math>C(x)=Ax</math> for any <math>x\in\{0,1\}^k</math>, where the additions and multiplications are defined over the finite field of order two, <math>(\{0,1\},+_{\bmod 2},\times_{\bmod 2})</math>.

The '''distance''' between two codeword <math>y_1</math> and <math>y_2</math>, denoted by <math>d(y_1,y_2)</math>, is defined as the Hamming distance between them. Formally, <math>d(y_1,y_2)=\|y_1-y_2\|_1=\sum_{i=1}^n|y_1(i)-y_2(i)|</math>. The distance of a code <math>C</math> is the minimum distance between any two codewords. Formally, <math>d=\min_{x_1,x_2\in \{0,1\}^k\atop x_1\neq x_2}d(C(x_1),C(x_2))</math>.

Usually we want to make both the code rate <math>r</math> and the code distance <math>d</math> as large as possible, because a larger rate means that the amount of actual message per transmitted bit is high, and a larger distance allows for more error correction and detection.

* Use the probabilistic method to prove that there exists a boolean code <math>C:\{0,1\}^k\rightarrow\{0,1\}^n</math> of code rate <math>r</math> and distance <math>\left(\frac{1}{2}-\Theta\left(\sqrt{r}\right)\right)n</math>. Try to optimize the constant in <math>\Theta(\cdot)</math>.
* Prove a similar result for linear boolean codes.

==Problem 3==
Let <math>G=(V,E)</math> be a cycle of length <math>4n</math>, and let <math>V=V_1 \cup V_2 \cup ... \cup V_n</math> be a paitition of its <math>4n</math> vertices into <math>n</math> pairwise disjoint subsets, each of cardinality <math>4</math>. Is it true that there must be an independent set of <math>G</math> containing precisely one vertex from each <math>V_i</math>? Prove or supply a counterexample.

== Problem 4==
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>.

* 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>.

== Problem 5==
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>.

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.
* 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>.
* Is it possible that for some more clever <math>f</math> we can do better than this? Try to justify your argument.

==Problem 6 ==
Given an undirected graph <math>G=(V,E)</math>, the feedback vertex set problem is to find the smallest subset of vertices, whose removal makes the graph acyclic.

Let <math>\mathcal{C}</math> denote the set of all cycles in graph <math>G</math>.

Consider the following integer program
:::<math>
\begin{align}
\text{minimize} &&& \sum_{v \in V}x_v\\
\text{subject to} && \sum_{v \in C}x_v &\geq 1, & \forall C&\in \mathcal{C},\\
&& x_v &\in\{0,1\}, & \forall v&\in V.
\end{align}
</math>
* Write the dual program.
* Use the prime-dual schema to design an approximation algorithm. What is the approximate ratio of your algorithm?
* '''Bonus problem''': assuming that the following proposition holds, can your obtain a better approximation algorithm?

Proposition: Given a graph with no degree-1 vertex, it must contain a cycle with at most <math>2\lceil \log_2 n \rceil</math> vertices of degree <math>\geq 3</math>, where <math>n</math> is the total number of vertices on this graph.

== Problem 7==
* Show that the following is an integer programming formulation for the minimum spanning tree (MST) problem. Assume we are given graph <math>G=(V,E)</math>, <math>|V|=n</math> with cost function <math>c:E\to Q^+</math>. For <math>A\subseteq E</math>, we will denote by <math>\kappa(A)</math> the number of connected components in graph <math>G_A=(V,A)</math>.
:::<math>
\begin{align}
\text{minimize} &&& \sum_e c_ex_e\\
\text{subject to} &&& \sum_{e\in A}x_e=n-\kappa(A), && A\subset E,\\
&&& \sum_{e\in E}x_e=n-1,\\
&&& x_e\in \{0,1\}, && e\in E.
\end{align}
</math>

* It will be convenient to change the objective function of IP to <math>\max \sum_e-c_ex_e </math> Obtain the LP-relaxation and dual of this modified formulation.

* Consider the primal solution produced by Kruskal's algorithm. Let <math> e_1,e_2,...,e_m </math> be the edges sorted by increasing cost, <math>|E|=m</math>. This algorithm greedily picks a maximal acyclic subgraph from this sorted list. Obtain a suitable dual feasible solution so that all complementary slackness conditions are satisfied. Hint: Let <math>A_t=\{e_1,...,e_t\}</math>. Set <math>y_{A_t} = e_{t+1}-e_t</math>, for </math>1\leq t<m </math>, and <math> y_E=-c_m</math> where <math>y</math> is the dual variable.