Articles in Turing Academy cover three major themes: ESG Net Zero Laboratory, AI Laboratory and Lean Management Laboratory. We will share articles on related topics from time to time. We also welcome students who are interested in the above topics to submit articles and share them with you. Insights (I want to contribute)

跨越數學疆界的演算法盛宴：Shayan Oveis Gharan 榮獲算盤獎與 TSP 歷史性突破

 


科楠老師
2026-7-27

 

    華盛頓大學（University of Washington）教授 Shayan Oveis Gharan 榮獲國際數學聯盟（IMU）頒發的算盤獎（Abacus Medal）。該獎項旨在表彰在資訊科學數學理論領域做出傑出貢獻的學者。Oveis Gharan 獲獎的核心成就之一，正是他與 Anna R. Karlin 及 Nathan Klein 合作，成功跨越了理論計算機科學領域沉寂長達 40 多年的經典高牆，打破了度量型旅行推銷員問題（Metric TSP）的 3/2 近似比極限。這項突破不僅解決了一個懸案已久的大難題，更展現了將代數幾何、概率論、譜圖論與組合最佳化深度融合的極致美感。


世紀難題：旅行推銷員問題與 44 年的「1.5 倍高牆」

 

    旅行推銷員問題（Traveling Salesperson Problem, TSP）是組合最佳化領域最著名的 NP-hard 難題之一。這也是科楠老師的研究專長之一。簡單來說，目標是為一位推銷員規劃一條最短的巡迴路線，使其經過所有指定城市並最終回到起點。在實際應用中，城市間的距離通常滿足「三角不等式」（即從城市 A 直達城市 B 的距離，絕不會大於經由城市 C 中轉的距離），這種情況被稱為度量型 TSP（Metric TSP）。

(距離滿足：Dist(A,B) <= Dist(A,C) + Dist(C,B))


    早在 1976 年與 1978 年，學者 Nicos Christofides 與 Anatolii Serdyukov 分別獨立提出了一個極其優雅的近似演算法（簡稱 Christofides-Serdyukov 演算法）：

 

1. 最小生成樹（MST）：首先在城市網絡中構建一棵覆蓋所有頂點且總成本最低的「最小生成樹」。


2. 奇數頂點匹配（Matching）：檢查生成樹中所有「度數（連接邊數）為奇數」的頂點，並找出這些頂點之間總成本最低的完美匹配。


3. 路線重構：將生成樹與完美匹配結合形成歐拉圖（Eulerian Graph），再利用三角不等式進行跳點縮短（Shortcut），得到最終的巡迴路線。

 

這個演算法保證輸出的路線成本最多不會超過最優解（OPT）的 3/2倍（即 1.5 倍）。然而，自 1970 年代以來，儘管學界在平面 TSP、歐幾里得空間 TSP、圖度量 TSP 等特殊限制條件下取得許多進展，但對於一般度量型 TSP，3/2這個瓶頸就像一座無法逾越的大山，整整 44 年無人能跨越半步。


破局之道：從確定性樹到「最大熵隨機生成樹」

 

    Shayan Oveis Gharan 與其合作者在論文《A (Slightly) Improved Approximation Algorithm for Metric TSP》中，給出了打破歷史紀錄的解答：

 

主要定理（Theorem 1.1）：存在一個隨機化多項式時間演算法，其輸出的巡迴路線期望成本最多為最佳解成本的(3/2 - Ɛ) 倍，其中常數 Ɛ > 10-36。
 

看似微小的常數 Ɛ，在理論計算機科學界卻是一場大地震。這意味著 3/2並非不可逾越的理論終點。

 

演算法的核心思維轉變

 

    傳統演算法選擇的是「確定性」的最小生成樹，而 Oveis Gharan 等人的創新在於引進隨機採樣與線性規劃鬆弛（Linear Programming Relaxation）的結合：

 

 

關鍵的核心在於：如果我們能以最大熵（Maximum Entropy）原則採樣生成樹，使其邊的出現邊際概率（Marginal Probability）精準吻合 Held-Karp 線性規劃的解，那麼生成樹中奇數度數頂點的出現規律將具備非常特殊的結構性質。


跨學科數學工具箱：強雷利分布與代數幾何的交響曲

 

    為什麼過去 40 多年學界無法分析隨機生成樹帶來的奇數匹配成本改善？因為常規的概率分析在面對圖論中複雜交織的割集（Cuts）時會徹底失效。Oveis Gharan 展現了其極具標誌性的跨學科研究風格，將現代高級數學工具引入演算法分析中。

 

