‹ 返回

跨越數學疆界的演算法盛宴：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）：

 

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

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

 

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）時，對應邊的鬆弛成本可以被嚴格扣減（s_e  ≤ βχ_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