خوارزمية التقريب المُعَلمة

الموسوعة الحرة

خوارزمية التقريب المُعَلمة هي نوع من الخوارزميات التي تهدف إلى إيجاد حلول تقريبية لمسائل التحسين الصعبة (NP-hard) في وقت متعدد الحدود ، وذلك بالنسبة لحجم المدخلات ودالة لمعامل محدد. صُممت هذه الخوارزميات لتجمع بين أفضل جوانب خوارزميات التقريب التقليدية وسهولة التعامل مع المعاملات الثابتة.

في خوارزميات التقريب التقليدية، يتمثل الهدف في إيجاد حلول لا تبعد عن الحل الأمثل، والمعروفة بتقريب α ، إلا بمعامل α ، وذلك في زمن متعدد الحدود. من جهة أخرى، تُصمم الخوارزميات المُعَلمة لإيجاد حلول دقيقة للمسائل، مع مراعاة أن زمن تشغيل الخوارزمية متعدد الحدود بالنسبة لحجم المدخلات، وهو دالة لمعامل محدد k . يصف هذا المعامل خاصية من خصائص المدخلات، ويكون صغيرًا في التطبيقات النموذجية. يُقال إن المسألة قابلة للحل بمعامل ثابت (FPT) إذا وُجدت خوارزمية قادرة على إيجاد الحل الأمثل في زمن متعدد الحدود.و(ك)نيا(1){\displaystyle f(k)n^{O(1)}}الوقت، أينو(ك){\displaystyle f(k)}هي دالة مستقلة عن حجم المدخلات n .

تهدف خوارزمية التقريب المُعَلمة إلى إيجاد توازن بين هذين النهجين من خلال إيجاد حلول تقريبية في زمن FPT: تحسب الخوارزمية تقريبًا من النوع α فيو(ك)نيا(1){\displaystyle f(k)n^{O(1)}}الوقت، أينو(ك){\displaystyle f(k)}هي دالة مستقلة عن حجم المدخلات n . يهدف هذا النهج إلى التغلب على قيود كلا النهجين التقليديين من خلال توفير ضمانات أقوى لجودة الحل مقارنةً بالتقريبات التقليدية، مع الحفاظ على أوقات تشغيل فعالة كما في خوارزميات FPT. يمكن الاطلاع على نظرة عامة على مجال البحث الذي يدرس خوارزميات التقريب المُعَلمة في دراسة ماركس [ 1 ] والدراسة الأحدث التي أجراها فيلدمان وآخرون [ 2 ] .

نسب التقريب الممكنة

يتم استغلال الإمكانات الكاملة لخوارزميات التقريب المُعَلمة عندما يُثبت أن مسألة تحسين معينة تقبل خوارزمية تقريب من النوع α تعمل فيو(ك)نيا(1){\displaystyle f(k)n^{O(1)}}في حين أن المشكلة لا تملك خوارزمية تقريبية من النوع α ذات زمن متعدد الحدود (في ظل افتراض معين للتعقيد ، على سبيل المثال،P≠شمالP{\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}), ولا خوارزمية FPT للمعامل k المعطى (أي أنها على الأقل W[1]-صعبة ).

على سبيل المثال، تقبل بعض المسائل التي تُصنف ضمن فئة APX-hard و W[1]-hard مخطط تقريبي مُعامل (PAS) ، أي لأيε>0{\displaystyle \varepsilon >0}أ(1+ε){\displaystyle (1+\varepsilon )}يمكن حساب التقريب فيو(ك،ε)نز(ε){\displaystyle f(k,\varepsilon )n^{g(\varepsilon )}}زمن بعض الدوال f و g . وهذا يتجاوز الحدود الدنيا من حيث تقريب الزمن متعدد الحدود وسهولة المعالجة ذات المعلمات الثابتة. يشبه مخطط تقريب الزمن متعدد الحدود (PAS ) مخطط تقريب الزمن متعدد الحدود (PTAS) في جوهره ، ولكنه يستغل بالإضافة إلى ذلك معلمة معينة k . بما أن درجة متعددة الحدود في زمن تشغيل مخطط تقريب الزمن متعدد الحدود تعتمد على دالةز(ε){\displaystyle g(\varepsilon )}، قيمةε{\displaystyle \varepsilon }يُفترض أن تكون قيمة عشوائية ولكنها ثابتة لكي يعمل نظام PAS في زمن FPT. إذا كان هذا الافتراض غير مُرضٍ،ε{\displaystyle \varepsilon }يتم التعامل معها كمعامل أيضًا للحصول على مخطط تقريبي فعال ذي معلمات (EPAS) ، والذي لأيε>0{\displaystyle \varepsilon >0}يحسب أ(1+ε){\displaystyle (1+\varepsilon )}التقريب فيو(ك،ε)نيا(1){\displaystyle f(k,\varepsilon )n^{O(1)}}الوقت لبعض الدوال f . وهذا يشبه في جوهره مخطط تقريبي فعال متعدد الحدود (EPTAS).

