高级算法 (Fall 2022)/Problem Set 4: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
Gispzjz (talk | contribs)
Gispzjz (talk | contribs)
Line 17: Line 17:
==Problem 3==
==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.
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.

Revision as of 07:37, 12 December 2022

Problem 1

Suppose there is a coin [math]\displaystyle{ C }[/math]. During each query, it outputs HEAD with probability [math]\displaystyle{ p }[/math] and TAIL with probability [math]\displaystyle{ 1-p }[/math], where [math]\displaystyle{ p \in (0, 1) }[/math] is a real number.

  • Let [math]\displaystyle{ q \in (0, 1) }[/math] be another real number. Design an algorithm that outputs HEAD with probability [math]\displaystyle{ q }[/math] and TAIL with probability [math]\displaystyle{ 1-q }[/math]. There is no other random sources for your algorithm except the coin [math]\displaystyle{ C }[/math]. Make sure that your algorithm halts with probability [math]\displaystyle{ 1 }[/math].
  • What is the expected number of queries for the coin [math]\displaystyle{ C }[/math] that your algorithm use before it halts?

Problem 2

A boolean code is a mapping [math]\displaystyle{ C:\{0,1\}^k\rightarrow\{0,1\}^n }[/math]. Each [math]\displaystyle{ x\in\{0,1\}^k }[/math] is called a message and [math]\displaystyle{ y=C(x) }[/math] is called a codeword. The code rate [math]\displaystyle{ r }[/math] of a code [math]\displaystyle{ C }[/math] is [math]\displaystyle{ r=\frac{k}{n} }[/math]. A boolean code [math]\displaystyle{ 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]\displaystyle{ A\in\{0,1\}^{n\times k} }[/math] such that [math]\displaystyle{ C(x)=Ax }[/math] for any [math]\displaystyle{ x\in\{0,1\}^k }[/math], where the additions and multiplications are defined over the finite field of order two, [math]\displaystyle{ (\{0,1\},+_{\bmod 2},\times_{\bmod 2}) }[/math].

The distance between two codeword [math]\displaystyle{ y_1 }[/math] and [math]\displaystyle{ y_2 }[/math], denoted by [math]\displaystyle{ d(y_1,y_2) }[/math], is defined as the Hamming distance between them. Formally, [math]\displaystyle{ 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]\displaystyle{ C }[/math] is the minimum distance between any two codewords. Formally, [math]\displaystyle{ 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]\displaystyle{ r }[/math] and the code distance [math]\displaystyle{ 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]\displaystyle{ C:\{0,1\}^k\rightarrow\{0,1\}^n }[/math] of code rate [math]\displaystyle{ r }[/math] and distance [math]\displaystyle{ \left(\frac{1}{2}-\Theta\left(\sqrt{r}\right)\right)n }[/math]. Try to optimize the constant in [math]\displaystyle{ \Theta(\cdot) }[/math].
  • Prove a similar result for linear boolean codes.

Problem 3

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

Problem 4

Given [math]\displaystyle{ m }[/math] subsets [math]\displaystyle{ S_1,S_2,\ldots, S_m\subseteq U }[/math] of a universe [math]\displaystyle{ U }[/math] of size [math]\displaystyle{ n }[/math], we want to find a [math]\displaystyle{ C\subseteq\{1,2,\ldots, {m}\} }[/math] of fixed size [math]\displaystyle{ k=|C| }[/math] with the maximum coverage [math]\displaystyle{ \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]\displaystyle{ 1-(1-1/k)^k\gt 1-1/e }[/math].

Problem 5

Recall the MAX-SAT problem and its integer program:

[math]\displaystyle{ \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]\displaystyle{ S_j^+,S_j^-\subseteq\{1,2,\ldots,n\} }[/math] are the respective sets of variables appearing positively and negatively in clause [math]\displaystyle{ j }[/math].

Let [math]\displaystyle{ 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]\displaystyle{ \hat{x}_i }[/math] is round to 1 independently with probability [math]\displaystyle{ x_i^* }[/math], we have approximation ratio [math]\displaystyle{ 1-1/\mathrm{e} }[/math].

We consider a generalized rounding scheme such that every [math]\displaystyle{ \hat{x}_i }[/math] is round to 1 independently with probability [math]\displaystyle{ f(x_i^*) }[/math] for some function [math]\displaystyle{ f:[0,1]\to[0,1] }[/math] to be specified.

  • Suppose [math]\displaystyle{ f(x) }[/math] is an arbitrary function satisfying that [math]\displaystyle{ 1-4^{-x}\le f(x)\le 4^{x-1} }[/math] for any [math]\displaystyle{ 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]\displaystyle{ 3/4 }[/math].
  • Derandomize this algorithm through conditional expectation and give a deterministic polynomial time algorithm with approximation ratio [math]\displaystyle{ 3/4 }[/math].
  • Is it possible that for some more clever [math]\displaystyle{ f }[/math] we can do better than this? Try to justify your argument.

Problem 6

Given an undirected graph [math]\displaystyle{ 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]\displaystyle{ \mathcal{C} }[/math] denote the set of all cycles in graph [math]\displaystyle{ G }[/math].

Consider the following integer program

[math]\displaystyle{ \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]\displaystyle{ 2\lceil \log_2 n \rceil }[/math] vertices of degree [math]\displaystyle{ \geq 3 }[/math], where [math]\displaystyle{ n }[/math] is the total number of vertices on this graph.