خوارزمية كارماركر
خوارزمية كارماركر هي خوارزمية قدمها ناريندرا كارماركر في عام 1984 لحل مسائل البرمجة الخطية . كانت أول خوارزمية ذات كفاءة معقولة لحل هذه المسائل في زمن متعدد الحدود . طريقة الإهليلجي هي أيضا متعددة الحدود لكنها أثبتت أنها غير فعالة عمليا.

بجعل تدل على عدد المتغيرات و  على عدد وحدات بت في مدخلات الخوارزمية، خوارزمية كارماركر تحتاج إلى عملية على خانات , في المقابل تحتاج إلى عمليات بخوارزمية الاهليجي.

بالتالي زمن تشغيل خوارزمية كارماركر هو:

 

باستخدام الضرب القائم على FFT (انظر رمز O الكبير ).

تندرج خوارزمية كارماركر ضمن فئة أساليب النقاط الداخلية : لا يتبع التخمين الحالي للحل حدود المجموعة الممكنة كما هو الحال في طريقة simplex ، لكنه يتحرك بداخل المنطقة الممكنة، مما يحسن تقريب الحل الأمثل بكسر واضح مع كل التكرار، والوصول إلى الحل الأمثل مع البيانات المنطقية.

الخوارزمية 
بالنظر في مشكلة البرمجة الخطية في شكل المصفوفة:

تحدد خوارزمية كارماركر الاتجاه التالي الممكن إلى المثالية وتوازن بمعامل .

وسع كامارك الطريقة  ، لتحل مسائل بقيود اعداد صحيحة والمسائل غير المحدبة.

 stopping criterion, .

  

 

 
   

 
   

 
   

 
   

 
   

 
     return unbounded

 
   end if

 
   

 
   

 
   

 
  end do

مثال 

بالنظر في البرنامج الخطي

 

حيث يوجد متغيرين  و 11 قيود مرتبطة باختلاف قيم  . يوضح هذا الشكل كل تكرار للخوارزمية كنقاط حمراء. وتظهر القيود كخطوط زرقاء.

جدل براءات الاختراع 
في الوقت الذي ابتكر فيه الخوارزمية، توظف كامارك بواسطة آي بي إم كزميل لما بعد الدكتوراه في مختبر أبحاث سان خوسيه في كاليفورنيا. في 11 أغسطس 1983 ، ألقى ندوة في جامعة ستانفورد لشرح الخوارزمية، وانتمائه لا يزال مدرجًا باسم آي بي إم. بحلول خريف عام 1983 ، بدأ كارماركر العمل في إيه تي آند تي وقدم مقالته إلى Symposium on Theory of Computing ACM لعام 1984 حول نظرية الحوسبة (STOC ، التي عقدت في 30 أبريل - 2 مايو 1984) موضحًا أن انتمائه لمختبرات بيل لإيه تي آند تي . بعد تطبيق الخوارزمية على تحسين شبكة هاتف إيه تي آند تي،  أدركوا أن اختراعه يمكن أن يكون ذا أهمية عملية. في أبريل 1985 ، تقدمت إيه تي آند تي بطلب للحصول على براءة اختراع على خوارزمية كارماركر.

المراجع 

 
 ناريندرا كارماركار (1984). " خوارزمية زمنية جديدة متعددة الحدود للبرمجة الخطية " ، Combinatorica ، المجلد 4 ، العدد. 4 ، ص.   373 – 395.

برمجة خطية
حساب المتغيرات
خوارزمية كارماركر هي خوارزمية قدم ها ناريندرا كارماركر في عاملحل مسائل البرمجة الخطية \ . كانت أول خوارزمية ذات كفاءة معقولة ل حل هذه المسائل في زمن متعدد الحدود\ . طريقة الإهليلجي هي أيضا متعددة الحدود لٰكن ها أثبتت أن ها غير فعالة عمليا . بجعل تدل على عدد المتغيرات و على عدد وحدات بت في مدخلات الخوارزمية ، خوارزمية كارماركر تحتاج إلى عملية على خانات , في المقابل تحتاج إلى عمليات بخوارزمية الاهليجي . ب التالي زمن تشغيل خوارزمية كارماركر هو : ب استخدام ا الضرب القائم على FFT ( انظر رمز O الكبير ) . تندرج خوارزمية كارماركر ضمن فئة أساليب النقاط الداخلية : لا يتبع التخمين الحالي ل الحل حدود المجموعة الممكنة كما هو الحال في طريقة simplex ، لٰكن ه يتحرك بداخل المنطقة الممكنة ، مما يحسن تقريب الحل الأمثل ب كسر واضح مع كل ال تكرار ، و الوصول إلى الحل الأمثل مع البيانات المنطقية . الخوارزمية ب النظر في مشكلة البرمجة الخطية في شكل المصفوفة : تحدد خوارزمية كارماركر الاتجاه التالي الممكن إلى المثالية وتوازن بمعامل \ . وسع كامارك الطريقة ، لتحل مسائل بقيود اعداد صحيحة والمسائل غير المحدبة . stopping criter io n ,\ . return unbounded end if end do مثال ب النظر في البرنامج الخطي حيث يوجد متغيرين وقيود مرتبطة ب اختلاف قيم \ . يوضح هذا الشكل كل تكرار للخوارزمية كنقاط حمراء . و تظهر القيود كخطوط زرقاء . جدل براءات الاختراع في الوقت الذي ابتكر في ه الخوارزمية ، توظف كامارك ب واسطة آي بي إم كزميل ل ما بعد الدكتورا ه في مختبر أبحاث سان خوسيه في كاليفورنيا . فيأغسطس ، ألقى ندوة في جامعة ستانفورد ل شرح الخوارزمية ، و انتماء ه لا يزال مدرجًا ب اسم آي بي إم . ب حلول خريف عام ، بدأ كارماركر العمل في إيه تي آند تي و قدم مقالة ه إلى Symposium on Theory of Computing ACM لعامحول نظرية الحوسبة ( STOC ، التي عقدت فيأبريل - مايوموضحًا أن انتماء ه لمختبرات بيل لإيه تي آند تي\ . بعد تطبيق الخوارزمية على تحسين شبكة هاتف إيه تي آند تي ، أدركوا أن اختراع ه يمكن أن يكون ذا أهمية عملية . في أبريل ، تقدمت إيه تي آند تي ب طلب ل الحصول على براءة اختراع على خوارزمية كارماركر . المراجع ناريندرا كارماركار " خوارزمية زمنية جديدة متعددة الحدود للبرمجة الخطية " ، Combinatorica ، المجلد ، العدد . ، ص . – برمجة خطية حساب المتغيرات