قطع k

لا توجد مسألة قطع من الرتبة k ذات وقت متعدد الحدود(2-ε){\displaystyle (2-\varepsilon )}خوارزمية تقريبية لأيε>0{\displaystyle \varepsilon >0}، بافتراضP≠شمالP{\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}وفرضية توسيع المجموعة الصغيرة . [ 3 ] وهي أيضًا مسألة صعبة من نوع W[1]، وتُحدد بمعامل عدد المكونات المطلوبة k . [ 4 ] ومع ذلك، يوجد نظام EPAS، الذي يحسب(1+ε){\displaystyle (1+\varepsilon )}التقريب في(ك/ε)يا(ك)نيا(1){\displaystyle (k/\varepsilon )^{O(k)}n^{O(1)}}الوقت. [ 5 ]

بائع متجول

تُعدّ مسألة البائع المتجول من المسائل الصعبة من فئة APX-hard ، ومن المسائل الصعبة من فئة paraNP-hard عند تحديدها بمعامل البُعد المضاعف (كما هو الحال في المسائل الصعبة من فئة NP-hard في المستوى الإقليدي ). ومع ذلك، توجد مسألة EPAS عند تحديدها بمعامل البُعد المضاعف ، وحتى عند تحديدها بمعامل بُعد الطريق السريع الأكثر عمومية . [ 6 ]

شجرة شتاينر

تُعدّ مسألة شجرة شتاينر مسألةً ذات وقت استجابة محدود (FPT) مُعَلمة بعدد المحطات الطرفية. [ 7 ] مع ذلك، بالنسبة للمعامل "الثنائي" الذي يتكون من عدد k من المحطات غير الطرفية الموجودة في الحل الأمثل، تُصنَّف المسألة على أنها W[2]-صعبة (بسبب اختزالها الشائع من مسألة المجموعة المهيمنة ). ومن المعروف أيضًا أن مسألة شجرة شتاينر هي مسألة APX-صعبة . [ 8 ] ومع ذلك، توجد مسألة EPAS لحساب(1+ε){\displaystyle (1+\varepsilon )}التقريب في2يا(ك2/ε4)نيا(1){\displaystyle 2^{O(k^{2}/\varepsilon ^{4})}n^{O(1)}}الوقت. [ 9 ] تُعدّ مسألة غابة شتاينر الأكثر عمومية مسألة صعبة من نوع NP على الرسوم البيانية ذات عرض الشجرة 3. ومع ذلك، على الرسوم البيانية ذات عرض الشجرة t، يمكن لـ EPAS حساب a(1+ε){\displaystyle (1+\varepsilon )}التقريب في2يا(ت2εسجل⁡تε)نيا(1){\displaystyle 2^{O({\frac {t^{2}}{\varepsilon }}\log {\frac {t}{\varepsilon }})}n^{O(1)}}الوقت. [ 10 ]

الرسم البياني الفرعي شتاينر ذو الاتصال القوي

