Karmarkar's algorithm

愛娃·塔多斯 - 在强多项式时间内求解网络中的最小费用环流。 Narendra Karmarkar（英语：Narendra Karmarkar） - 线性规划中的Karmarkar算法（英语：Karmarkar's algorithm）。 1991: Martin E. Dyer, Alan M. Frieze

1984年，貝爾實驗室印度裔數學家納倫德拉·卡爾瑪卡爾（英语：Narendra Karmarkar）提出了投影尺度法（又名卡爾瑪卡爾演算法（英语：Karmarkar's algorithm））。這是第一個在理論上和實際上都表現良好的算法：它的最壞情況僅為多項式時間，且在實際問題中它比

39–57. MR 2115066. doi:10.1090/S0273-0979-04-01040-7 .  Chambolle, Antonin; Pock, Thomas. A First-Order Primal-Dual Algorithm for Convex Problems with Applications

time）。实际上除了符合以上定义的演算法，其他一些演算法也拥有次线性时间的时间复杂度。例如有O(n½) 葛羅佛搜尋（英语：Grover's algorithm）演算法。 常见的非合次线性时间演算法都采用了诸如平行处理（就像NC1 matrix行列式计算那样）、非古典處理（如同葛羅佛搜尋那樣），又

1962年，他與邁克爾·赫爾德（Michael Held）共同開發了赫爾德-卡普算法（英语：Held–Karp algorithm），這是一種針對旅行推銷員問題的精確指數時間算法。 1971年，他與傑克·埃德蒙茲（英语：Jack Edmonds）共同開發了埃德蒙茲-卡普