อัลกอริทึมของคาร์มาร์การ์เป็นอัลกอริทึม ที่ นเรนทรา คาร์มาร์การ์คิดค้นขึ้นในปี 1984 เพื่อแก้ปัญหาการเขียนโปรแกรมเชิงเส้น เป็น อัลกอริทึมแรกที่มีประสิทธิภาพพอสมควรที่สามารถแก้ปัญหาเหล่านี้ได้ใน เวลาพหุนามวิธีการวงรีก็ใช้เวลาพหุนามเช่นกัน แต่พิสูจน์แล้วว่าไม่มีประสิทธิภาพในทางปฏิบัติ

โดยกำหนดให้เป็นจำนวนตัวแปรmเป็นจำนวนข้อจำกัดความไม่เท่าเทียมกัน และเป็นจำนวนบิตของอินพุตไปยังอัลกอริทึม อัลกอริทึมของ Karmarkar ต้องการการดำเนินการกับตัวเลขหลัก n เมื่อเทียบกับการดำเนินการดังกล่าวสำหรับอัลกอริทึมทรงรี^{[ 1 ]}ในปัญหา "สี่เหลี่ยม" เมื่อmอยู่ใน O( n ) อัลกอริทึมของ Karmarkar ต้องการการดำเนินการกับตัวเลขหลัก n เมื่อเทียบกับการดำเนินการดังกล่าวสำหรับอัลกอริทึมทรงรี ดังนั้นเวลาการทำงานของอัลกอริทึมของ Karmarkar จึง ใช้การคูณแบบ FFT (ดูสัญกรณ์ Big O ) ${\displaystyle n}$${\displaystyle L}$${\displaystyle O(m^{1.5}n^{2}L)}$${\displaystyle O(L)}$${\displaystyle O(n^{3}(n+m)L)}$${\displaystyle O(n^{3.5}L)}$${\displaystyle O(L)}$${\displaystyle O(n^{4}L)}$$${\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L),}$$

อัลกอริทึมของ Karmarkar จัดอยู่ในกลุ่มของวิธีการจุดภายใน : การคาดเดาปัจจุบันสำหรับคำตอบไม่ได้ติดตามขอบเขตของเซตที่เป็นไปได้เหมือนในวิธีการซิมเพล็กซ์แต่เคลื่อนที่ผ่านภายในของพื้นที่ที่เป็นไปได้ ปรับปรุงการประมาณคำตอบที่เหมาะสมที่สุดด้วยเศษส่วนที่แน่นอนในแต่ละรอบการทำซ้ำ และลู่เข้าสู่คำตอบที่เหมาะสมที่สุดด้วยข้อมูลเชิงตรรกะ^{[ 2 ]}

พิจารณาปัญหาการเขียนโปรแกรมเชิงเส้นในรูปแบบเมทริกซ์:

อัลกอริทึมของ Karmarkar กำหนดทิศทางที่เป็นไปได้ถัดไปสู่ความเหมาะสมที่สุดและปรับขนาดกลับด้วยปัจจัย0 < γ ≤ 1มีการอธิบายไว้ในแหล่งข้อมูลหลายแหล่ง^{[ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ]} Karmarkar ยังได้ขยายวิธีการ^{[ 9 ] [ 10 ] [ 11 ] [ 12 ]}เพื่อแก้ปัญหาที่มีข้อจำกัดจำนวนเต็มและปัญหาที่ไม่นูน^{[ 13 ]}

อัลกอริทึมการปรับขนาดเชิงเส้น 

อินพุต: A, b, c, , ${\displaystyle x^{0}}$เกณฑ์การหยุด , γ . 

${\displaystyle k\leftarrow 0}$ทำซ้ำในขณะที่เงื่อนไขการหยุดไม่เป็นไปตามที่กำหนดหากเป็นเช่นนั้นให้ส่งคืนค่าที่ไม่มี  ขอบเขต จบการทำซ้ำ${\displaystyle v^{k}\leftarrow b-Ax^{k}}$${\displaystyle D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots ,v_{m}^{k})}$${\displaystyle h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c}$${\displaystyle h_{v}\leftarrow -Ah_{x}}$${\displaystyle h_{v}\geq 0}$${\displaystyle \alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v})_{i}<0,\,i=1,\ldots ,m\}}$${\displaystyle x^{k+1}\leftarrow x^{k}+\alpha h_{x}}$${\displaystyle k\ลูกศรซ้าย k+1}$

