高级算法 (Fall 2019)/Problem Set 4

• 作业电子版于2020/1/17 23:59 之前提交到邮箱 njuadvalg@163.com
• 每道题目的解答都要有完整的解题过程。中英文不限。

Problem 1

Suppose we want to estimate the value of [math]\displaystyle{ Z }[/math]. Let [math]\displaystyle{ \mathcal{A} }[/math] be an algorithm that outputs [math]\displaystyle{ \widehat{Z} }[/math] satisfying [math]\displaystyle{ \Pr[ (1-\epsilon)Z \leq \widehat{Z} \leq (1+\epsilon )Z] \geq \frac{3}{4} . }[/math]

We run [math]\displaystyle{ \mathcal{A} }[/math] independently for [math]\displaystyle{ s }[/math] times, and obtain the outputs [math]\displaystyle{ \widehat{Z}_1,\widehat{Z}_2,\ldots,\widehat{Z}_s }[/math].

Let [math]\displaystyle{ X }[/math] be the median (中位数) of [math]\displaystyle{ \widehat{Z}_1,\widehat{Z}_2,\ldots,\widehat{Z}_s }[/math]. Find the number [math]\displaystyle{ s }[/math] such that [math]\displaystyle{ \Pr[ (1-\epsilon)Z \leq X \leq (1+\epsilon )Z] \geq 1 - \delta . }[/math]

Express [math]\displaystyle{ s }[/math] as a function of [math]\displaystyle{ \delta }[/math]. Make [math]\displaystyle{ s }[/math] as small as possible.

Remark: in this problem, we boost the probability of success from [math]\displaystyle{ \frac{3}{4} }[/math] to [math]\displaystyle{ 1-\delta }[/math]. This method is called the median trick.

Hint: Chernoff bound.

Problem 2

Given an undirected graph [math]\displaystyle{ G(V, E) }[/math] with maximum degree [math]\displaystyle{ \Delta }[/math], where the vertex set [math]\displaystyle{ V }[/math] is partitioned into [math]\displaystyle{ r }[/math] disjoint subsets, i.e., [math]\displaystyle{ V = S_1 \cup S_2 \cup \cdots \cup S_r }[/math] with [math]\displaystyle{ S_i \cap S_j = \varnothing }[/math] for all [math]\displaystyle{ i \neq j }[/math]. We call a vertex set [math]\displaystyle{ T }[/math] is a transversal of the partition [math]\displaystyle{ \{S_1, S_2, \cdots, S_r\} }[/math], if [math]\displaystyle{ |T \cap S_i| = 1 }[/math] for all [math]\displaystyle{ 1 \leq i \leq r }[/math]. Assume that [math]\displaystyle{ |S_i| \geq 2e\Delta }[/math] for all [math]\displaystyle{ 1 \leq i \leq r }[/math].

1. Prove that there must be an independent transversal (a transversal which is also an independent set) of [math]\displaystyle{ \{S_1, S_2, \cdots, S_r\} }[/math].

Hint: Lovász Local Lemma.

2. Design a randomized algorithm that finds an independent transversal of [math]\displaystyle{ \{S_1, S_2, \cdots, S_r\} }[/math] in expected polynomial time.

Problem 3

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.

Problem 4

Let [math]\displaystyle{ G=(V,E) }[/math] be a simple and undirected graph. The Ising model is a distribution [math]\displaystyle{ \mu }[/math] over [math]\displaystyle{ \{-1,+1\}^V }[/math] such that

[math]\displaystyle{ \forall \sigma \in \{-1,+1\}^V, \quad \mu(\sigma) = \frac{1}{Z}\exp\left( -\sum_{\{u,v\}\in E}\beta\sigma(u)\sigma(v) \right), }[/math]

where the parameter [math]\displaystyle{ \beta \in \mathbb{R} }[/math] is called the inverse temperature and the partition function [math]\displaystyle{ Z }[/math] is defined as

[math]\displaystyle{ Z = \sum_{\tau \in \{-1,+1\}^V} \exp\left( -\sum_{\{u,v\}\in E}\beta\tau(u)\tau(v) \right). }[/math]

Hence, [math]\displaystyle{ \mu }[/math] is a joint distribution of [math]\displaystyle{ |V| }[/math] random variables and each variable [math]\displaystyle{ v \in V }[/math] takes its value from [math]\displaystyle{ \{-1,+1\} }[/math].

Let [math]\displaystyle{ \sigma \in \{-1,+1\}^V }[/math] and [math]\displaystyle{ v \in V }[/math]. Let [math]\displaystyle{ \mu_v(\cdot\mid \sigma( V \setminus \{v\})) }[/math] denote the marginal distribution on [math]\displaystyle{ v }[/math] conditioning on the value of [math]\displaystyle{ u }[/math] is fixed as [math]\displaystyle{ \sigma(u) }[/math] for all [math]\displaystyle{ u\neq v }[/math].

The Glauber dynamics for Ising model is defined as follows:

• initially, start from an arbitrary [math]\displaystyle{ X \in \{-1,+1\}^{V} }[/math];
• in each step, pick a vertex [math]\displaystyle{ v \in V }[/math] uniformly at random, and resample [math]\displaystyle{ X(v) }[/math] according to the distribution [math]\displaystyle{ \mu_v(\cdot\mid X( V \setminus \{v\})) }[/math].

Here are the problems.

• Calculate [math]\displaystyle{ \mu_v(+1\mid \sigma( V \setminus \{v\})) }[/math] and [math]\displaystyle{ \mu_v(-1\mid \sigma( V \setminus \{v\})) }[/math].

Here [math]\displaystyle{ \mu_v(+1\mid \sigma( V \setminus \{v\})) }[/math] is the probability that [math]\displaystyle{ v }[/math] takes the value +1 conditioning on the value of [math]\displaystyle{ u }[/math] is fixed as [math]\displaystyle{ \sigma(u) }[/math] for all [math]\displaystyle{ u\neq v }[/math].

• Show that the Glauber dynamics for Ising model is irreducible, aperiodic and reversible with respect to [math]\displaystyle{ \mu }[/math].