高级算法 (Fall 2022)/Problem Set 3

Problem 1

Let [math]\displaystyle{ N }[/math] be a set (the "universe") and [math]\displaystyle{ F }[/math] a function mapping subsets of [math]\displaystyle{ N }[/math] to real numbers. There are two different standard definitions of what it means for [math]\displaystyle{ F }[/math] to be submodular:

(i) For all [math]\displaystyle{ A,B\subseteq N }[/math],

[math]\displaystyle{ F(A\cap B)+F(A\cup B)\leq F(A)+F(B) }[/math].

(ii) For all [math]\displaystyle{ A\subseteq B\subseteq N }[/math], [math]\displaystyle{ j\notin B }[/math],

[math]\displaystyle{ F(A\cup\{j\})-F(A)\geq F(B\cup\{j\})-F(B) }[/math].

You have the following tasks.

• Show that (i) implies (ii).

• Show that (ii) implies (i).

• Design a [math]\displaystyle{ O(2^nn^2) }[/math]-time algorithm for the following problem. Prove the correctness and efficiency of the algorithm. (You are welcome to implement and test your algorithm here)

Given a function [math]\displaystyle{ F:2^{[n]}\to \mathbb{Z} }[/math]. Find two subsets (not necessarily distinct) [math]\displaystyle{ A,B\subseteq [n] }[/math] such that [math]\displaystyle{ F(A\cap B)+F(A\cup B)\gt F(A)+F(B) }[/math] or certify no such pair of subsets exist.

Problem 2

Consider the following greedy algorithm for the knapsack problem:

Sort all items according to the ratio [math]\displaystyle{ r_i = v_i/w_i }[/math] so that [math]\displaystyle{ r_1 ≥ r_2 ≥ … ≥ r_n }[/math]; for [math]\displaystyle{ i=1,2, ..., n }[/math] item [math]\displaystyle{ i }[/math] joins [math]\displaystyle{ S }[/math] if the resulting total weight [math]\displaystyle{ ≤ B }[/math];

• Show that the approximation ratio of this algorithm can be arbitrarily bad. Formally, given an arbitrary constant [math]\displaystyle{ \epsilon \in (0,1) }[/math], construct an instance that the solution of this algorithm [math]\displaystyle{ SOL }[/math] is less than [math]\displaystyle{ (1-\epsilon)OPT }[/math].
• Consider the following modification to this algorithm. Let the sorted order of objects be [math]\displaystyle{ a_1,..., a_n }[/math]. Find the lowest [math]\displaystyle{ k }[/math] such that the size of the first [math]\displaystyle{ k }[/math] objects exceeds [math]\displaystyle{ B }[/math]. Now, pick the more valuable of [math]\displaystyle{ \{a_1,...,a_{k−1}\} }[/math] and [math]\displaystyle{ \{a_k\} }[/math] (we have assumed that the size of each object is at most [math]\displaystyle{ B }[/math]). Show that this algorithm achieves an approximation ratio of [math]\displaystyle{ 1/2 }[/math].

Problem 3

A matroid [math]\displaystyle{ (E,\mathcal{I}) }[/math] is a set [math]\displaystyle{ E }[/math] of ground elements of [math]\displaystyle{ I }[/math] together with a collection [math]\displaystyle{ \mathcal{I} }[/math] of subsets of [math]\displaystyle{ E }[/math]; that is, if [math]\displaystyle{ S\in \mathcal{I} }[/math], then [math]\displaystyle{ S\subseteq E }[/math]. A set [math]\displaystyle{ S\in \mathcal{I} }[/math] is said to be independent. The independent sets of a matroid obey the following axioms:

• If [math]\displaystyle{ S }[/math] is independent, then any [math]\displaystyle{ S'\subseteq S }[/math] is also independent.
• If [math]\displaystyle{ S }[/math] and [math]\displaystyle{ T }[/math] are independent, and [math]\displaystyle{ \vert S\vert\lt \vert T\vert }[/math], then there is some [math]\displaystyle{ e\in T-S }[/math] such that [math]\displaystyle{ S\cup \{e\} }[/math] is also independent.

An independet set [math]\displaystyle{ S }[/math] is a base of the matroid if no set strictly containing it is also independent.

You have the following tasks.

• Given an undirected graph [math]\displaystyle{ G=(V,E) }[/math], show that the forests of [math]\displaystyle{ G }[/math] forms a matroid; that is, show that if [math]\displaystyle{ E }[/math] is the ground set, and [math]\displaystyle{ \mathcal{I} }[/math] the set of forests of [math]\displaystyle{ G }[/math], then the matroid axioms are obeyed;
• Show that for any matroid, every base of the matroid has the same number of ground elements.
• For any given matroid, suppose that for each [math]\displaystyle{ e\in E }[/math], we have a nonnegative weight [math]\displaystyle{ w_e\geq 0 }[/math]. Design a greedy algorithm for the problem of finding a maximum-weight base of the matroid.
• Let [math]\displaystyle{ (E,\mathcal{I}) }[/math] be any matroid. Let [math]\displaystyle{ f:2^{E}\rightarrow \mathbb{Z} }[/math] be a monotone, submodular function satisfying [math]\displaystyle{ f(\emptyset)=0 }[/math]. Design an approximation algorithm for finding a maximum-value base of the matroid with respect to [math]\displaystyle{ f }[/math]. Show that your algorithm outputs a solution that has value at least half the optimal value. (Hint: Show that for any two bases of the matroid, [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math], there exists a bijection [math]\displaystyle{ g:X\to Y }[/math] such that for any [math]\displaystyle{ e\in X,X-\{e\}+\{g(e)\} }[/math] is independent. Try to design a local search algorithm using this property.)

Problem 4

The following is the weighted version of set cover problem:

Given [math]\displaystyle{ m }[/math] subsets [math]\displaystyle{ S_1,S_2,\ldots,S_m\subseteq U }[/math], where [math]\displaystyle{ U }[/math] is a universe of size [math]\displaystyle{ n=|U| }[/math], and each subset [math]\displaystyle{ S_i }[/math] is assigned a positive weight [math]\displaystyle{ w_i\gt 0 }[/math], the goal is to find a [math]\displaystyle{ C\subseteq\{1,2,\ldots,m\} }[/math] such that [math]\displaystyle{ U=\bigcup_{i\in C}S_i }[/math] and the total weight [math]\displaystyle{ \sum_{I\in C}w_i }[/math] is minimized.

• 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]\displaystyle{ \{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]\displaystyle{ U }[/math] is fully covered. Show that this can return a set cover with [math]\displaystyle{ O(\log n) }[/math] approximation ratio with probability at least [math]\displaystyle{ 0.99 }[/math].

Problem 5

In the maximum directed cut (MAX-DICUT) problem, we are given as input a directed graph [math]\displaystyle{ G(V,E) }[/math]. The goal is to partition [math]\displaystyle{ V }[/math] into disjoint [math]\displaystyle{ S }[/math] and [math]\displaystyle{ T }[/math] so that the number of edges in [math]\displaystyle{ 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]\displaystyle{ \begin{align} \text{maximize} &&& \sum_{(u,v)\in E}y_{u,v}\\ \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]\displaystyle{ 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]\displaystyle{ v\in V }[/math], [math]\displaystyle{ \hat{x}_v=1 }[/math] independently with probability [math]\displaystyle{ 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]\displaystyle{ v\in V }[/math], [math]\displaystyle{ \hat{x}_v=1 }[/math] independently with probability [math]\displaystyle{ 1/4+x_v^*/2 }[/math]. Analyze the approximation ratio for this algorithm.