Approximation of Bookmark Assignment

CREATED: 200712180737 Speaker: Hirotaka Ono (Kyushu University) ** Background

• directory structure and links as a rooted connected DAG
• vertices are weighted with frequency of access
• goal is to improve the efficiency of accessing the vertices
• gain of a set of bookmarks, $g(B) = \sum_{v \in V} p_v (d(v) - d_b(v))$
• k-BAP problem: $|B| \le k$ and $g(B)$ is maximum
• related to proxy server allocation, root - server, vertices - proxy, bookmark - direct link to server ** Result
• (1 - 1/e ~ 0.632) approximation algorithm
• Unless P = NP, there does not exist a (1 - 1/e - $\epsilon$) approximation algorithm
• Therefore the approximation algorithm is optimal! ** Inapproximability result
• gap preserving reduction from unit cost maximum coverage problem ** Approximation algorithm
• Greedy algorithm

for i from 1 to k

B = B union B

• Complexity is O(k|V||E|), maintain shortest path tree ** Determining the approximation ratio
• g(ALG) / g(OPT) >= a
• standard technique: instead of using g(ALG), use lower bound of g(OPT), instead of using g(OPT) using upper bound of g(ALG)
• more general framework is submodular function optimization
• given set S, f:2^S -> R, f({}) = 0
• submodular iff $f(A \cup B) + f(A \cap B) \le f(A) + f(B)$
• monotone iff $f(A \cup {x}) - f(A) \ge 0$
• submodular set function optimization has a greedy algorithm with (1 + 1/e) approximation
• Proof is to show that the gain function is monotone submodular ** g is monotone (easy) ** g is submodular (need a number of lemmas first) ** P1: $V(A) \cup V(B) = V(A \cup B), V(A) \cap V(B) \supseteq V(A \cap B)$ ** P2: $\sum_{V(A) - V(B)} p(d_{A \cup B} - d_A) = 0, \sum_{V(B) - V(A)} p(d_{A \cup B} - d_B) = 0$ ** P3: $d_{A \cup B} = min(d_A, d_B), d_{A \cap B} \ge max(d_A, d_B)$