Trong blog của mình có ít nhất 3 bài liên quan (1,2,3) đến tìm cặp ghép cực đại (maximum matching) trong đồ thị hai phía. Trong 3 bài đó, có bài trình bày thuật toán dễ hiểu, nhưng chậm hơn, và có bài trình bày thuật toán gần như nhanh nhất hiện tại. Tại sao lại cần phải có thêm một bài nữa về cặp ghép trên đồ thị hai phía?

Cả 3 bài trước đây đều sử dụng khái niệm đường tăng (augmenting path). Bài này sẽ trình bày một giải thuật dựa trên khái niệm đấu thầu (auction), và hoàn toàn không liên quan gì đến khái niệm đường tăng. Giải thuật này cực kì đơn giản, có thể làm việc được cả khi đồ thị có trọng số. Một số cách thực thi giải thuật này còn cho tốc độ tối ưu trong một vài trường hợp đặc biệt.

Giải thuật này được phát triển bởi Demange, Gale, and Sotomayor [1] trong một bài báo về đấu thầu trong kinh tế, do đó, nó không được phổ biến rộng rãi trong giới khoa học máy tính. Mình biết đến thuật toán này do tình cờ đọc được trên một bài viết trên blog Algorithmic Game Theory. Bài viết gốc hơi ngăn gọn súc tích quá, nên bài này mình viết lại và thêm chú giải.

Bài toán

Giả sử trong một cuộc đấu thầu có một tập $B$ nhà thầu (bidder) và $I$ mặt hàng (item). Nhà thầu thứ $i$ chỉ muốn trả tối đa $w[i,j]$ đồng cho mặt hàng thứ $j$. Tìm cách bán mỗi sản phẩm cho một nhà thầu sao cho tổng doanh thu là lớn nhất. Điều kiện của bài toán là mỗi người chỉ được mua tối đa một sản phẩm và mỗi sản phẩm chỉ được bán cho tối đa một người.

Nếu coi đồ thị hai phía $G(B\cup I, E)$ trong đó bên trái là các nhà thầu, bên phải là mặt hàng và cạnh nối giữa người thứ $i$ và mặt hàng thứ $j$ có trọng số $w[i,j]$ thì bài toán đặt ra là tìm một cặp ghép (matching) $M$ sao cho tổng trọng số:

$w(M) = \sum_{(i,j) \in M}w[i,j] \qquad (1)$

đạt cực đại.

Giả sử thêm nữa là tất cả các trọng số $w[i,j]$ đều nguyên.

Giải thuật

Trong quá trình thực hiện giải thuật dưới đây, mỗi mặt hàng $j$ sẽ lưu lại hai thông tin: $O[j]$ là người sở hữu (owner) hiện tại của mặt hàng và $P[j]$ là số tiền mà người đó đồng ý trả cho mặt hàng $j$. Ban đầu $O[j] = $ Null và $P[j] \leftarrow 0$. Trong mỗi lần lặp, ta sẽ xét một nhà thầu $i$ lấy ra từ một hàng đợi $Q$ (ban đầu tống tất cả nhà thầu vào $Q$), và tìm ra mặt hàng $j$ sao cho giá trị đặt thầu hiện tại $P[j]$ vẫn không lớn hơn số tiền mà người đó muốn trả cho mặt hàng $w[i,j]$. (Nếu $P[j] $ > $W[i,j]$ thì người $i$ không mua được $P[j]$ vì có người khác trả cao hơn người $i$ rồi). Trong số các mặt hàng đó, tìm ra mặt hàng có hiệu số $W[i,j] - P[j]$ lớn nhất và gán mặt hàng đó cho người $i$. Do $j$ đã bị gán cho $i$, ta sẽ phải tìm một mặt hàng khác để gán cho người sở hữu trước đó $O[j]$ của $j$, i.e ta sẽ đẩy $O[j]$ vào hàng đợi để tìm cho nhà thầu này một mặt hàng phù hợp sau. Cuối cùng tăng $P[j]$ lên $\delta = \frac{1}{|I|+1}$ đơn vị để thông báo cho những người khác biết đã có người đồng ý trả cho mặt hàng $j$ hơn người cao nhất khoảng $\delta$ đơn vị đồng.

