結對編程的分配問題

01-29

現實世界:

公司高層學到了結對編程(pair programming)這個概念. 對於每一個任務, 要保證有兩個程序員同時在編. 於是此高層下令任何任務必須有兩個程序員同時在寫. 一個任務要麼兩個程序員在做, 要麼沒有人做. 每個任務只能被分配給擁有解決這個任務的能力的程序員. 那麼是否可以保證至少k個任務被分配出去呢?

可以得到下面的一個問題:

給一個二分圖 $G=(Acup B, E)$ . 找到一個"匹配" $Msubset E$ , 使得在 $G=(Acup B, M)$ 里,

1. 每一個A的頂點 $v$ , $deg(v) in {0,t}$ . 且 $deg(v)=t$ 的頂點至少有k個.

2. 每一個B的頂點 $v$ , $deg(v) in {0,1}$ .

這裡的M叫做t匹配.

t=1的時候, 是常見的二分圖匹配問題.

t=2的時候, 就是我們要解決的問題.

t=3的時候, 這個問題是3-dimensional matching, 是NP-hard的. 所以還好沒有什麼trio programming...

那麼t=2的時候問題可以多項式時間解么? 另一個同樣的描述方法, 是找到k個的vertex disjoint的 $K_{1,2}$ , 使得center在A裡面. 一般人會猜這個是NP-hard的問題. 因為如果同樣的問題, 不要求center在A裡面的話, 那就是NP-hard的.

這個問題是可以多項式時間解答的. 可以規約到最大權值完美匹配.

方法如下.

創建一個新的圖 $G=(V,E)$ . 假設 $|B|=n$ .

$C={t_1,ldots,t_{n-2k}}$ , 是一個有 $n-2k$ 個新頂點的集合.

$V = Acup { v_1,v_2 | vin B}cup C$

對於每一個 $vin A$ , 有一個邊 $v_1v_2$ , 權值0.

對於每一個 $vin A, uin B$ , 有邊 $v_1u$ 和 $v_2u$ ,權值都為1.

對於每一個 $vin A,uin C$ , 有邊 $uv$ , 權值為0.

原來的問題有解, 有且僅有在 $G$ 上的最大權值完美匹配的值為 $2k$ .

原先的問題的有權值的版本也能用類似的方法做出來.

現實世界:

由於結對編程導致程序員強烈不滿, 高層允許梨子編程(pear programming).

Open problems:

1. 如果每一個邊上都有權值w, 然後2-匹配 M 的值為 $c(M) = sum_{a in V} min { w(e) | a in b in M}$ . 如何找到值最大的2-匹配? 因為pair programming的時會被弱一點的人拉後腿. [幾乎解決: NP-hard, 存在2-approximation, APX-hard. 不知道是否存在更好的approximation]

2. $Asubseteq A$ 叫做nice, 如果存在一個2-匹配,使得 $A$ 里每一個頂點的度都是2. 找到最少的nice集合, 使得他們的並集是A. [已解決: OPT+1-approximation!]

3. $Bsubseteq B$ 叫做nice, 如果存在一個2-匹配,使得 $B$ 里每一個頂點的度都是1. 找到最少的nice集合, 使得他們的並集是B. [已解決: 存在多項式時間解]

4. 一個scheduling問題的拓展: scheduling on unrelated parallel machines minimizing makespan allowing preemption, 加上一個新的條件: 任何時候一個job要有兩個worker, 而且有些worker不能做某些job. [已解決: 存在多項式時間解]