堵丁柱

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

堵丁柱教授現任德克薩斯大學達拉斯分校（UTD）計算機系教授，美國自然科學基金委計算機理論的項目主管，也是西安交通大學教授。他的研究方向包括組合優化，計算機網路和計算理論。

堵丁柱教授已經發表論文60多篇，出版了20本書。他是組合優化雜誌和系列書籍《網路理論和應用》的主編，是超過15個雜誌的編委。 1998年獲得美國INFORMS的CSTS獎，1993年獲得中國自然科學二等獎， 1992年獲得中國科學院自然科學一等獎。

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

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

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

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

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

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

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

但是，1996年堵的老師越民義在《運籌學雜誌》發表文章，對堵的文章表示有若干問題，並表示沒有看懂。

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

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

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

在伯克利數學所的工作經歷對一個數學家來說是重要的。這裡節奏緊張，氣氛誘人。在一年的時間裡，他大約寫了10篇論文。他與葛可一、龍格合作的關於單項函數和多項時間同構的重要工作就是在1985年9月在伯克利完成的。

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

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

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

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

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

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

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

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

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

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

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

堵丁柱學成回國三年堅持獨立自主地進行科學研究，在數學的王國里遨遊，終於攻克了期坦納比難題，他並未停止自己前進的腳步。為了在計算機科研領域佔一席之地，參與國際的激烈的競爭，他進入了電子計算機新的領域，並且為推動我國與國際的數學界交往，開擴青年科學工作者的眼界，他在周光召院長的資助下創辦了系列數學國際會議，現已開過三次，並著書立說，指導國內外學生瞄準數學領域的重大課題進行攻關。

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