1. 強雷利分布（Strongly Rayleigh Distributions）與負相關性

 

    在概率論與代數幾何中，實穩定多項式（Real Stable Polynomials） 是一類極其優秀的多變量多項式。如果一個隨機變數分布的生成多項式是實穩定的，該分布就被稱為強雷利分布（SR Distributions）。生成樹的分布正是典型的強雷利分布。這類分布具備深刻的負相關性（Negative Association）：

 

  • 當我們知道邊 e1被選入生成樹時，鄰近的邊 e2被選入樹中的概率傾向於降低。

  • 這種負相關性保證了隨機生成樹不會在某個區域局部「扎堆」，從而讓頂點度數的奇偶分布更為均勻與可控。

 

2. 推廣的 Gurvits 引理（Generalized Gurvits' Lemma）

 

    著名數學家 Leonid Gurvits 曾利用實穩定多項式證明了多元不等的 Gurvits 引理。在這篇論文中，作者們將其大幅推廣：

  • 非正式命題（Proposition 5.1）：對於一個強雷利分布，即使變數的期望值不完全等於 1，只要在多個不相交子集上的採樣數量滿足一定條件，多個特定事件同時發生的概率就能獲得一個不依賴於底層圖規模 n的常數下界。

 

這項推廣為分析生成樹中多個割集同時維持良好Parity（奇偶性）提供了穩固的概率下界。

 

3. 保持邊際概率的條件概率技巧（Conditioning while Preserving Marginals）

 

    通常情況下，如果我們對概率分布進行條件限制（例如：強制要求某個割集 A 和 B各採樣 1 條邊），其餘邊的邊際概率可能會發生劇烈扭曲。Oveis Gharan 等人證明了一個極其強大的理論結果：

 

  • 定理（Theorem 1.7 / Proposition 5.6）：在強雷利分布下，存在一個概率不為零的特定事件 εA,B，在該事件發生的條件下，集合 A 與 B的採樣數精準為 1，同時其餘所有邊的邊際概率依然被極佳地保持（全變差距離變差極小）。

 

這一技巧使得研究團隊能在不破壞線性規劃整體結構前提下，局部「修剪」生成樹的邊際分佈。


割集幾何與多邊形結構（Polygon Structure）

 

    除了概率工具，論文在圖結構理論上也帶來了深刻突破。為了證明奇數匹配的成本可以嚴格低於 1/2 OPT，作者需要對圖中的近最小割集（Near-Minimum Cuts）進行幾何剖析。


圖reference: Karlin et al., 2023

 

論文引入並完善了近最小割集的分層結構與多邊形表示法：

 

  • 原子與多邊形（Atoms & Polygons）：近最小割集可以被簡化並排列在多邊形頂點上。團隊證明，只需專注於單側相交的特別多邊形結構，即可涵蓋所有需要處理的複雜割集。
  • 鬆弛向量構造（Slack Vectors  s  and s*）：團隊構造了一套動態鬆弛向量：

  • 當某些特定割集在隨機樹中變為偶數（Even Cut）時，對應邊的鬆弛成本可以被嚴格扣減（se  ≤ βχe）。

  • 當割集變為奇數時，再利用相鄰的邊或最優解（OPT）邊進行補償。


論文證明，綜合所有割集與條件概率後，這套機制能夠保證對應奇數頂點匹配（O-join）的期望總成本嚴格小於( 1/2 - ε) OPT。

 

為什麼常數 ε > 10-36 依然是世紀突破？


    許多非專業讀者可能會好奇：ε > 10-36 這個數字小到在實際工程中根本無法感知，為什麼它能獲得學術界如此高的尊崇，甚至成為算盤獎的核心評獎依據？

 

理論計算機科學中的「0 到 1 飛躍」
在複雜度理論中，從「不可能（無演算法能打破 1.5）」到「可能（存在演算法打破 1.5）」是一條不可逾越的鴻溝。10-36 的出現證明了 Christofides 的 3/2 並非數學真理的終點。一旦這扇封印 44 年的大門被推開，後續研究者就能沿著這套新建立的數學框架，進一步將常數提升至更具實用價值的範圍。
 


結語：跨學科數學的勝利

 

    Shayan Oveis Gharan 獲頒算盤獎，不僅是對他個人才華的肯定，更是現代演算法理論發展方向的一個縮影。這篇打破 TSP 44 年紀錄的論文深刻地證明：當代最前沿的演算法突破，早已不再局限於傳統的組合技巧或單一演算法結構，而是深植於高維代數幾何、分析學、機率論與圖論的深度交匯點。Oveis Gharan 用他的工作為我們展示了一幅宏大的數學圖景，跨越學科邊界，用抽象數學的力量，照亮理論計算機科學最深邃的角落。

 

 

Reference
1.Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan (2023), A (Slightly) Improved Approximation Algorithm for Metric TSP, arXiv, 
https://doi.org/10.48550/arXiv.2007.01409
2.2026 Fields and Abacus Medals: A Master of the Traveling Salesperson Problem Finds His Own Path