من المعروف أن مسألة الرسم البياني الفرعي شتاينر المتصل بقوة هي مسألة صعبة من النوع W[1]، ويتم تحديدها بواسطة عدد k من المحطات الطرفية، [ 11 ] كما أنها لا تقبليا(سجل2-ε⁡ن){\displaystyle O(\log ^{2-\varepsilon }n)}تقريب من الدرجة الثانية في وقت متعدد الحدود (في ظل افتراضات التعقيد القياسية ). [ 12 ] ومع ذلك، يمكن حساب تقريب من الدرجة الثانية في3كنيا(1){\displaystyle 3^{k}n^{O(1)}}[ 13 ] علاوة على ذلك ، هذا هو الأفضل، حيث لا يوجد(2-ε){\displaystyle (2-\varepsilon )}يمكن حساب التقريب فيو(ك)نيا(1){\displaystyle f(k)n^{O(1)}}الوقت لأي دالة f ، في ظل Gap- ETH . [ 14 ]

الوسيط k والمتوسط ​​k

بالنسبة لمسائل التجميع المتري المدروسة جيدًا، مثل k -median و k -means، والمُعَلمة بعدد المراكز k ، فمن المعروف أنه لا(1+2/هـ-ε){\displaystyle (1+2/e-\varepsilon )}-تقريب لـ k-الوسيط ولا(1+8/هـ-ε){\displaystyle (1+8/e-\varepsilon )}يمكن حساب التقريب لخوارزمية k-Means فيو(ك)نيا(1){\displaystyle f(k)n^{O(1)}}الوقت لأي دالة f ، في ظل Gap- ETH . [ 15 ] توجد خوارزميات تقريبية مُعاملة مُطابقة، [ 15 ] ولكن من غير المعروف ما إذا كان من الممكن حساب التقريبات المُطابقة في وقت متعدد الحدود.

غالبًا ما يُؤخذ التجميع في الاعتبار عند التعامل مع البيانات منخفضة الأبعاد، ولذا فإنّ التحديد الأمثل للمعاملات عمليًا يعتمد على بُعد المقياس الأساسي . في الفضاء الإقليدي ، تقبل مسألتا k-Median و k-Means نموذج EPAS مُحددًا بالبعد d ، [ 16 ] [ 17 ] وكذلك نموذج EPAS مُحددًا بالبعد k . [ 18 ] [ 19 ] وقد عُمم النموذج الأول ليصبح نموذج EPAS عند تحديده بمضاعفة البُعد . [ 20 ] أما بالنسبة لمعامل بُعد الطريق السريع ذي الصلة غير المباشرة ، فلا يُعرف حتى الآن سوى مخطط تقريبي بزمن تشغيل XP . [ 21 ]

مركز ك

بالنسبة لمسألة المركز k المتري ، يمكن حساب تقريب من الدرجة الثانية في وقت متعدد الحدود. ومع ذلك، عند تحديد المعلمات إما بعدد المراكز k ، [ 22 ] أو بُعد المضاعفة (في الواقع بُعد المقياس المانهاتني )، [ 23 ] أو بُعد الطريق السريع ، [ 22 ] لا توجد معلمات قابلة للتحديد(2-ε){\displaystyle (2-\varepsilon )}توجد خوارزمية تقريبية، في ظل افتراضات التعقيد القياسية . علاوة على ذلك، تُعدّ مسألة k-Center صعبة من الدرجة W[1] حتى على الرسوم البيانية المستوية عند تحديدها في آنٍ واحد بعدد المراكز k ، وبُعد المضاعفة ، وبُعد الطريق السريع ، وعرض المسار . [ 24 ] ومع ذلك، عند دمج k مع بُعد المضاعفة، يوجد حل تقريبي مكافئ (EPAS)، [ 24 ] وينطبق الأمر نفسه عند دمج k مع بُعد الطريق السريع . [ 25 ] بالنسبة للنسخة الأكثر عمومية ذات سعات الرؤوس، يوجد حل تقريبي مكافئ (EPAS) عند تحديدها باستخدام k وبُعد المضاعفة، ولكن ليس عند استخدام k وبُعد الطريق السريع كمعامل. [ 26 ] فيما يتعلق بعرض المسار، تقبل مسألة k-Center حلاً تقريبيًا مكافئًا (EPAS) حتى مع معامل عرض الشجرة الأكثر عمومية ، وكذلك مع عرض الزمرة . [ 27 ]

الرسم البياني الفرعي الأكثر كثافة