พิจารณาโปรแกรมเชิงเส้น นี้ นั่นคือ มีตัวแปร 2 ตัวและข้อจำกัด 11 ข้อที่เกี่ยวข้องกับค่าต่างๆ ของรูปนี้แสดงการวนซ้ำแต่ละครั้งของอัลกอริทึมด้วยจุดวงกลมสีแดง ข้อจำกัดแสดงด้วยเส้นสีน้ำเงิน $${\displaystyle {\begin{array}{lrclr}{\text{maximize}}&x_{1}+x_{2}\\{\text{subject to}}&2px_{1}+x_{2}&\leq &p^{2}+1,&p=0.0,0.1,0.2,\ldots ,0.9,1.0.\end{array}}}$$${\displaystyle x_{1},x_{2}}$${\displaystyle p}$

ในขณะที่เขาคิดค้นอัลกอริทึมนั้น Karmarkar ทำงานให้กับIBMในตำแหน่งนักวิจัยหลังปริญญาเอกที่ห้องปฏิบัติการวิจัย IBM San Joseในแคลิฟอร์เนีย เมื่อวันที่ 11 สิงหาคม 1983 เขาได้บรรยายในสัมมนาที่มหาวิทยาลัยสแตนฟอร์ดเพื่ออธิบายอัลกอริทึม โดยยังคงระบุสังกัดของเขาเป็น IBM อยู่ ในฤดูใบไม้ร่วงปี 1983 Karmarkar เริ่มทำงานที่AT&Tและส่งบทความของเขาไปยังงานประชุมวิชาการ ACM Symposium on Theory of Computing (STOC ซึ่งจัดขึ้นระหว่างวันที่ 30 เมษายน - 2 พฤษภาคม 1984) ประจำปี 1984 โดยระบุว่าสังกัดของเขาคือAT&T Bell Laboratories ^{[ 16 ]}หลังจากนำอัลกอริทึมไปใช้ในการเพิ่มประสิทธิภาพเครือข่ายโทรศัพท์ของ AT&T ^{[ 17 ]}พวกเขาก็ตระหนักว่าสิ่งประดิษฐ์ของเขาสามารถมีความสำคัญในทางปฏิบัติได้ ในเดือนเมษายน 1985 AT&T จึงยื่นขอจดสิทธิบัตรอัลกอริทึมของเขาทันที

สิทธิบัตรดังกล่าวกลายเป็นเชื้อเพลิงเพิ่มเติมให้กับข้อโต้แย้งที่กำลังดำเนินอยู่เกี่ยวกับประเด็นสิทธิบัตรซอฟต์แวร์ [ ^{18 ] สิ่ง} นี้ทำให้บรรดานักคณิตศาสตร์หลายคนรู้สึกไม่สบายใจ เช่นโรนัลด์ ริเวสต์ (ซึ่งเป็นหนึ่งในผู้ถือสิทธิบัตรของ อัลกอริทึม RSA ) ผู้ซึ่งแสดงความคิดเห็นว่าการวิจัยดำเนินไปบนพื้นฐานที่ว่าอัลกอริทึมควรเป็นอิสระ แม้กระทั่งก่อนที่สิทธิบัตรจะได้รับการอนุมัติจริง ก็มีการโต้แย้งว่าอาจมีงานวิจัยก่อนหน้าที่สามารถนำไปใช้ได้^{[ 19 ]}นักคณิตศาสตร์ที่เชี่ยวชาญด้านการวิเคราะห์เชิงตัวเลขรวมถึงฟิลิป กิลล์และคนอื่นๆ อ้างว่าอัลกอริทึมของคาร์มาร์การ์เทียบเท่ากับวิธีการกั้นแบบนิวตันที่ฉายภาพด้วยฟังก์ชันกั้นแบบ ลอการิทึม หากเลือกพารามิเตอร์อย่างเหมาะสม^{[ 20 ]} นักวิชาการด้านกฎหมาย แอนดรูว์ ชิน แสดงความคิดเห็นว่าข้อโต้แย้งของกิลล์มีข้อบกพร่อง เนื่องจากวิธีการที่พวกเขาอธิบายนั้นไม่ถือเป็น "อัลกอริทึม" เพราะต้องมีการเลือกพารามิเตอร์ที่ไม่เป็นไปตามตรรกะภายในของวิธีการ แต่ต้องอาศัยคำแนะนำจากภายนอก โดยพื้นฐานแล้วมาจากอัลกอริทึมของคาร์มาร์การ์^{[ 21 ]}ยิ่งไปกว่านั้น ผลงานของ Karmarkar ถือว่าไม่ชัดเจนนักเมื่อพิจารณาจากผลงานก่อนหน้าทั้งหมด รวมถึง Fiacco-McCormick, Gill และคนอื่นๆ ที่ Saltzman อ้างถึง^{[ 21 ] [ 22 ] [ 23 ]} สิทธิบัตรนี้ได้รับการอนุมัติเพื่อเป็นการยอมรับถึงความริเริ่มสร้างสรรค์ที่สำคัญของผลงานของ Karmarkar โดยเป็นสิทธิบัตรของสหรัฐอเมริกาหมายเลข 4,744,028 : "วิธีการและอุปกรณ์สำหรับการจัดสรรทรัพยากรอย่างมีประสิทธิภาพ" ในเดือนพฤษภาคม พ.ศ. 2531