Chi tiết giả mã như sau:

 

Thủ tục FindMax$(i,I,w)$ tìm ra mặt hàng trong $I$ có $w[i,j] - P[j]$ lớn nhất. Giả mã như sau:

 

Tính đúng đắn

Trong phần này, ta sẽ lần lượt trả lời 4 câu hỏi về tính đúng đắn của thuật toán AuctionBipartiteMatching: (a) thuật toán có dừng hay không, (b) đầu ra có phải là một cặp ghép hợp lệ (valid matching) hay không, (c) nếu đầu ra $M$ là một cặp ghép thì nó có phải là cặp ghép cực đại hay không và (d) sau bao lâu thì thuật toán kết thúc?

Câu (a): Thuật toán chắc chắn sẽ dừng vì mỗi lần ta đẩy vào $Q$ một nhà thầu mới, ta tăng $P[j]$ của một mặt hàng lên $\delta$ đơn vị, và một nhà thầu chỉ được xem xét đẩy vào $Q$ nếu $P[j] \leq w[i,j]$.

Câu (b): Dễ thấy mỗi mặt hàng $j$ chỉ được ghép với tối đa một nhà thầu $O[j]$ (nói tối đa là vì $O[j]$ có thể là Null). Chứng minh mỗi nhà thầu được ghép tối đa với một mặt hàng khó hơn một chút. Ta nhận xét thấy: nếu nhà thầu nào vẫn còn nằm trong hàng đợi $Q$ thì nhà thầu đó chưa được ghép với mặt hàng nào cả còn nhà thầu nằm ngoài $Q$ sẽ được ghép với tối đa một mặt hàng. Cụ thể, nếu $ i \in Q$, không tồn tại $j$ để $O[j] = i$ và nếu $i\not\in Q$, tồn tại tối đa một mặt hàng $j$ sao cho $i = O[j]$. Nhận xét này này có thể chứng minh được bằng quy nạp, chi tiết coi như bài tập cho bạn đọc.

Câu (c): Nhà thầu thứ $i$ được gọi là $\delta$-happy nếu một trong 2 điều sau là đúng:

1. Tồn tại một mặt hàng $j$ sao cho $i = O[j]$ và:

   $\delta + w[i,j] - P[j] \geq w[i,j'] - P[j'] \qquad (2)$

   với mọi $j' \not= j$.

2. Không tồn tại mặt hàng $j$ nào thỏa mãn $i = O[j]$ và với mọi mặt hàng $j' \in I$, $w[i,j']$< $P[j']$.

 
Chứng minh: Ta chứng minh bằng quy nạp. Ban đầu tất cả các nhà thầu đều nằm trong $Q$, Lemma 1 hiển nhiên đúng. Ta chỉ cần chứng minh mỗi lần lấy một nhà thầu ra khỏi hàng đợ thì nhà thầu đó $\delta$-happy. Theo mô tả thuật toán ở trên, ta xét hai trường hợp.

• TH1: tồn tại $j$ sao cho $w[i,j] \geq P[j]$ như trong câu lệnh if của vong lặp while. Do $j$ là một mặt hàng có $w[i,j] - P[j]$ cực đại, $w[i,j] - P[j] \geq w[i,j'] - P[j']$. Cuối khối lệnh if, ta tăng $P[j]$ lên $\delta$ đơn vị (điều này giải thích tại sao có đại lượng $\delta$ ở bên trái của $(2)$). Do đó, sau vòng lặp while này, điều kiện 1 của $\delta$-happy đúng với $i$.Do ta tăng $P[j]$ ở cuối khối lệnh, người sở hữu cũ (khác $i$) của $P[j]$ có thể không còn thỏa mãn điều kiện $\delta$-happy nữa. Nhưng ngay khi gán $j$ cho $i$, ta đã đưa người sở hữu cũ này vào hàng đợi $Q$. Do đó, Lemma 1 vẫn đúng.
• TH2: Không tồn tại $j$ sao cho $w[i,j] \geq P[j]$. Khi đó, $w[i,j']$ < $P[j']$ với mọi $j \in I$. Chú ý là $i$ vừa được lấy ra khỏi hàng đợi, theo câu (b), nó chưa được gán mặt hàng nào cả. Do đó, $i$ thỏa mãn điều kiện 2 của $\delta$-happy.

---

Lemma 1 cho phép chúng ta kết luận về tính tối ưu của $M$.

 

Trước hết ta sẽ xét ý nghĩa của Theorem 1. Nếu $M'$ là một cặp ghép cực đại, từ $(3)$ ta suy ra $w(M') \geq w(M) \geq w(M) - \epsilon$ với $\epsilon = \delta |I| $ là một số nhỏ hơn $1$ vì $\delta = \frac{1}{ |I|+1}$. Do $w[i,j]$ là các số nguyên, $w(M)$ và $w(M')$ cũng là các số nguyên. Do đó, $w(M) = w(M')$. Hay nói cách khác, $M$ cũng là một cặp ghép cực đại.