يُعدّ مسألة إيجاد الرسم البياني الفرعي الأكثر كثافة من النوع k (وهي مسألة إرضاء قيود ثنائية ) أحد أشكال التحسين لمسألة k -Clique ، حيث تتمثل المهمة في إيجاد رسم بياني فرعي على k رأسًا بأكبر عدد ممكن من الحواف. ليس من الصعب الحصول على(ك-1){\displaystyle (k-1)}-تقريب عن طريق اختيار حجم مطابقك/2{\displaystyle k/2}في الرسم البياني المدخل المعطى، بما أن الحد الأقصى لعدد الحواف على k رأس يكون دائمًا على الأكثر(ك2)=ك(ك-1)/2{\displaystyle {k \choose 2}=k(k-1)/2}وهذا أيضًا هو الأمثل تقاربًا ، لأنه في ظل Gap- ETH لاك1-o(1){\displaystyle k^{1-o(1)}}يمكن حساب التقريب في وقت FPT المحدد بواسطة k . [ 28 ]

مجموعة مهيمنة

بالنسبة لمسألة مجموعة الهيمنة، فإن حساب أيز(ك){\displaystyle g(k)}التقريب فيو(ك)نيا(1){\displaystyle f(k)n^{O(1)}}الوقت لأي دالتين g و f . [ 29 ]

التقريب إلى النواة

تُعدّ عملية التمركز تقنية تُستخدم في قابلية معالجة المسائل ذات المعاملات الثابتة لمعالجة حالة من مسائل NP-hard مسبقًا ، وذلك لإزالة "الأجزاء السهلة" وكشف جوهر المسألة NP-hard. تأخذ خوارزمية التمركز حالة I ومعامل k ، وتُعيد حالة جديدة.أنا′{\displaystyle I'}مع المعلمةك′{\displaystyle k'}بحيث يكون حجمأنا′{\displaystyle I'}وك′{\displaystyle k'}تكون محدودة كدالة لمعامل الإدخال k ، ويعمل الخوارزمية في وقت متعدد الحدود. خوارزمية النواة التقريبية α هي شكل من أشكال هذه التقنية المستخدمة في خوارزميات التقريب المُعَلمة. تُعيد هذه الخوارزمية نواة.أنا′{\displaystyle I'}بحيث يكون أي تقريب β فيأنا′{\displaystyle I'}يمكن تحويلها إلى تقريب من الدرجة α β للحالة المدخلة I في وقت متعدد الحدود. وقد طُرح هذا المفهوم من قِبل لوكشتانوف وآخرون [ 30 ]، ولكن توجد مفاهيم أخرى ذات صلة في الأدبيات مثل نواة تورينج [ 31 ] وتقنية النواة ذات الدقة α [ 32 ] .

بالنسبة للنوى العادية (غير التقريبية)، تقبل المسألة خوارزمية تقريبية من الدرجة α إذا وفقط إذا كان لها خوارزمية تقريبية من الدرجة α ذات معلمات. ويشابه برهان هذه الحقيقة إلى حد كبير برهان النوى العادية . [ 30 ] مع ذلك، قد تكون النواة التقريبية المضمونة ذات حجم أُسّي (أو أسوأ) بالنسبة لمعلمة الإدخال. لذا، يصبح من المهم إيجاد مسائل تقبل نوى تقريبية ذات حجم متعدد الحدود. علاوة على ذلك، فإن مخطط التقريب ذي الحجم متعدد الحدود (PSAKS) هو خوارزمية تقريبية من الدرجة α تحسب نواة ذات حجم متعدد الحدود، ويمكن ضبط قيمة α فيها على1+ε{\displaystyle 1+\varepsilon }لأيε>0{\displaystyle \varepsilon >0}.

على سبيل المثال، في حين أن مسألة تغطية الرؤوس المتصلة هي مسألة ذات وقت حل سريع (FPT) يتم تحديدها بواسطة حجم الحل، إلا أنها لا تقبل نواة بحجم متعدد الحدود (منتظم) (إلا إذاNP⊆coNP/poly{\displaystyle {\textsf {NP}}\subseteq {\textsf {coNP/poly}}})، ولكن يوجد PSAKS. [ 30 ] وبالمثل، فإن مسألة شجرة شتاينر هي مسألة FPT مُعَلمة بعدد المحطات الطرفية، ولا تقبل نواة بحجم متعدد الحدود (إلا إذاNP⊆coNP/poly{\displaystyle {\textsf {NP}}\subseteq {\textsf {coNP/poly}}})، ولكن يوجد حل PSAKS. [ 30 ] عند تحديد معلمات شجرة شتاينر بعدد الرموز غير الطرفية في الحل الأمثل، تصبح المسألة صعبة من الدرجة W[2] (وبالتالي لا تقبل نواة دقيقة على الإطلاق، إلا إذا كانت FPT=W[2])، ولكنها لا تزال تقبل حل PSAKS. [ 9 ]

