我的研究工作與作品

吳邦一(Bang Ye Wu), 2004/6

【出發】

1995年9月我進入清大資工系攻讀博士學位，就此開始了我的研究工作。在選定計算生物學做為研究之主題後，即開始survey，由於是一個完全陌生的領域自己又是十足的菜鳥，survey的工作做的很辛苦。很快的發現sequence與tree是這個領域演算法問題的兩大塊，而立刻就對演化樹問題感到興趣，在時間上的壓力下，我很快的在1996年8月完成了我第一個非常簡單的作品：「如何決定一個物種在一個已知演化樹上的位置」[IPL97]。

所謂Distance-base的演化樹建構問題是給定一群物種之間的差異程度，要尋求一個以這群物種為leaf的樹狀結構而最佳化某個objective function，Farach於95年發表在Algorithmica的作品是我當時研究這個問題很重要的一個參考。「理論上有沒有辦法突破實無把握，於是先做苦工吧」，憑藉著多年來所鍛鍊的programming能力，在1997年5月完成了「以branch-and-bound方式求minimum ultrametric tree」的研究[JoCO99]。

演化樹問題與Steiner tree問題非常類似，「未知spanning tree，焉知Steiner tree」在這樣的想法下，開始研究「給定一群物種之間的距離，如何建構一以這群物種為節點的樹狀結構而使得兩兩之間的距離和為最小」的問題，survey後發現在圖形演算法的世界裡，此問題稱為「shortest total path length spanning tree」在1980年左右提出了兩倍誤差之演算法分析後即無下文，於是我們將目標放在此問題的近似演算法上並於1997年5月完成了(4/3+e)的近似演算法[DAM00a]。

【獵狐不成總算喝到汽水】

97年的研究工作緊湊到無法喘息，在研究問題時我們碰到一個困難，使得所採用的方法只能做到(4/3+e)倍的演算法，於是我們將結果submit到journal也submit到FOCS，在此同時我們已經意識到，如果是metric graph (完全圖且滿足三角不等式)，幾乎可以確定可以做到PTAS (polynomial time approximation scheme)，但是有一個先要解決的問題：「在metric graph上這個問題是不是NP-hard？」。我還記得當時和唐老師一起拿著Garey&Johnson的書一個問題一個問題的找，看看用哪個問題來做reduction。6月，我們找到了一個非常漂亮的transformation，不但可以證明metric上此問題是NP-hard，而且metric上的PTAS也是general graph上的PTAS，這個reduction不是從別的問題來，而是將此問題的general版本reduce到他的metric版本。在五月FOCS放榜時，在通知我們獵狐不成的同時，Editor告知我們這世界上有另一組人（G. Lancia, V. Bafna, R. Ravi）也在做相同的問題，並建議我們的研究結果合併，由於時間的因素，在SODA截稿前我們雙方都尚未能取得對方的結果，雙方在擔心被對方幹掉的緊張情緒下，大家都將盡量衝刺，他們加入了可以將Bartal的成果運用在OCT的內容而我們將剛找到的PTAS投稿到SODA，最後我們在editor的建議下合併發表，由於我們的分析比他們精緻的多而同意由我擔任第一作者，並且在11月直接revise他們submit到SICOMP (SIAM J. Computing)的作品而順利的於99年發表於 [SICOMP99]。至此，我們對樹與序列兩大問題有了比較深刻的了解。

【MRCT問題的延伸】

在MRCT問題獲得成果後，我們很自然的期望其結果也能運用到更一般化的問題，這一系列的問題之間的關聯如下圖：

在MRCT問題上，兩點之間的需求量是相同的，而此問題的最一般化結果為OCT問題，其兩點之間的需求量是任意的，試圖對中間問題進行研究，我們將焦點對準PROCT，在此問題上兩點之間的需求量為兩點權重之乘積，以及SROCT（兩點之間的需求量為兩點權重之和）。在98年1月，成功發展出常數倍數的近似演算法[DAM00b]，再接再厲，98年11月，我們又成功的運用scaling and rounding的技術，將PROCT做到了PTAS [JoA00]。除了這一系列的問題之外，我對與樹狀結構有關的演算法問題都有相當的興趣，98年6月，我們研究了在樹上如何快速的找出長度限制下的最重路徑[IPL98]。

