高级算法 (Fall 2024)/Problem Set 2

• 请同学们完成Problem 1 ～ 5，然后在Problem 6 ～ 9中任选2个作答。

• 每道题目的解答都要有完整的解题过程，中英文不限。

• 我们推荐大家使用LaTeX, markdown等对作业进行排版。

Problem 1

(a.) Let [math]\displaystyle{ M_1 = (E_1, \mathcal{I}_1) }[/math] and [math]\displaystyle{ M_2 = (E_2, \mathcal{I}_2) }[/math] be two matroids with [math]\displaystyle{ E_1 \cap E_2 = \emptyset }[/math]. Define [math]\displaystyle{ \mathcal{I}_1 \oplus \mathcal{I}_2 = \{ A_1 \cup A_2 : A_1 \in \mathcal{I}_1, A_2 \in \mathcal{I}_2 \} }[/math]. Prove that [math]\displaystyle{ M := (E_1 \cup E_2, \mathcal{I}_1 \oplus \mathcal{I}_2) }[/math] is a matroid.

(b.) Let [math]\displaystyle{ M = (E, \mathcal{I}) }[/math] be a matroid, and [math]\displaystyle{ X \subseteq E }[/math]. Define [math]\displaystyle{ \mathcal{I}_X = \{ A \subseteq X : A \in \mathcal{I} \} }[/math]. Show that [math]\displaystyle{ M_X := (X, \mathcal{I}_X) }[/math] is a matroid.

(c.) Let [math]\displaystyle{ M = (E, \mathcal{I}) }[/math] be a matroid, and [math]\displaystyle{ k \geq 0 }[/math] be an integer. Define [math]\displaystyle{ \mathcal{I}_k = \{ A \in \mathcal{I} : |A| \leq k \} }[/math]. Show that [math]\displaystyle{ M_k := (E, \mathcal{I}_k) }[/math] is a matroid.

Problem 2

Recall that in the uncapacitated facility location problem, we are given a set [math]\displaystyle{ F }[/math] of potential facilities, a set [math]\displaystyle{ D }[/math] of clients, a metric [math]\displaystyle{ c }[/math] over [math]\displaystyle{ F \cup D }[/math], and a cost [math]\displaystyle{ f_i \gt 0 }[/math] for every [math]\displaystyle{ i \in F }[/math]. For any [math]\displaystyle{ S \subseteq F }[/math], we define [math]\displaystyle{ \mathrm{cost}(S) := \sum_{i \in S} f_i + \sum_{j \in D} c(j, S) }[/math], where [math]\displaystyle{ c(j, S) := \min_{i \in S} c_{ji} }[/math]. (We assume [math]\displaystyle{ c(j, \emptyset) = \infty }[/math]).

Prove that [math]\displaystyle{ -\mathrm{cost}(S) }[/math] is submodular. (We say [math]\displaystyle{ \mathrm{cost}(S) }[/math] is supermodular.)

Problem 3

Suppose we are given [math]\displaystyle{ n }[/math] activities. Each activity has a starting time [math]\displaystyle{ s_i }[/math], a finishing time [math]\displaystyle{ f_i \gt s_i }[/math], and a weight [math]\displaystyle{ w_i \gt 0 }[/math]. We have [math]\displaystyle{ m }[/math] rooms to hold the activities. Two activities [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] can be held in the same room if [math]\displaystyle{ [s_i, f_i) }[/math] and [math]\displaystyle{ [s_j, f_j) }[/math] are disjoint. (There is no constraint between two activities held in two different rooms.) Our goal is to schedule a maximum weight of activities using the [math]\displaystyle{ m }[/math] rooms.

Show how to use the linear programming technique to solve the problem. Assume you can require the LP solver to return a vertex point.

Problem 4

Let [math]\displaystyle{ G = (L, R, E) }[/math] be a bipartite graph. Write down the linear program that finds the maximum matching in [math]\displaystyle{ G }[/math], and the linear program that finds the minimum vertex cover of [math]\displaystyle{ G }[/math]. Prove that the size of the maximum matching in [math]\displaystyle{ G }[/math] is equal to the size of the minimum vertex cover in [math]\displaystyle{ G }[/math]. This suggests that the vertex cover problem in bipartite graphs is polynomial time solvable.

Problem 5

