堵丁柱教授，11949年出生在齊齊哈爾市，978年在東北重型機械學(xué)院（今燕山大學(xué)）計算機系學(xué)習(xí)，1982年獲中國科學(xué)院碩士學(xué)位，1985年獲美國加里弗尼亞大學(xué)圣巴巴拉分校博士學(xué)位。1985年～1986年在美國加州伯克利數(shù)學(xué)科學(xué)研究院作博士后，1986～1987年在美國麻省理工大學(xué)數(shù)學(xué)系作訪問學(xué)者，1987年任中國科學(xué)院應(yīng)用數(shù)學(xué)所教授。他先后在美國伯克利大學(xué)（Berkeley）， 麻省理工大學(xué), 普林斯頓大學(xué)數(shù)學(xué)研究所工作。1991年和1995年成為 Minnesota大學(xué)計算機系的副教授和教授。 并于1998到1999年之間任職香港城市大學(xué)計算機科學(xué)系訪問教授。 1987-2002年為中國科學(xué)院應(yīng)用數(shù)學(xué)所研究員。

　　堵丁柱教授現(xiàn)任Texas 大學(xué)計算機系教授，美國自然科學(xué)基金委計算機理論的項目主管，也是西安交通大學(xué)教授。 他的研究方向包括組合優(yōu)化，計算機網(wǎng)絡(luò)和計算理論。

　　堵丁柱教授已經(jīng)發(fā)表論文60多篇， 出版了20本書。 他是組合優(yōu)化雜志和系列書籍《網(wǎng)絡(luò)理論和應(yīng)用》的主編， 是超過15個雜志的編委。 1998年獲得美國INFORMS的CSTS獎，1993年獲得中國自然科學(xué)二等獎， 1992年獲得中國科學(xué)院自然科學(xué)一等獎。

　　為了汲取西方新的知識，堵丁柱研究員1990年2月再次出國，在美國普林斯頓大學(xué)作訪問學(xué)者。才一個多月，即4月10日，他就和美國貝爾實驗室黃光明研究員合作攻克了吉爾伯特——波雷克猜想，即斯坦納比難題。所以堵丁柱研究員說，這個結(jié)果是在國外做完的，但是大量研究工作實際是在國內(nèi)做的。1990年10月正式公布以后，沒想到會引起國際數(shù)學(xué)界那樣廣泛注意和強烈反響，被列為1989年-1990年度美國離散數(shù)學(xué)界和理論計算機科學(xué)界重大成果。英國大百科全書在收錄這一成果時也評價說：“在過去的一年里，數(shù)學(xué)上最顯著的進展包括長期、著名的猜想——一個最短網(wǎng)絡(luò)的猜想……這個猜想就是斯坦納比問題。”

　　什么是斯坦納比問題呢？假設(shè)我們在北京、上海、西安三城市之間架設(shè)電話線，一種辦法是分別聯(lián)通北京——上海和北京——西安。另一種辦法是選第四個點，假設(shè)鄭州。由此分別向三城市架線，可能你不會想到第二種辦法所用的電話線只是第一種辦法的86.6%，即可取得比第一種辦法節(jié)約13%的顯著經(jīng)濟效益。這就是離散數(shù)學(xué)界30年代提出的著名的斯坦納比問題，但一直未能得到證明。直到1967年大名鼎鼎的貝爾電話公司，遇上了一家精明的用戶航空公司，竟被戳了一個大窟窿。這家用戶要求在第四個點的位置上架上電話線。這樣使得電話公司不僅要拉新線，增加服務(wù)網(wǎng)點，而且要減少收費。這件事的連鎖反應(yīng)迫使電話公司改變了堅持長達10年按照最少發(fā)生樹長度收費的原則，并且不得不對最短網(wǎng)絡(luò)問題進行研究。于是，貝爾實驗室數(shù)學(xué)中心主任波雷克和研究員吉爾伯特對斯坦納比問題作了許多研究，根據(jù)自己多年研究所得提出如下猜想：對歐氏平面上的任何有限點集，其最小的Steiner樹同最小發(fā)生樹的長度之比（稱為Steiner比，即斯坦納比）不小于√3/2.換言之，正三角形加點可以節(jié)省最多。但他們自己并沒有能證明它。

