# 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
- short cut links (bookmarks) are additional edges from the root
- 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

## B =

## for i from 1 to k

### b = arg max g(B union b)

### 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)$