【再出發】

1999年4月，結束了清大的學生身分，返回軍中的工作崗位，軍中的工作與演算法或計算生物學沒什麼關係，工作也十分繁忙，由於無法忘情於研究工作，我在工作之餘對minimum latency problem做了一點研究。給定一個圖以及一個起點，此問題要求一個路徑使得各點等待時間之總合為最小，這個問題與TSP有點像但是更難，TSP問題在系統的觀點求成本最小而此問題是在客戶角度求服務品質最好，這是個非常有趣的問題也吸引了許多研究好手投入，我們提出了一個充分條件說明具有什麼性質的圖可以用dynamic programming來得到polynomial time的解，同時也探討了此問題的變形：如何決定起點[IPL00]。

2000年，由於一些外在的因素變遷，使得我可以有機會自由選擇是否留在原工作崗位，也就是說我可以解甲歸田了，這個消息對我是個重大的衝擊，原本以為與自己熱愛的演算法研究已經無緣，此時卻又死灰復燃，正如同94年以前以為不可能有機會進修博士學位，誰知又會峰迴路轉給我一個機會。這是一個需要勇氣的抉擇，當時我已經升副研究員了，離開軍中到學校，不但要從最資淺的助理教授開始而且要放棄2004年就可達到的月退俸資格，此外，我不見得有機會能夠爭取到大家所認為的理想環境。

為了不使自己將來後悔（個人興趣與家庭的因素），我決定到樹德科大繼續自己的研究興趣，充分的尊重與合理的制度，對我而言，這是非常理想的環境了。重新暖機花了些時間，我還是從演化樹開始，但是這一次不專注於distance-base，我對triplet method進行研究，給定一些三者之間的關係（triplet），這個問題在求出一個演化樹以滿足最多的triplet，2001年5月，我們提出dynamic programming的方法以及一些heuristic的方法，利用程式實驗（苦工）進行效益的分析，同時也包括前人所提出之方法，其結果發表於[JoCO04]，在這個問題上，我們又做了一些改進的方法，研究如果在DP的過程中不保留所有的結果，犧牲部分品質以加快執行時間的方法，其結果發表於[JISE04]。

對於MRCT問題族群仍未忘情，在1999年時我們對平衡一個樹的routing cost與building cost有一些結果投稿至Networks，2000年12月我們把這個部分做的更完整並直接revise先前的作品而成功的被接受發表[Net02]，我開始研究MRCT在多起點（multi-source）的版本，2001年8月證明了對兩個起點，此問題皆屬NP-hard，同時我們提出兩個起點時，此問題的PTAS [JoA02]，其中也包括weighted版本時在metric上的PTAS。另外，對於任意固定起點數，我們證明此問題皆屬NP-hard，並且提出metric graph上固定起點數而任意需求量時之兩倍近似演算法以及general graph上兩個起點任意需求量之3倍近似演算法，其結果已被接受發表[DAM04a]。在多起點的問題上我們也研究maximum eccentricity問題，兩點之間的距離是兩個點之間的最近路程，eccentricity是一個圖上之最遠距離（max-min），在多起點問題上，是要求的一個spanning tree使得起點至其他點之最遠距離要最小，在這個問題上，我們改進了別人的結果得到一個更有效率的polynomial time演算法[DAM04b]。

除了研究工作之外，2003年，我與趙坤茂教授合作，將近年來在spanning tree問題上的研究進展寫成了一本書Spanning Trees and Optimization Problems，由Chapman & Hall / CRC於2004年一月出版[Book04]，雖然只是一本小書，我花了很多時間，對我而言，這是難得的經驗。

【未完待續】