محادثات حول التقريبات البارامترية

مراجع

  1. ↑ ماركس، دانيال (2008). "التعقيد المُعَلم وخوارزميات التقريب" . مجلة الحاسوب . 51 (1): 60-78 . doi : 10.1093/comjnl/bxm048 .
  2. ↑ فيلدمان، أندرياس إميل؛ كارثيك سي. إس؛ لي، إيوونغ؛ مانورانغسي، باسين (2020). "دراسة استقصائية حول التقريب في التعقيد المُعَلم: الصعوبة والخوارزميات" . الخوارزميات . 13 (6): 146. arXiv : 2006.04411 . doi : 10.3390/a13060146 . ISSN 1999-4893 .  تتضمن هذه المقالة نصًا من هذا المصدر، وهو متاح بموجب ترخيص CC BY 4.0 .
  3. ↑ مانورانغسي، باسين (2018). "عدم إمكانية تقريب مسائل المجموعة الثنائية القصوى، والقطع الأدنى من الرتبة k، والرسم البياني الفرعي الأكثر كثافة من الرتبة k على الأقل من فرضية توسيع المجموعة الصغيرة" . الخوارزميات . 11 (1): 10. arXiv : 1705.03581 . doi : 10.3390/a11010010 . ISSN 1999-4893 . 
  4. ↑ جي. داوني، رودني؛ إستيفيل-كاسترو، فلاديمير؛ فيلوز، مايكل؛ برييتو، إيلينا ؛ روزاموند، فرانسيس أ. (1 أبريل 2003). "التقطيع صعب: التعقيد البارامتري لمسألة القطع من الرتبة k والمسائل ذات الصلة" . ملاحظات إلكترونية في علوم الحاسوب النظرية . CATS'03، الحوسبة: ندوة النظرية الأسترالية. 78 : 209-222 . doi : 10.1016/S1571-0661(04)81014-4 . hdl : 10230/36518 . ISSN 1571-0661 . 
  5. ↑ لوكشتانوف، دانيال؛ سوراب، ساكيت؛ سوريانارايانان، فايشالي (25 أبريل 2022). "مخطط تقريبي مُعَلم لـ Min k-Cut" . مجلة SIAM للحوسبة : FOCS20–205. arXiv : 2005.00134 . doi : 10.1137/20M1383197 . ISSN 0097-5397 . 
  6. ↑ إميل فيلدمان، أندرياس؛ فيلتسر، أرنولد (يناير 2025)، "بعد الطريق السريع: منظور متري" ، وقائع ندوة ACM-SIAM السنوية لعام 2025 حول الخوارزميات المنفصلة (SODA) ، وقائع جمعية الرياضيات الصناعية والتطبيقية، الصفحات 3267-3276 ، doi : 10.1137/1.9781611978322.104 ، تاريخ الاسترجاع 2025-06-02 
  7. ↑ دريفوس، إس إي؛ فاغنر، آر إيه (1971). "مشكلة شتاينر في الرسوم البيانية" . الشبكات . 1 (3): 195-207 . doi : 10.1002/net.3230010302 .
  8. ^ شلبيك، ميروسلاف؛ تشليبيكوفا ، يانكا (31 أكتوبر 2008). "مشكلة شجرة شتاينر على الرسوم البيانية: نتائج عدم التقريب" . علوم الكمبيوتر النظرية . الجوانب الخوارزمية للحوسبة العالمية. 406 (3): 207-214 . دوى : 10.1016/j.tcs.2008.06.046 . ISSN 0304-3975 . 
  9. 1 2 دفورجاك، بافيل؛ فيلدمان، أندرياس E.؛ نوب، دوشان؛ ماساريك، توماس؛ توفار، توماس؛ فيسيلي ، بافيل (1 يناير 2021). "مخططات التقريب ذات المعلمات لأشجار شتاينر ذات عدد صغير من رؤوس شتاينر" . مجلة SIAM للرياضيات المنفصلة . 35 (1): 546–574 . أرخايف : 1710.00668 . دوى : 10.1137/18M1209489 . ISSN 0895-4801 . S2CID 3581913 .  
  10. ^ فيلدمان، أندرياس إميل؛ لامبيس، مايكل (2024). “خوارزميات ذات معلمات لغابة شتاينر في الرسوم البيانية ذات العرض المحدود”. في برينجمان، كارل؛ جروهي، مارتن؛ بوبيس، غابرييل؛ سفينسون، علا (محرران). الندوة الدولية الحادية والخمسون حول الأتمتة واللغات والبرمجة، ICALP 2024، 8-12 يوليو 2024، تالين، إستونيا . LIPics. المجلد. 297. شلوس داغستوهل – مركز لايبنتز للمعلوماتية. ص 61: 1-61:20. أرخايف : 2402.09835 . دوى : 10.4230/LIPICS.ICALP.2024.61 .  
  11. ↑ غو، جيونغ؛ نيدرماير، رولف؛ سوتشي، أوندريج (1 يناير 2011). "التعقيد البارامتري لمسائل شتاينر الموجهة الموزونة بالأقواس" . مجلة SIAM للرياضيات المتقطعة . 25 (2): 583-599 . doi : 10.1137/100794560 . ISSN 0895-4801 . 
  12. ↑ هالبرين، إران؛ كراوثغامر، روبرت (9 يونيو 2003). "عدم إمكانية التقريب متعدد اللوغاريتمات" . وقائع الندوة السنوية الخامسة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة . STOC '03. نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 585-594 . doi : 10.1145/780542.780628 . ISBN  978-1-58113-674-6. S2CID 8554166 . 
  13. ↑ شيتنيس، راجيش؛ حاجي آغاي، محمد تقي؛ كورتسارز، غاي (2013). "خوارزميات المعاملات الثابتة والتقريبية: نظرة جديدة". في: غوتين، غريغوري؛ سزيدر، ستيفان (محرران). الحساب المُعامل والحساب الدقيق . سلسلة محاضرات في علوم الحاسوب. المجلد 8246. تشام: دار نشر سبرينغر الدولية. الصفحات 110-122 . arXiv : 1308.3520 . doi : 10.1007/978-3-319-03898-8_11 . ISBN   978-3-319-03898-8. S2CID 6796132 . 
  14. ↑ تشيتنيس، راجيش؛ فيلدمان، أندرياس إميل؛ مانورانجسي، باسين (19 أبريل 2021). "خوارزميات التقريب المُعَلمة لمسائل شبكة شتاينر ثنائية الاتجاه" . معاملات ACM في الخوارزميات . 17 (2): 12:1–12:68. arXiv : 1707.06499 . doi : 10.1145/3447584 . ISSN 1549-6325 . S2CID 235372580 .  
  15. 1 2 كوهين-أداد، فنسنت؛ غوبتا، أنوبام؛ كومار، أميت؛ لي، إيوونغ؛ لي، جيسون (2019). باير، كريستيل؛ تشاتزيجياناكيس، يوانيس؛ فلوتشيني، باولا؛ ليوناردي، ستيفانو (محررون). "تقريبات دقيقة لوقت الفاصل الزمني الخاطئ لخوارزميتي k-Median و k-Means" . المؤتمر الدولي السادس والأربعون حول الأوتوماتا واللغات والبرمجة (ICALP 2019) . وقائع لايبنيز الدولية في المعلوماتية (LIPIcs). 132. داغشتول، ألمانيا: قصر داغشتول - مركز لايبنيز للمعلوماتية: 42:1–42:14. doi : 10.4230/LIPIcs.ICALP.2019.42 . ISBN 978-3-95977-109-2. S2CID 139103417 . 
  16. ↑ كوليوبولوس، ستافروس ج.؛ راو، ساتيش (1999). "مخطط تقريبي شبه خطي لمسألة الوسيط k الإقليدي". في: نيشيتريل، ياروسلاف (محرر). الخوارزميات - ESA' 99. سلسلة محاضرات في علوم الحاسوب. المجلد 1643. برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ. الصفحات 378-389 . doi : 10.1007/3-540-48481-7_33 . ISBN   978-3-540-66251-8.
  17. ↑ كوهين-أداد، فنسنت (2018). "مخطط تقريب سريع لخوارزمية k-Means منخفضة الأبعاد". وقائع ندوة ACM-SIAM السنوية لعام 2018 حول الخوارزميات المنفصلة (SODA) . وقائع الجمعية الصناعية والتطبيقية للرياضيات. الصفحات 430-440 . arXiv : 1708.07381 . doi : 10.1137/1.9781611975031.29 . ISBN  978-1-61197-503-1. S2CID 30474859 . 
  18. ↑ فيلدمان، دان؛ مونيمي زاده، مرتضى؛ سولر، كريستيان (6 يونيو 2007). "خوارزمية تقريبية متعددة الحدود لتجميع البيانات باستخدام خوارزمية k-means بناءً على مجموعات أساسية ضعيفة" . وقائع الندوة السنوية الثالثة والعشرين حول الهندسة الحسابية - SCG '07 . نيويورك، نيويورك، الولايات المتحدة الأمريكية: رابطة آلات الحوسبة. الصفحات 11-18 . doi : 10.1145/1247069.1247072 . ISBN  978-1-59593-705-6. S2CID 5694112 . 
  19. ↑ فيلدمان، دان؛ لانغبيرغ، مايكل (6 يونيو 2011). "إطار عمل موحد لتقريب البيانات وتجميعها" . وقائع الندوة السنوية الثالثة والأربعين لجمعية آلات الحوسبة حول نظرية الحوسبة . STOC '11. نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 569-578 . doi : 10.1145/1993636.1993712 . ISBN  978-1-4503-0691-1. S2CID 2677556 . 
  20. ↑ كوهين-أداد، فنسنت؛ فيلدمان، أندرياس إميل؛ سولبيك، ديفيد (31 أكتوبر 2021). "مخططات تقريب زمني شبه خطي للتجميع في مقاييس مضاعفة" . مجلة ACM . 68 (6): 44:1–44:34. arXiv : 1812.08664 . doi : 10.1145/3477541 . ISSN 0004-5411 . S2CID 240476191 .  
  21. ↑ فيلدمان، أندرياس إميل؛ سولبيك، ديفيد (1 ديسمبر 2021). "مخططات تقريبية متعددة الحدود للتجميع في رسوم بيانية منخفضة الأبعاد" . مجلة علوم الحاسوب والنظم . 122 : 72-93 . doi : 10.1016/j.jcss.2021.06.002 . ISSN 0022-0000 . 
  22. 1 2 فيلدمان، أندرياس إميل (1 مارس 2019). "تقريبات ذات معلمات ثابتة لمسائل k-Center في رسوم بيانية منخفضة الأبعاد" . Algorithmica . 81 ( 3): 1031–1052 . arXiv : 1605.02530 . doi : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 . S2CID 46886829 .  
  23. ↑ فيدر، توماس؛ غرين، دانيال (1 يناير 1988). "الخوارزميات المثلى للتجميع التقريبي" . وقائع الندوة السنوية العشرون لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '88 . نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 434-444 . doi : 10.1145/62212.62255 . ISBN  978-0-89791-264-8. S2CID 658151 . 
  24. 1 2 فيلدمان، أندرياس إميل؛ ماركس، دانيال (1 يوليو 2020). "صعوبة مسألة المركز k في شبكات النقل باستخدام المعاملات" . Algorithmica . 82 (7): 1989-2005 . arXiv : 1802.08563 . doi : 10.1007/s00453-020-00683-w . ISSN 1432-0541 . S2CID 3532236 .  
  25. ↑ بيكر، أماريا؛ كلاين، فيليب ن.؛ سولبيك، ديفيد (2018). عازار، يوسي؛ باست، هانا؛ هيرمان، غريغورز (محررون). "مخططات تقريبية متعددة الحدود لتوجيه المركبات من نوع k-center و k-median والسعة المحدودة في بُعد الطريق السريع المحدود" . الندوة الأوروبية السنوية السادسة والعشرون حول الخوارزميات (ESA 2018) . وقائع لايبنيز الدولية في المعلوماتية (LIPIcs). 112. داغشتول، ألمانيا: قصر داغشتول - مركز لايبنيز للمعلوماتية: 8:1–8:15. doi : 10.4230/LIPIcs.ESA.2018.8 . ISBN 978-3-95977-081-1.
  26. ↑ فيلدمان، أندرياس إميل؛ فو، تونغ آنه (2022). "مركز k المعمم : التمييز بين المضاعفة وبُعد الطريق السريع". في بيكوس، مايكل أ.؛ كوفمان، مايكل (محرران). مفاهيم نظرية الرسم البياني في علوم الحاسوب . سلسلة محاضرات في علوم الحاسوب. المجلد 13453. تشام: دار نشر سبرينغر الدولية. الصفحات 215-229 . arXiv : 2209.00675 . doi : 10.1007/978-3-031-15914-5_16 . ISBN   978-3-031-15914-5.
  27. ↑ كاتسيكارلس، يوانيس؛ لامبيس، مايكل؛ باشوس، فانجيليس ث. (15 يوليو 2019). "المعلمات الهيكلية، والحدود الدقيقة، والتقريب لمركز (k,r)" . الرياضيات التطبيقية المنفصلة . التحسين التوافقي: بين الممارسة والنظرية. 264 : 90-117 . arXiv : 1704.08868 . doi : 10.1016/j.dam.2018.11.002 . ISSN 0166-218X . 
  28. ↑ دينور، إيريت؛ مانورانجسي، باسين (2018). كارلين، آنا ر. (محررة). "صعوبة ETH لتقريب مسائل إرضاء القيود من الرتبة 2 وشبكة شتاينر الموجهة" . المؤتمر التاسع للابتكارات في علوم الحاسوب النظرية (ITCS 2018) . وقائع لايبنيز الدولية في المعلوماتية (LIPIcs). 94. داغشتول، ألمانيا: قصر داغشتول - مركز لايبنيز للمعلوماتية: 36:1–36:20. doi : 10.4230/LIPIcs.ITCS.2018.36 . ISBN 978-3-95977-060-6. S2CID 4681120 . 
  29. ↑ S., Karthik C.; Laekhanukit, Bundit; Manurangsi, Pasin (20 يونيو 2018). "حول التعقيد البارامتري لتقريب المجموعة المهيمنة" . وقائع الندوة السنوية الخمسين لجمعية ACM SIGACT حول نظرية الحوسبة . STOC 2018. نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 1283-1296 . arXiv : 1711.11029 . doi : 10.1145/3188745.3188896 . ISBN  978-1-4503-5559-9. S2CID 3170316 . 
  30. 1 2 3 4 لوكشتانوف، دانيال؛ بانولان، فهد؛ رامانوجان، إم إس؛ سوراب، ساكيت (19 يونيو 2017). "التحويل إلى نواة مع فقدان البيانات" . وقائع الندوة السنوية التاسعة والأربعين لجمعية ACM SIGACT حول نظرية الحوسبة (ملف PDF) . STOC 2017. نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 224-237 . doi : 10.1145/3055399.3055456 . ISBN  978-1-4503-4528-6. S2CID 14599219 . 
  31. ^ هيرميلين ، داني. كراتش، ستيفان؛ سولتيس، كارولينا؛ والستروم، ماغنوس. وو شي (1 مارس 2015). "نظرية الاكتمال لتنويع متعدد الحدود (تورينج)" . خوارزمية . 71 (3): 702-730 . دوى : 10.1007 / s00453-014-9910-8 . ردمك 1432-0541 . S2CID 253973283 .  
  32. ↑ فيلوز، مايكل ر.؛ كوليك، أرييل؛ روزاموند، فرانسيس؛ شاشناي، هاداس (1 مايو 2018). "التقريب المُعَلم عبر التحويلات الحافظة للدقة" . مجلة علوم الحاسوب والنظم . 93 : 30-40 . doi : 10.1016/j.jcss.2017.11.001 . ISSN 0022-0000 .