Consider the unrelated machine makespan minimization problem. Let [math]\displaystyle{ p_{\max} }[/math] be the maximum [math]\displaystyle{ p_{ij} }[/math] value over all non-infinity [math]\displaystyle{ p_{ij} }[/math] values; that is, [math]\displaystyle{ p_{\max} := \max_{i \in M, j \in J : p_{ij} \neq \infty} p_{ij} }[/math]. Assume we are promised that the optimum makespan [math]\displaystyle{ T }[/math] of the instance is at least [math]\displaystyle{ L \cdot p_{\max} }[/math] for some [math]\displaystyle{ L \geq 1 }[/math].

Show that the algorithm you learned in class gives a [math]\displaystyle{ (1 + 1/L) }[/math]-approximation for the problem.

Problem 6

In class, you learned two linear program relaxations for the uncapacitated facility location problem:

First LP Relaxation	Second LP Relaxation
[math]\displaystyle{ \min \quad \sum_{(i, J)} \mathrm{cost}(i, J) \cdot x_{i, J} }[/math] [math]\displaystyle{ \begin{aligned} \sum_{(i, J): j \in J} x_{i, J} &\geq 1 &&\forall j \in C \\ x_{i, J} &\geq 0 &&\forall (i, J) \end{aligned} }[/math]	[math]\displaystyle{ \min \quad \sum_{i \in F} f_i y_i + \sum_{i \in F, j \in C} c(i, j)x_{i, j} }[/math] [math]\displaystyle{ \begin{aligned} \sum_{i \in F} x_{i, j} &\geq 1 &&\forall j \in C \\ x_{i, j} &\leq y_i &&\forall i \in F, j \in C \\ x_{i, j} & \geq 0 &&\forall i \in F, j \in C \\ y_i & \geq 0 &&\forall i \in F \end{aligned} }[/math]

Write down the dual of both LPs, and prove that the two dual LPs are equivalent directly, without using the equivalence of the two primal LPs.

Problem 7

In the maximum 2-SAT problem, we are given [math]\displaystyle{ n }[/math] boolean variables [math]\displaystyle{ x_1, x_2, \cdots, x_n }[/math] and [math]\displaystyle{ m }[/math] clauses, where each clause is the disjunction (the "or" operation) of 2 literals (a literal is either [math]\displaystyle{ x_i }[/math] or [math]\displaystyle{ \neg x_i }[/math]). The goal of the problem is to find an assignment to [math]\displaystyle{ x_1, x_2, \cdots, x_n }[/math] so as to maximize the number of satisfied clauses.

Use SDP to design a [math]\displaystyle{ 0.878 }[/math]-approximation algorithm for this problem.

Problem 8

Recall that in the weighted set cover problem, we are given [math]\displaystyle{ m }[/math] subsets [math]\displaystyle{ S_1, S_2, \cdots, S_m }[/math] of [math]\displaystyle{ [n] }[/math], and a weight vector [math]\displaystyle{ w = (w_1, w_2, \cdots, w_m) \in \mathbb{R}_{\geq 0}^m }[/math]. The goal is to choose a set [math]\displaystyle{ I \subseteq [m] }[/math] such that [math]\displaystyle{ \bigcup_{i \in I} S_i = [n] }[/math] so as to minimize [math]\displaystyle{ \sum_{i \in I} w_i }[/math].

Consider the following natural LP relaxation for the problem:

[math]\displaystyle{ \min \quad \sum_{i \in [m]} w_i x_i \quad \text{s.t.} }[/math]

[math]\displaystyle{ \sum_{i : j \in S_i} x_i \geq 1 \quad \forall j \in [n] }[/math]

[math]\displaystyle{ x_i \geq 0 \quad \forall i \in [m] }[/math]

Assume we have an efficient rounding algorithm [math]\displaystyle{ \mathcal{A} }[/math] that, given any weighted set cover instance [math]\displaystyle{ (n, m, \{S_i\}_{i \in m}, w) }[/math] and any valid solution [math]\displaystyle{ x }[/math] to the above linear programming, outputs a valid solution [math]\displaystyle{ I \subseteq [m] }[/math] to the instance such that [math]\displaystyle{ \sum_{i \in I} w_i \leq \alpha_n \sum_{i \in [m]} w_i x_i }[/math], for some function [math]\displaystyle{ \alpha: \mathbb{Z}_{\gt 0} \to [1, \infty) }[/math].