除了上述的作品，目前仍有一些研究在進行中。2003年8月，接了系上的行政工作，工作有時繁瑣，難免阻礙了時間但不能減低熱情，網路世界無遠弗屆，在研究的領域，更加沒有距離，無論身處何處，能夠與世界上的一流好手競爭與合作，是多麼有趣的事啊！路，還要繼續… (June, 2004)

作品清單

[IPL97] Wu, B.Y. and Tang, C.Y. (1997)," An O(n) algorithm for finding an optimal position with relative distances in an evolutionary tree", Information Processing Letters, vol. 63, pp. 263-269. [SCIE, EI]

[IPL99] Wu, B.Y., Chao, K.M., and Tang, C.Y. (1999), “An efficient algorithm for the length-constrained heaviest path problem on a tree”, Information Processing Letters, vol. 69, pp. 63-67. [SCIE, EI]

[JoCO99] Wu, B.Y., Chao, K.M., and Tang, C.Y. (1999), “Approximation and exact algorithms for constructing minimum ultrametric trees from distance matrices”, Journal of Combinatorial Optimization, vol. 3, pp. 199-211. [SCIE, EI]

[SICOMP99] Wu, B.Y., Lancia, G., Bafna, V., Chao, K. M., Ravi, R., and Tang, C.Y. (1999), “A polynomial time approximation scheme for minimum routing cost spanning trees”, SIAM J. on Computing, vol. 29, no. 3, pp. 761-778. [SCI,EI]

[DAM00a] Wu, B.Y., Chao, K.M., and Tang, C.Y. (2000), "Approximation algorithms for some optimum communication spanning tree problems", Discrete Applied Mathematics, vol. 102(3), pp. 245-266. [SCI,EI]

[DAM00b] Wu, B.Y., Chao, K.M., and Tang, C.Y. (2000), “Approximation algorithms for the shortest total path length spanning tree problem”, Discrete Applied Mathematics, vol. 105, pp. 273-289. [SCI,EI]

[JoA00] Wu, B.Y., Chao, K.M., and Tang, C.Y. (2000), " A polynomial time approximation scheme for optimal product-requirement communication spanning trees”, Journal of Algorithms, vol. 36, pp. 182-204. [SCI,EI]

[IPL00] Wu, B.Y. (2000), "Polynomial time algorithms for some minimum latency problems", Information Processing Letters, vol. 75(5), pp. 225-229. [SCIE, EI]

[Net02] Wu, B.Y., Chao, K.M., and Tang. C.Y. , (2002), "Light graphs with small routing cost", Networks, vol. 39(3), pp. 130-138, [SCI,EI]. (NSC 90-2213-E-366-005)

[JoA02] Wu, B.Y. (2002), “A polynomial time approximation scheme for the two-source minimum routing cost spanning trees”, Journal of Algorithms, vol. 44(2), pp. 359-378, [SCI,EI] (NSC 91-2213-E-366-004).

[JISE04] Wu, B.Y. (2004), “Constructing evolutionary trees from rooted triples”, Journal of Inforamtion Science and Engineering, vol. 20(1), pp. 181-190. [SCIE, EI] (NSC 89-2218-E-266-003)

[JoCO04] Wu, B.Y. (2004), “Constructing the maximum consensus tree from rooted triples”, Journal of Combinatorial Optimization, vol. 8(1), pp. 29-39,. [SCIE, EI] (NSC 89-2218-E-266-003)

[DAM04a] Wu, B.Y., “Approximation algorithms for the optimal p-source communication spanning tree”, to appear in Discrete Applied Mathematics. [SCI,EI] (NSC 92-2213-E-366-001)

[DAM04b] Wu, B.Y., “An improved algorithm for the k-source maximum eccentricity spanning trees”, to appear in Discrete Applied Mathematics. [SCI,EI]

[Book04] Wu, B.Y. and Chao, K-.M. (2004), Spanning Trees and Optimization Problems, ISBN: 1584884363, Chapman & Hall / CRC