　　由于其在運輸、通信和計算機等現(xiàn)代經(jīng)濟與科技中的重要作用，近幾十年來它的研究進展越來越快。1985年，格拉姆和金芳容借助于計算機進行了大量運算，證明了斯坦納比大于0.824，雖距0.866不遙遠(yuǎn)，卻始終未能達到最終目標(biāo)。美國數(shù)學(xué)會主席曾感嘆道：“這問題已經(jīng)公開了22年，這件事總令你不安，你不能證明這樣初級的東西。”也許源于猜想提出的戲劇性背景，也許源于理論意義以及貝爾實驗室的學(xué)術(shù)權(quán)威，也許源于數(shù)學(xué)家對形成初等而又難解問題的愛好，人們對這個問題的研究歷久不衰。

　　1990年，41歲的堵丁柱因為攻克這一問題而成為世界數(shù)學(xué)界冒出的奇葩。他與貝爾實驗室黃光明研究員合作，找到了一個全新途徑，給出了吉爾伯特-波雷克猜想完整的證明。證明的核心是關(guān)于鞍點的一個定理。其主要思想是，首先在歐氏平面含n點的集合與2n-3維空間的點之間建立一一對應(yīng)的關(guān)系，使得猜想可以化為2n-3維空間上函數(shù)的極值問題。然后利用鞍點定理找出可以達到極值的臨界點應(yīng)滿足的必要條件。之后，再將此條件轉(zhuǎn)換為臨界點對應(yīng)的點集上的幾何性質(zhì)。最后，利用這幾何性質(zhì)確定幾何結(jié)構(gòu)，驗證該猜想。一個重要的注釋是，為獲得較易驗證的幾何結(jié)構(gòu)，他們將猜想先轉(zhuǎn)換為一個較強的形式，然后再如上法炮制。

　　證明于1990年10月在會議上正式公開，《紐約時報》立刻做了報道。接著《科學(xué)》雜志、《科學(xué)新聞》《新科學(xué)論》《SLAM新聞》等報刊上出現(xiàn)了許多報道。值得提及的《SLAM新聞》在頭版上用了個有趣的“在計算機時代歐氏幾何的歐氏平面上n點的集合←→2n-3維空間的點力與運氣”。在《不列顛百科全書1992年鑒》中，該證明進一步被列為入選的6項數(shù)學(xué)成果的第一項。因此，堵丁柱也榮獲了中國科學(xué)院自然科學(xué)一等獎、國家科技進步二等獎和中國青年科學(xué)家獎等殊榮。

　　Stewart教授對證明的意義作了闡述。12年前曾當(dāng)過堵丁柱的老師，12年后又配合堵丁柱攻克斯坦納比難題的貝爾實驗室研究員黃光明在興奮之余撰文記述了研究過程。他幽默地寫道：“如果要等我證出0.866的猜想才退休，那我可能要在貝爾實驗室過百歲生日了。解決這一問題的關(guān)鍵也許不在時間而在人，我能做的貢獻是找到一個比我強的人來作此問題。我找到了堵丁柱，而堵丁柱今年四月找到了答案�！�

　　每個成功者的背后，都會留下奮斗的足跡。探索一下堵丁柱的成才之路，或許對今天的青年朋友有所啟迪。

　　1996年堵的老師越民義在《運籌學(xué)雜志》發(fā)表文章，否定了堵的工作。

　　伯利克是個多霧的山城。早上，發(fā)動汽車前，要先擦去凝在風(fēng)擋上的水珠。頭頂，總是陰沉沉的不見太陽。可是，駕車上山后，景觀卻大不一樣。籠罩著的伯利克和舊金山的云霧已被踩到腳下。由陳省身創(chuàng)辦的數(shù)學(xué)所就坐落在加州大學(xué)伯利克校園背后的一座小山上。站著數(shù)學(xué)所的陽臺上，你可以俯瞰整個伯利克城，遠(yuǎn)眺舊金山的高檔大廈以及舉世聞名的金山大橋。

　　1985-1986年數(shù)學(xué)所以計算復(fù)雜性作為研究的主攻方向。這一年，有60多位實力雄厚的博士或即將獲得博士學(xué)位的研究生提出申請，最后只選了8名。堵丁柱在激烈的競爭中又一次獲勝，這成為圣巴巴拉數(shù)學(xué)系的一大新聞。系主任得到消息后馬上寫了一封賀信，每個教授見到他都表示了真誠的祝賀。

　　數(shù)學(xué)所在一座三層小樓里，樓內(nèi)十分講究、舒適，充分體現(xiàn)了陳省身先生當(dāng)初對設(shè)計者的要求：工作在這里，像置身于家中。每天下午3時，所里有一次點心和飲料供應(yīng)，其目的是讓教授們有互相接觸的機會，堵丁柱和卡波、替米爾、銳本等著名教授就是在邊吃邊談中相識并加深友誼的，對年輕的博士后來說，這里稱得上是得天獨厚、令人神往的地方。