Chứng minh Theorem 1: Do khi thuật toán kết thúc, $Q = \emptyset$. Do đó, theo Lemma 1, mọi nhà thầu đều $\delta$-happy. Với mỗi cặp $(i,j) \in M'$, ta gọi $a[j]$ là mặt hàng trong $M$ ghép với $i$ (có thể xảy ra trường hợp $a[j] = j$, khi đó cặp $(i,j) \in M\cap M'$). Nếu không có mặt hàng nào trong $M$ ghép với $i$ thì ta coi $a[i] = \emptyset$. Lúc đó, ta sẽ coi $w[i, \emptyset] = P[ \emptyset] = 0$ trong phương trình dưới đây.

Ta có:

$\begin{array} {l} \sum_{(i,j) \in M'} (w[i,j] - P[j])&\leq \sum_{(i,j) \in M'}( w[i,a[j]] - P[a[j]] + \delta) \\ & \leq \sum_{(i,j) \in M} (w[i,j] - P[j] + \delta)
\\ & \leq \sum_{(i,j) \in M} w[i,j] - \sum_{j \in M} P[j] + |I|\delta
\\ & \leq \sum_{(i,j) \in M} w[i,j] - \sum_{j \in M'} P[j] + |I|\delta \end{array} \qquad (4)$

Từ (4) ta suy ra điều phải chứng minh bằng cách trừ $ \sum_{j \in M'} P[j]$ cho cả hai vế.

Phần còn lại, ta sẽ lần lượt giải thích từng bất đẳng thức trong $(4)$.

• Bất đẳng thức ở dòng đầu tiên là do $i$ thỏa mãn điều kiện $\delta$-happy. Chú ý, nghay cả khi $a[j] = \emptyset$ thì theo điều kiện 2 của $\delta$-happy $w[i,j]$ < $P[j]$, do đó, $w[i,j]-P[j]\leq \delta$.
• Bất đẳng thức ở dòng thứ 2 là do $w[i,j] - P[j] + \delta \geq 0$ với mọi $(i,j) \in M$.
• Bất đẳng thức ở dòng thứ 3 là do $|M| \leq |I|$.
• Bất đẳng thức ở dòng cuối cùng là do tất cả các $j$ chỉ xuất hiện tối đa một lần trong $M$ và tối đa một lần trong $M'$, và nếu mặt hàng $j$ không xuất hiện trong $M$, nó có $P[j] = 0$.

---

Câu (d): Gọi $C = \max_{i,j}W[i,j]$ là trọng số cực đại của các cạnh. Do mỗi lần thêm vào $Q$ một nhà thầu, $P[j]$ của mặt hàng nào đó tăng lên $\delta$ đơn vị. Theo điều kiện của vòng lặp, $P[j]$ không bao giờ vượt quá $C + \delta$. Do đó, số lần lặp trong vòng lặp while sẽ không quá:

$O(|I| \frac{C}{\delta}) = O(C|I|^2) \qquad (5)$

Mỗi lần thực hiện FindMax, ta trả không quá thời gian $O(|B|)$. Do đó, ta có thể thực thi thuật toán trong thời gian $O(C|I|^2|B|) = O(Cn^3)$, ở đây $n = |I| + |B|$.

Với đồ thị dầy $m = \Omega(n^2)$, cách thực thi đơn giản trên thực sự không quá tệ. Trong phần tới, ta sẽ tìm hiểu các cách thực thi hiệu quả hơn khi đồ thị thưa.

Thực thi hiệu quả thuật toán

Phần trước ta đã chỉ ra thuật toán có thể thực thi trong thời gian $O(Cn^3)$ trong đó $C$ là trọng số lớn nhất của cạnh. Tuy nhiên, ta có thể thực thi FindMax nhanh hơn bằng cách sử dụng các cấu trúc dữ liệu.

Cách thứ nhất, ta có thể dùng một max-heap cho mỗi nhà thầu, với khóa là $w[i,j] - P[j]$. Mỗi khi cập nhật lại $P[j]$, ta sẽ cập nhât $d_j$ max-heap, trong đó $d_j$ là bậc của $P[j]$. Do $P[j]$ tăng không quá $\frac{C}{\delta} = O(C|I|)$ lần, tổng số lần cập nhật max-heap cho tất cả các mặt hàng là:

$O( \frac{C}{\delta})(\sum_{j \in I} d_j) = O(Cnm) \qquad (7)$

trong đó $n,m$ là số đỉnh/cạnh của đồ thị. Do mỗi thao tác cập nhật max-heap có thể thực hiện trong thời gian $O(\log n)$, cách thực thi này có thời gian $O(Cmn \log n)$.

Cách thứ hai, với mỗi nhà thầu $i$ ta sử dụng một mảng các danh sách liên kêt $A_i[1,\ldots, C(|I|+1)]$ có kích thước $C(|I|+1)$. Phần tử thứ $t$ của mảng lưu các mặt hàng $j$ thỏa mãn $w[i,j] - P[j] = t\delta$. Thủ tục FindMax chính là tìm ô có chỉ số lớn nhất và khác rỗng trong mảng. Mỗi lần cập nhật lại $P[j]$, ta cập nhật lại mảng của các nhà thầu kề $i$ kề với $j$. Ta sẽ đưa $j$ vào ô $(w[i,j] - P[j])/\delta$. Tuy nhiên, sau khi đưa $j$ vào ô mới, ta cần phải "xóa" $j$ ra khỏi các ô cũ. Điều này có thể thực hiện bằng cách với mỗi mặt hàng $j$, lưu lại một mảng $A_j[1,\ldots, |B|]$, trong đó $A_j[i]$ lưu vị trí mới nhất của $j$ trong mảng của $i$. Các thao tác đều có thể thực hiện trong thời gian khấu trừ $O(1)$. Do đó, FindMax có thể thực hiện được trong thời gian khấu trừ $O(d_j)$, và với cấu trúc dữ liệu này, tổng thời gian của thuật toán là $O(Cmn)$. Cách này tuy có tiết kiệm được thời gian nhưng số lượng bộ nhớ sử dụng hơi lớn.

Đồ thị không có trọng số

Trong trường hợp đồ thị không có trọng số ($C = 1$), như đã chỉ ra ở phần trước, thuật toán có thể tìm được cặp ghép cực đại trong thời gian $O(mn)$. Tuy nhiên, ta có thể sửa đổi thuật toán chút ít để thu được thuật toán $O(m\sqrt{n})$, bằng thời gian thuật toán Hopcroft-Karp.

Ta thay đổi $\delta = \frac{1}{\sqrt{|I|}}$. Chú ý, với giá trị $\delta$ như vậy, ta có thể thực thi thuật toán như mô tả ở trên trong thời gian $O(m\frac{1}{\delta}) = O(m\sqrt{n})$. Theo $(3)$, đầu ra của thuật toán đấu thầu là một cặp ghép $M$ có ít hơn cặp ghép cực đại tối đa $O(\sqrt{|I|})$ cạnh. Do đó, ta chỉ cần áp dụng thuật toán đường tăng (augmenting path) mà ta đã học ở bài đầu tiên thêm $O(\sqrt{|I|})$ lần nữa là ta có thể thu được cặp ghép cực đại. Do mỗi lần tăng chỉ mất thời gian $O(m+n)$, tổng thời gian của thuật toán vẫn là $O(m\sqrt{n})$.

Tham khảo

[1] G. Demange, D. Gale, and M. Sotomayor. Multi-item Auctions. Journal of Political Economy 94.4 (1986): 863-872.