Use [math]\displaystyle{ \mathcal{A} }[/math] as a black box to design an efficient randomized rounding algorithm [math]\displaystyle{ \mathcal{A}' }[/math] that is "oblivious" to the weight vector [math]\displaystyle{ w }[/math]. More specifically, let [math]\displaystyle{ \epsilon \gt 0 }[/math] be a given parameter. Then given [math]\displaystyle{ (n, m, \{S_i\}_{i \in m}) }[/math] and a valid solution [math]\displaystyle{ x }[/math] to the LP, [math]\displaystyle{ \mathcal{A}' }[/math] should randomly output a valid solution [math]\displaystyle{ I }[/math] to the instance such that [math]\displaystyle{ \Pr[i \in I] \leq (1 + \epsilon) \alpha_n x_i }[/math] for every [math]\displaystyle{ i \in [n] }[/math]. Notice that [math]\displaystyle{ w }[/math] is not given to [math]\displaystyle{ \mathcal{A}' }[/math]; also notice that whether [math]\displaystyle{ x }[/math] or [math]\displaystyle{ I }[/math] is valid is independent of the [math]\displaystyle{ w }[/math] vector, so the requirement for [math]\displaystyle{ \mathcal{A}' }[/math] is well-defined.

Hint: Design a zero-sum game between a [math]\displaystyle{ w }[/math]-player and an [math]\displaystyle{ I }[/math]-player; then use the multiplicative weight update method to find the strategy for the [math]\displaystyle{ I }[/math]-player.

Problem 9

Suppose we have a set [math]\displaystyle{ S \subseteq \{0, 1\}^n }[/math] of valid solutions for a problem, and a set [math]\displaystyle{ C \subseteq \mathbb{R}^n }[/math] of potential cost functions. For notation convenience, we assume [math]\displaystyle{ C }[/math] is finite, but the problem also makes sense when [math]\displaystyle{ C }[/math] is infinite. The cost of the solution [math]\displaystyle{ x \in S }[/math] for the instance [math]\displaystyle{ c \in C }[/math] is [math]\displaystyle{ c^{\mathrm{T}} x }[/math]. Given an instance (or cost function) [math]\displaystyle{ c \in C }[/math], the goal of the problem is to find a solution [math]\displaystyle{ x \in S }[/math] so as to minimize the cost [math]\displaystyle{ c^{\mathrm{T}} x }[/math]. Let [math]\displaystyle{ \mathrm{OPT}(c) }[/math] be the optimum solution for this instance [math]\displaystyle{ c }[/math], and let [math]\displaystyle{ \mathrm{opt}(c) }[/math] be the cost, i.e., [math]\displaystyle{ \mathrm{opt}(c) = c^{\mathrm{T}} \cdot \mathrm{OPT}(c) }[/math]. For every [math]\displaystyle{ x \in S }[/math], there is some [math]\displaystyle{ c \in C }[/math] such that [math]\displaystyle{ x }[/math] is the optimal solution for [math]\displaystyle{ c }[/math], i.e., [math]\displaystyle{ \mathrm{OPT}(c) = x }[/math].

Suppose we try to formulate an LP to solve the problem using a polytope [math]\displaystyle{ \mathcal{Q} \subseteq \mathbb{R}^n }[/math] as follows:

[math]\displaystyle{ \min \quad c^{\mathrm{T}} x \quad \text{s.t.} \quad (x, y) \in \mathcal{Q}. }[/math]

Notice that [math]\displaystyle{ \mathcal{Q} }[/math] is a polytope independent of [math]\displaystyle{ c }[/math]. We say that the LP correctly solves the problem if for every [math]\displaystyle{ c \in C }[/math], we have that [math]\displaystyle{ (\mathrm{OPT}(c), y) }[/math] for some [math]\displaystyle{ y }[/math] is an optimum solution to the LP.

Define a matrix [math]\displaystyle{ M \in \mathbb{R}_{\geq 0}^{S \times C} }[/math] as follows: [math]\displaystyle{ M_{x, c} = c^{\mathrm{T}} x - \mathrm{opt}(c) }[/math] for every [math]\displaystyle{ x \in S }[/math] and [math]\displaystyle{ c \in C }[/math].

Show that the minimum possible number of facets of [math]\displaystyle{ \mathcal{Q} }[/math] is equal to [math]\displaystyle{ \mathrm{rank}^+(M) }[/math], the non-negative rank of [math]\displaystyle{ M }[/math].