deferred-decision-principle

You are currently browsing articles tagged deferred-decision-principle.

Đẹp 5

Trong bài này, chúng ta tìm hiểu một kết quả vô cùng đẹp của lý thuyết khoa học máy tính: Isolation Lemma (bổ đề cô lập). Bổ đề này lần đầu tiên được phát biểu và chứng minh bởi Valiant và Vazirani [1]. Sau đó Mulmuley, Vazirani và Vazirani [2] ứng dụng một phiên bản hơi khác trong bài toán cặp ghép, làm cho bổ đề này trở nên nổi tiếng. Bổ đề phát biểu như sau:

Isolation Lemma: Cho một tập gốc (ground set) gồm $n$ phần tử $[n] = \{1,2,\ldots, n\}$ và một họ (family) các tập con $\mathcal{F}$ của $[n]$. Với mỗi $x \in [n]$, ta gán cho nó một trọng số $w(x)$ là một số ngẫu nhiên từ tập $[N] = \{1,2,\ldots, N\}$. Ta định nghĩa trọng số của mỗi tập con $S \in \mathcal{F}$ như sau:

$w(S) = \sum_{x\in S}w(x)\qquad(1)$

Với xác suất ít nhất $1-n/N$, tồn tại duy nhất một tập $S \in \mathcal{F}$ có trọng số nhỏ nhất.

 
Về mặt lí thuyết, Isolation Lemma thực sự đáng kinh ngạc: nếu chọn $N = 2n$ thì xác suất tồn tại duy nhất tập con $S$ có trọng số nhỏ nhất $\geq 1/2$; không phụ thuộc vào kích thước của tập $\mathcal{F}$. Trong trường hợp tồi nhất, $\mathcal{F}$ có thể có tới $2^{n}-1$ tập con.

Nếu vào trang Wikipedia, bạn sẽ thấy một loạt các ứng dụng của Isolation Lemma trong lý thuyết khoa học máy tính. Ở đây có một ứng dụng mà mình rất thích: đảm bảo tính duy nhất của đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có trọng số không âm.

Remark: Ta sử dụng $[n]$ để kí hiệu tập các số nguyên $\{1,2,\ldots, n\}$.

Ứng dụng trong đường đi ngắn nhất

Weight Perturbation: Gọi $G(V,E)$ là một đồ thị đơn, vô hướng trong đó mỗi cạnh $e\in E$ có một trọng số $w(e) \geq 0$. Bài toán đặt ra là tìm một hàm trọng số không âm $\ell(.)$ cho các cạnh của $G$ sao cho với mọi cặp đỉnh $u,v$ bất kì của đồ thị ($u \not= v$):

  1. Đường đi ngắn nhất $u$ và $v$ với hàm trọng số $\ell(.)$ cũng là đường đi ngắn nhất giữa hai đỉnh đó với hàm trọng số $w(.)$.
  2. Đường đi ngắn nhất giữa $u,v$ với hàm trọng số $\ell(.)$ là duy nhất.

 
Lời giải: Để đơn giản, trước hết ta giả sử trọng số của mỗi cạnh trong $G$ là $0$, i.e, $w(e) = 0 \quad \forall e\in E$. Ta gán cho mỗi cạnh một trọng số là một số ngẫu nhiên từ tập $[|V|^2|E|]$. Cố định hai đỉnh $u,v$. Gọi $\mathcal{F}_{uv}$ là tập các đường đi ngắn nhất (có cùng trọng số 0) từ $u$ tới $v$. Theo Isolation Lemma, xác xuất tồn tại duy nhất một tập con $S \in \mathcal{F}_{uv}$ có trọng số nhỏ nhất ít nhất là:

$1 - \frac{|E|}{|V|^2|E|} = 1- \frac{1}{|V|^2}\qquad(2)$

Đây cũng là xác suất mà đường đi ngắn nhất giữa $u,v$ với hàm trọng số $\ell'(.)$ là duy nhất. Do có không quá $|V|^2/2$ cặp đỉnh $u,v$, xác suất đề đường đi ngắn nhất giữa hai đỉnh bất kì với hàm trọng số $\ell'(.)$ trở nên duy nhất là ít nhất:

$1 - \frac{|V|^2/2}{|V|^2} = 1/2 \qquad(3)$

Ta quay trở lại trường hợp tổng quát với hàm trọng số $w(.)$ không âm bất kì. Coi trọng số của mỗi cạnh được biểu diễn bởi một số nguyên $p$ bít trong đó $p = \lfloor \log_2( \max_{e\in E }w(e)) \rfloor +1$. Thêm bít 0 vào sau biểu diễn nhị phân của trọng số mỗi cạnh (tương đương với nhân trọng số mỗi cạnh với $2^q$); ở đây:

