本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
Karmarkar-Karp 差分演算法是最著名的數位分割問題多項式時間啟發式演算法，是理論電腦科學和統計物理學的基礎。我們透過將差分演算法映射到非線性速率方程式來分析差分演算法在隨機實例上的表現。我們的分析揭示了強烈的有限尺寸效應，這解釋了為什麼很難透過模擬建立差分解的精確漸近性。從速率方程中出現的漸近級數滿足 Karmarkar-Karp 演算法的所有已知界限，並投影縮放 n(-c ln n) ，其中 c = 1/(2 ln 2) = 0.7213 ....我們的計算揭示了該演算法和類斐波那契序列之間的微妙關係，並且我們為此建立了明確的恆等式。