　　在伯克利數(shù)學(xué)所的工作經(jīng)歷對一個數(shù)學(xué)家來說是重要的。這里節(jié)奏緊張，氣氛誘人。在一年的時間里，他大約寫了10篇論文。他與葛可一、龍格合作的關(guān)于單項函數(shù)和多項時間同構(gòu)的重要工作就是在1985年9月在伯克利完成的。

　　單項函數(shù)在存在性是涉及密碼學(xué)的重大理論問題。當(dāng)年的若干公共鑰匙密碼系統(tǒng)就是在假定這種函數(shù)的基礎(chǔ)上建立的。這樣，若單項函數(shù)不存在，這些系統(tǒng)也就不存在了。因此，對該問題的研究不僅具有理論意義，而且有經(jīng)濟意義和軍事意義。多項式的時間同構(gòu)問題是研究NP完全問題中產(chǎn)生的。NP完全問題是計算機科學(xué)中最重要的問題之一。1979年11月27日，《紐約時報》在報道哈契場算法時誤認(rèn)為NP完全問題已被解決，引起學(xué)術(shù)界大嘩。事實上，這一問題的答案不僅牽動著數(shù)學(xué)家和計算理論專家的心，而且牽動著許多經(jīng)濟界和軍事界專家的心。

　　1975年波曼和哈特曼尼斯猜想，所有NP完全問題是多項式時間同構(gòu)的。如果說該猜想被肯定，NP完全問題就可以解決。1982年，楊格和約瑟夫提出，這個猜測是否對，可能和單項函數(shù)的存在性有關(guān)。而堵丁柱等人的文章則第一次建立了兩者之間的關(guān)系，這就使得對多項式時間同構(gòu)的研究進入了一個高潮。1986年，在伯克利舉辦的計算機復(fù)雜性年會，為這一方向舉辦專題討論會，會議的組織者，貝爾實驗室的馬哈尼博士在其后的論文中寫道：這兩篇論文的主要結(jié)果是這領(lǐng)域中的最重要先進成果，由兩文引入的技巧是有力的。

　　1986-1987年是伯利克數(shù)學(xué)所的代數(shù)數(shù)論年，搞計算復(fù)雜性的學(xué)者們便各奔東西了。堵丁柱接受麻省理學(xué)的聘請，以訪問助理教授的身份開始了與克拉依曼教授的合作。事隔4年從不能接收作正式研究生到可以作助理教授，變化之大，令人感慨萬端。

　　麻省理工學(xué)院是一所舉世聞名的大學(xué)，它座落在查理士河畔，與波士頓的高大建筑群隔河相望。樓內(nèi)走廊的墻上，掛滿了為科學(xué)技術(shù)作出重大貢獻的教授們的歷史圖片，這使人一進其中，就體驗到它的歷史悠久和碩果累累。在應(yīng)用數(shù)學(xué)方面享有很高聲望的林加翹教授就在這里工作。幸運的是，堵丁柱的辦公室被安排在林教授的斜對面，使他有機會經(jīng)常當(dāng)面聆聽先生的教誨。在教書之余，堵丁柱充分利用業(yè)余時間，同這里的教授和訪問學(xué)者們探討問題。在此期間，他完成了9篇論文，并在另外的項目上也取得了有意義的進展。

　　在麻省理工學(xué)院期間，堵丁柱和章祥蓀合作的羅素梯度投影收斂的論文刊印出來了。

　　羅素梯度投影方法是解決帶約束非線性規(guī)劃問題的基本方法。自1960年羅素提出這個方法以來，收斂問題一直沒有解決。此后，幾乎每個討論該方法的教科書都要提及這個問題，使這個問題成為非線性規(guī)劃領(lǐng)域中較有名的長期未解決的問題之一。早在1980年，在越民義教授和韓繼業(yè)教授的指導(dǎo)下，堵丁柱對羅素投影法曾作過較系統(tǒng)的學(xué)習(xí)和研究，在碩士畢業(yè)論文中，又解決了梯度投影的退化處理問題。在此后的工作中，他又簡化了由泡拉克提出、章祥蓀教授改進的一種羅素梯度投影法的變形，并且以反例證實了在某種特殊情況下，原算法是可以不收斂的。1986年刊出的與章祥蓀教授合作的論文是在1984年完成的，這篇論文的主要結(jié)論是，一般說來，羅素算法提供的技巧是可以使算法收斂的。因此，基本解決了這個問題。羅素本人在后來的一封信中肯定了他們的工作。他寫道，我想祝賀你們，你們最近的工作，最終解決了和我的原始論文相關(guān)聯(lián)的收斂性問題。