$q = \lfloor \log_2( |V|^2|E|) \rfloor +1 \qquad(4)$

Chú ý, trọng số $\ell'(e)$ tìm được bằng cách áp dụng Isolation Lemma ở trên có thể biểu diễn bởi tối đa $q$ bít. Ta định nghĩa:

$\ell(e) = w(e)2^q + \ell'(e) \qquad(5)$

Do $\ell'(.)$ là một hàm ngẫu nhiên, $\ell(.)$ cũng là một hàm ngẫu nhiên. Không khó để thấy rằng, với xác suất ít nhất $1/2$, hàm $\ell(.)$ thỏa mãn hai tính chất cần có của bài toán Weight Perturbation. Ta có thể tăng cường xác suất này lên $1-\epsilon$ với $\epsilon$ nhỏ tùy ý bằng cách lặp đi lặp lại nhiều lần gán trọng số cạnh ngẫu nhiên.


Trong một số tình huống, giả thiết đường đi ngắn nhất giũa mọi cặp đỉnh là duy nhất làm việc thiết kế giải thuật trở nên đơn giản hơn rất nhiều. Ví dụ, Krauthgamer, Nguyễn, Zondiner [3] sử dụng giả thiết này trong bài toán preserving terminal distance. Borradaile, Zafirani và Nayyeri [4] sử dụng một giải thiết tương tự để giải bài toán shortest disjoint paths.

Tóm lại, nếu bạn làm việc các bài toán liên quan đến đường đi thì Isolation Lemma cho phép bạn giả sử rằng đường đi ngắn nhất giữa một hoặc nhiều cặp đỉnh là duy nhất.

Chứng minh Isolation Lemma

Chứng minh Isolation Lemma khá đơn giản (nhưng không tầm thường). Trên trang wikipedia trình bày chi tiết 2 chứng minh khác nhau: chứng minh của Mulmuley, Vazirani, và Vazirani [2] và chứng minh của Joel Spencer. Gần đây, Ta-Shma [5] trình bày một chứng minh khác (tại thời điểm paper này được publish, Ta-Shma là một học sinh cấp 3), cho một kết quả mạnh hơn Isolation Lemma một chút.

Chứng minh Isolation Lemma: Xét một phần tử $x \in [n]$. Gọi:

$\alpha(x) = \min_{S\in \mathcal{F}, x\not\in S}w(S) - \min_{S \in \mathcal{F}, x\in S } w(S\setminus \{x\})\qquad(6)$

Nhận xét: giá trị của $\alpha(x)$ không phụ thuộc vào $w(x)$. Do đó, ta có thể giả sử giá trị của $w(x)$ được gán sau tất cả các phần tử khác thì $\alpha(x)$ xác định trước khi $w(x)$ được gán (ta đang sử dụng deferred decision principle). Như vậy, xác suất để $w(x) = \alpha(x)$ là không quá $\frac{1}{N}$. Từ đó suy ra:

Claim: Xác suất để tồn tại một phần tử $x\in [n]$ sao cho $w(x) = \alpha(x)$ là không quá $\frac{n}{N}$.

Giả sử tồn tại $A, B \in \mathcal{F}, A\not= B$ sao cho $w(A) = w(B)$ và $w(A), w(B)$ là nhỏ nhất. Gọi $y$ là một phần tử bất kì của $A\setminus B$. Ta có:

$\begin{array}{lcl} \alpha(y) & = & \min_{S\in \mathcal{F}, y\not\in S}w(S) - \min_{S \in \mathcal{F}, y\in S } w(S\setminus \{y\}) \\ & = & w(B) - (w(A) - y) \\ & = & w(y) \end{array} \qquad (7)$

Theo Claim trên, xác suất này không quá $n/N$. Như vậy, xác suất không tồn tại $A,B$ như vậy là ít nhất $1 - n/N$.


Tham khảo

[1] L. G. Valiant and V. V. Vazirani. NP is as easy as detecting unique solutions. Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing (STOC'85). ACM, 1985.
[2] K. Mulmuley and U. V. Vazirani and V. V. Vazirani. Matching is as easy as matrix inversion. Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (STOC'87). ACM, 1987.
[3] R. Krauthgamer and H. L Nguyễn, and T. Zondiner. Preserving terminal distances using minors. SIAM Journal on Discrete Mathematics 28.1 (2014): 127-141.
[4] G. Borradaile and A. Nayyeri and F. Zafarani. Towards single face shortest vertex-disjoint paths in undirected planar graphs. Algorithms-ESA 2015. Springer, Berlin, Heidelberg, 2015. 227-238.
[5] N. Ta-Shma. A simple proof of the Isolation Lemma. Electronic Colloquium on Computational Complexity (ECCC). Vol. 22. 2015.

Tags: , , , ,

« Older entries