AT&T ออกแบบ ระบบคอมพิวเตอร์ มัลติโปรเซสเซอร์เวกเตอร์ โดยเฉพาะเพื่อใช้งานอัลกอริทึมของ Karmarkar โดยเรียกการผสมผสานระหว่างฮาร์ดแวร์และซอฟต์แวร์ที่ได้นี้ว่า KORBX ^{[ 24 ]}และวางตลาดระบบนี้ในราคา 8.9 ล้านดอลลาร์สหรัฐ^{[ 25 ] [ 26 ]}ลูกค้ารายแรกคือเพนตากอน^{[ 27 ] [ 28 ]}

ผู้คัดค้านสิทธิบัตรซอฟต์แวร์ยังโต้แย้งเพิ่มเติมว่าสิทธิบัตรดังกล่าวทำลายวงจรปฏิสัมพันธ์เชิงบวกที่เคยเป็นลักษณะเฉพาะของความสัมพันธ์ระหว่างนักวิจัยในการเขียนโปรแกรมเชิงเส้นและอุตสาหกรรม และโดยเฉพาะอย่างยิ่งทำให้คาร์มาร์การ์ถูกแยกออกจากเครือข่ายนักวิจัยทางคณิตศาสตร์ในสาขาของเขา^{[ 29 ]}

สิทธิบัตรดังกล่าวหมดอายุในเดือนเมษายน พ.ศ. 2549 และปัจจุบันอัลกอริทึมนี้เป็นสาธารณสมบัติแล้ว

ศาลฎีกาสหรัฐอเมริกาได้ตัดสินว่าคณิตศาสตร์ไม่สามารถจดสิทธิบัตรได้ในคดี^Gottschalk v. Benson [ ^{30 ]}ในคดีนั้น ศาลได้พิจารณาก่อนว่าอัลกอริทึมคอมพิวเตอร์สามารถจดสิทธิบัตรได้หรือไม่ และได้ตัดสินว่าไม่สามารถจดสิทธิบัตรได้ เนื่องจากระบบสิทธิบัตรไม่ได้คุ้มครองแนวคิดและนามธรรมที่คล้ายคลึงกัน ในคดี^Diamond v. Diehr [ ^{31 ]}ศาลฎีกาได้กล่าวว่า "สูตรทางคณิตศาสตร์นั้นไม่ได้รับการคุ้มครองตามกฎหมายสิทธิบัตรของเรา และหลักการนี้ไม่สามารถหลีกเลี่ยงได้โดยการพยายามจำกัดการใช้สูตรให้อยู่ในสภาพแวดล้อมทางเทคโนโลยีเฉพาะ^{[ 32 ]}ในคดี Mayo Collaborative Services v. Prometheus Labs., Inc. [ ^{33 ] ศาลฎีกา}ได้อธิบายเพิ่มเติมว่า "การนำหลักการทางคณิตศาสตร์ไปใช้กับเครื่องจักรทางกายภาพ เช่น คอมพิวเตอร์ ไม่ใช่การประยุกต์ใช้หลักการนั้นที่สามารถจดสิทธิบัตรได้" ^{[ 34 ]}

อัลกอริทึมของ Karmarkar ถูกใช้โดยกองทัพสหรัฐฯ สำหรับการวางแผนด้านโลจิสติกส์ในช่วง^{สงคราม}อ่าว [ ^{1 ]}