　　在堵丁柱的論文目錄分類中有可靠性理論題目。他對這方面的研究是從證明德曼·勒伯曼和羅斯猜測開始的。他們的猜測是關(guān)一種概率模型中幾個性質(zhì)相同但工作概率不同的部件的最優(yōu)分配。堵丁柱與黃光明合作，在1982年年初得出完全的證明，并且建立了一些較一般的定理用于解決最優(yōu)分配的問題。在紐約期弟文斯工學(xué)院舉辦的可靠性會議上，他被邀請報告了該問題及有關(guān)成果。

　　在麻省理學(xué)院的研究工作中，堵丁柱給克拉依曼教授印象最深的是關(guān)于他本人的一個猜測的證明。這個猜測是關(guān)于曼哈頓格中具有給定直徑最大的集約性質(zhì)。教授萬沒有想到，這位中國學(xué)者在證明中使用了與他提出猜測論文中相同的技巧，在不長的時間里卻獲得了出人意外的成功。

　　在伯克利期間，堵丁柱和陳省身教授經(jīng)常在一起談心。他們的研究領(lǐng)域不同，但卻說得來。他們都有一個共同的心愿，就是要讓中國的數(shù)學(xué)界跨入世界先進行列。有一次，他們談到這樣一個問題：要讓中國的數(shù)學(xué)界走在世界前列，就要有人作出一定的犧牲，起紐帶作用，回到目前還落后的祖國去工作。這對研究工作正處于鼎盛時期的年輕博士們來說不能不是一個難題。堵丁柱說，這種犧牲是值得的，他一定會在祖國大陸上與陳先生相會。

　　堵丁柱說到做到，就在他事業(yè)上一帆風(fēng)順蒸蒸日上的時候，毅然作出了馬上回國的決定，棄麻省理工學(xué)院的名位高薪不顧，可以得到綠卡也不動心，扔下洋房，賣掉汽車，攜妻子返回祖國。有人感到不理解。他樸實地說，很難回答為什么要回來的問題�；貒�，談不上崇高。從良心上講一種責(zé)任，受了國家這么多年的培養(yǎng)，總覺得有點兒欠。我只覺得，年輕時不回國效力，等老了會感到遺憾的。

　　科學(xué)家看重自己的生命，國內(nèi)的研究工作條件明擺著不如國外，個人的事業(yè)不能不受影響。堵丁柱對此也有他的見解。他認(rèn)為，對科學(xué)家來說，事業(yè)有兩種，一種是完全科學(xué)上的事業(yè)，就是指在科學(xué)上作出很大的結(jié)果。另一種是讓落后的趕上先進行列，這更是一件很有意義的工作，他說，我回到祖國，可能研究工作會受到一些影響，但在第二種事業(yè)上我可能會有所補償。語調(diào)平緩卻是擲地有聲。

　　堵丁柱學(xué)成回國三年堅持獨立自主地進行科學(xué)研究，在數(shù)學(xué)的王國里遨游，終于攻克了期坦納比難題，他并未停止自己前進的腳步。為了在計算機科研領(lǐng)域占一席之地，參與國際的激烈的競爭，他進入了電子計算機新的領(lǐng)域，并且為推動我國與國際的數(shù)學(xué)界交往，開擴青年科學(xué)工作者的眼界，他在周光召院長的資助下創(chuàng)辦了系列數(shù)學(xué)國際會議，現(xiàn)已開過三次，并著書立說，指導(dǎo)國內(nèi)外學(xué)生瞄準(zhǔn)數(shù)學(xué)領(lǐng)域的重大課題進行攻關(guān)。

　　事業(yè)上的成就卓著的人可以稱作是明星，可是這兩個字怎么能包容下堵丁柱那顆熱愛祖國的赤子之心呢？他是一個普通人，他又是被耽擱的一代人中的杰出代表。他沒有怨天尤人去詛咒命運不公，更不肯無所作為地在嘆息中消沉。他有堅定的信念和樂觀向上，他說后天的努力比天才更重要，他有執(zhí)著的追求，所以他成功了。我們偉大的祖國也將因這一代人的崛起而更有希望！