مركز القياس k

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 57 صور
الموسوعة الحرة

في نظرية المخططات ، تُعدّ مسألة المركز k المتري ، أو مسألة مركز الرأس k، مسألةً كلاسيكيةً في التحسين التوافقي، وهي مسألة صعبة الحل (NP-hard) تُدرس في علوم الحاسوب النظرية . بافتراض وجود n مدينة بمسافات محددة، يُراد بناء k مستودعًا في مدن مختلفة، مع تقليل أقصى مسافة بين كل مدينة ومستودع. في نظرية المخططات ، يعني هذا إيجاد مجموعة من k رأسًا بحيث تكون أكبر مسافة بين أي نقطة وأقرب رأس لها في المجموعة k هي الأدنى. يجب أن تكون هذه الرؤوس في فضاء متري ، مما يُشكّل مخططًا بيانيًا كاملًا يُحقق متباينة المثلث . تُستخدم هذه المسألة في تحديد مواقع المرافق وتجميعها . [ 1 ] [ 2 ]

التعريف الرسمي

تم طرح هذه المشكلة لأول مرة من قبل حكيمي في عام 1964. [ 3 ]

يترك(X،د){\displaystyle (X,d)}ليكن فضاء متري حيثX{\displaystyle X}هي مجموعة ود{\displaystyle d}هو مقياس مجموعةV⊆X{\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}يتم توفيرها مع معلمةك{\displaystyle k}الهدف هو إيجاد مجموعة جزئيةج⊆V{\displaystyle {\mathcal {C}}\subseteq \mathbf {V} }مع|ج|=ك{\displaystyle |{\mathcal {C}}|=k}بحيث تكون أقصى مسافة لنقطة فيV{\displaystyle \mathbf {V} }إلى أقرب نقطة فيج{\displaystyle {\mathcal {C}}}يتم تقليلها. يمكن تعريف المشكلة رسميًا على النحو التالي: بالنسبة لفضاء متري (X{\displaystyle {\mathcal {X}}}د)،

  • المدخلات : مجموعةV⊆X{\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}ومعاملك{\displaystyle k}.
  • الناتج : مجموعةج⊆V{\displaystyle {\mathcal {C}}\subseteq \mathbf {V} }لك{\displaystyle k}نقاط.
  • الهدف : تقليل التكلفةرج(V)=الأعلىv∈V{\displaystyle r^{\mathcal {C}}(\mathbf {V} )={\underset {v\in V}{\max }}}د(v،ج{\displaystyle {\mathcal {C}}})

أي أن كل نقطة في مجموعة تقع على مسافة لا تتجاوزرج(V){\displaystyle r^{\mathcal {C}}(V)}من مركزها المعني. [ 4 ]

يمكن تعريف مسألة التجميع k-Center على رسم بياني كامل غير موجه G =  (  V , E ) على النحو التالي: بالنظر إلى رسم بياني كامل غير موجه G = ( V , E ) بمسافات d ( vi , vj ) ∈ N تحقق متباينة المثلث، أوجد مجموعة جزئية C ⊆ V بحيث | C | = k مع تقليل:           

الأعلىv∈Vمينج∈جد(v،ج){\displaystyle \max _{v\in V}\min _{c\in C}d(v,c)}

التعقيد الحسابي

في الرسم البياني الكامل غير الموجه G  =  ( V , E )، إذا رتبنا الحواف ترتيبًا تصاعديًا للمسافات: d ( e1 ) ≤ d ( e2 ) ≤ ... ≤ d ( em ) ، ولتكن Gi = (V, Ei ) ، حيث Ei = { e1 , e2 , ... , ei } . فإن مسألة المركز k تُكافئ إيجاد أصغر فهرس i بحيث يكون لـ Gi مجموعة مهيمنة بحجم لا يتجاوز k . [ 5 ]               

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

التقريبات

خوارزمية جشعة بسيطة

خوارزمية تقريبية جشعة بسيطة تحقق عامل تقريب قدره 2ج{\displaystyle {\mathcal {C}}}باستخدام خوارزمية البحث من الأبعد أولاً في k تكرار. ببساطة، تختار هذه الخوارزمية النقطة الأبعد عن مجموعة المراكز الحالية في كل تكرار لتكون المركز الجديد. ويمكن وصفها كما يلي:

  • اختر نقطة عشوائيةج¯1{\displaystyle {\bar {c}}_{1}}داخلج1{\displaystyle C_{1}}
  • لكل نقطةv∈V{\displaystyle v\in \mathbf {V} }حسابد1[v]{\displaystyle d_{1}[v]}منج¯1{\displaystyle {\bar {c}}_{1}}
  • اختر النقطةج¯2{\displaystyle {\bar {c}}_{2}}مع أطول مسافة منج¯1{\displaystyle {\bar {c}}_{1}}.
  • أضفها إلى مجموعة المراكز، وارمز إلى هذه المجموعة الموسعة من المراكز بـج2{\displaystyle C_{2}}استمر في ذلك حتى يتم العثور على k مركزًا

مدة التشغيل

  • تستغرق عملية اختيار المركز رقم i التكرار رقم iيا(ن){\displaystyle {\mathcal {O}}(n)}وقت.
  • يوجد عدد k من هذه التكرارات.
  • وبالتالي، تأخذ الخوارزمية بشكل عاميا(نك){\displaystyle {\mathcal {O}}(nk)}الوقت. [ 6 ]

إثبات عامل التقريب

الحل الذي تم الحصول عليه باستخدام خوارزمية الجشع البسيطة هو تقريب بمقدار 2 للحل الأمثل. يركز هذا القسم على إثبات عامل التقريب هذا.

بفرض مجموعة من النقاط nV⊆X{\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}، التي تنتمي إلى فضاء متري (X{\displaystyle {\mathcal {X}}}، د)، تقوم خوارزمية K -center الجشعة بحساب مجموعة K من k مركز، بحيث تكون K تقريبًا 2 للتجميع الأمثل k -center لـ V.

أيرك(V)≤2رoصت(V،ك){\displaystyle r^{\mathbf {K} }(\mathbf {V} )\leq 2r^{opt}(\mathbf {V} ,{\textit {k}})}[ 4 ]

يمكن إثبات هذه النظرية باستخدام حالتين كما يلي:

الحالة 1: كل مجموعة منجoصت{\displaystyle {\mathcal {C}}_{opt}}يحتوي على نقطة واحدة بالضبط منك{\displaystyle \mathbf {K} }

  • لنفترض نقطةv∈V{\displaystyle v\in \mathbf {V} }
  • يتركج¯{\displaystyle {\bar {c}}}كن المركز الذي ينتمي إليهجoصت{\displaystyle {\mathcal {C}}_{opt}}
  • يتركك¯{\displaystyle {\bar {k}}}كن مركزًا لـك{\displaystyle \mathbf {K} }هذا فيΠ(جoصت،ج¯){\displaystyle \Pi ({\mathcal {C}}_{opt},{\bar {c}})}
  • د(v،ج¯)=د(v،جoصت)≤رoصت(V،ك){\displaystyle d(v,{\bar {c}})=d(v,{\mathcal {C}}_{opt})\leq r^{opt}(\mathbf {V} ,k)}
  • بصورة مماثلة،د(ك¯،ج¯)=د(ك¯،جoصت)≤رoصت{\displaystyle d({\bar {k}},{\bar {c}})=d({\bar {k}},{\mathcal {C}}_{opt})\leq r^{opt}}
  • بحسب متباينة المثلث:د(v،ك¯)≤د(v،ج¯)+د(ج¯،ك¯)≤2رoصت{\displaystyle d(v,{\bar {k}})\leq d(v,{\bar {c}})+d({\bar {c}},{\bar {k}})\leq 2r^{opt}}

الحالة الثانية: يوجد مركزانك¯{\displaystyle {\bar {k}}}وu¯{\displaystyle {\bar {u}}}لك{\displaystyle \mathbf {K} }كلاهما فيΠ(جoصت،ج¯){\displaystyle \Pi ({\mathcal {C}}_{opt},{\bar {c}})}بالنسبة للبعضج¯∈جoصت{\displaystyle {\bar {c}}\in {\mathcal {C}}_{opt}}(بحسب مبدأ تصنيف الأشياء حسب نوعها، فهذا هو الاحتمال الآخر الوحيد)

  • لنفترض، دون فقدان للعمومية ، أنu¯{\displaystyle {\bar {u}}}تمت إضافتها لاحقًا إلى المجموعة المركزيةك{\displaystyle \mathbf {K} }بواسطة الخوارزمية الجشعة، لنقل في التكرار رقم i .
  • لكن بما أن الخوارزمية الجشعة تختار دائمًا النقطة الأبعد عن مجموعة المراكز الحالية، فإننا نحصل على ذلكك¯∈جأنا-1{\displaystyle {\bar {k}}\in {\mathcal {C}}_{i-1}}و،

رك(V)≤رجأنا-1(V)=د(u¯،جأنا-1)≤د(u¯،ك¯)≤د(u¯،ج¯)+د(ج¯،ك¯)≤2رoصت{\displaystyle {\begin{align}r^{\mathbf {K} }(\mathbf {V} )\leq r^{{\mathcal {C}}_{i-1}}(\mathbf {V} )&=d({\bar {u}},{\mathcal {C}}_{i-1})\\&\leq d({\bar {u}},{\bar {ك}})\\&\leq d({\bar {u}},{\bar {c}})+d({\bar {c}},{\bar {k}})\\&\leq 2r^{opt}\end{محاذاة}}}[ 4 ]

خوارزمية تقريب أخرى ذات عاملين

تستغل خوارزمية أخرى، بنفس عامل التقريب، حقيقة أن مسألة مركز k تُكافئ إيجاد أصغر فهرس i بحيث يكون لـ G <sub>i </sub> مجموعة مهيمنة بحجم لا يتجاوز k، وتحسب مجموعة مستقلة قصوى لـ G<sub> i</sub> ، باحثةً عن أصغر فهرس i الذي له مجموعة مستقلة قصوى بحجم لا يقل عن k . [ 7 ] لا يمكن إيجاد خوارزمية تقريب بعامل تقريب 2 − ε لأي ε > 0، إلا إذا كان P = NP. [ 8 ] علاوة على ذلك، يجب أن تحقق مسافات جميع الحواف في G متباينة المثلث إذا أُريد تقريب مسألة مركز k ضمن أي عامل ثابت، إلا إذا كان P = NP. [ 9 ]    

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

يمكن إثبات أن مسألة مركز k هي مسألة صعبة من الدرجة W[2] لتقريبها ضمن عامل 2 − ε لأي قيمة ε > 0، عند استخدام k كمعامل. [ 10 ] وينطبق هذا أيضًا عند استخدام بُعد المضاعفة (في الواقع، بُعد مقياس مانهاتن )، إلا إذا كانت P=NP . [ 11 ] عند النظر إلى المعامل المُركّب المُعطى بواسطة k وبُعد المضاعفة ، تظل مسألة مركز k صعبة من الدرجة W[1]، ولكن من الممكن الحصول على مخطط تقريب مُعامل . [ 12 ] وهذا ممكن حتى بالنسبة للمتغير ذي سعات الرؤوس، التي تحدد عدد الرؤوس التي يمكن تعيينها لمركز مفتوح للحل. [ 13 ]    

خوارزميات التقريب

لوP≠شمالP{\displaystyle P\neq NP}لا يمكن حل مشكلة مركز الرأس k (بشكل أمثل) في وقت متعدد الحدود. ومع ذلك، توجد بعض خوارزميات التقريب متعددة الحدود التي تُعطي حلولًا شبه مثالية. على وجه التحديد، حلول تقريبية من الدرجة 2. في الواقع، إذاP≠شمالP{\displaystyle P\neq NP}أفضل حل ممكن يمكن تحقيقه بواسطة خوارزمية ذات زمن متعدد الحدود هو حل تقريبي من الدرجة الثانية. [ 14 ] [ 15 ] [ 16 ] [ 17 ] في سياق مسألة تصغير، مثل مسألة مركز الرأس k ، فإن الحل التقريبي من الدرجة الثانية هو أي حل.ج′{\displaystyle C'} بحيثر(ج′)≤2×ر(الخيار){\displaystyle r(C')\leq 2\times r({\text{OPT}})}، أينر(الخيار){\displaystyle r({\text{OPT}})} يمثل حجم الحل الأمثل. تُعرف الخوارزمية التي تضمن توليد حلول تقريبية من الدرجة 2 بخوارزمية التقريب من الدرجة 2. من أبرز خوارزميات التقريب من الدرجة 2 لمسألة مركز k رأس ، والمذكورة في الأدبيات، خوارزمية Sh [ 18 ] ، وخوارزمية HS [ 17 ] ، وخوارزمية Gon [ 15 ] [ 16 ] . على الرغم من أن هذه الخوارزميات هي الأفضل (من حيث الوقت)، إلا أن أداءها على معظم مجموعات البيانات المعيارية ضعيف للغاية. لهذا السبب، تم تطوير العديد من الطرق الاستدلالية والطرق فوق الاستدلالية على مر الزمن. وخلافًا للاعتقاد السائد، فإن إحدى أكثر الطرق الاستدلالية العملية (من حيث الوقت) لمسألة مركز k رأس تعتمد على خوارزمية CDS، وهي خوارزمية تقريب من الدرجة 3 [ 19 ].

خوارزمية Sh

تم وصف خوارزمية Sh رسميًا بواسطة ديفيد شمويز في عام 1995، [ 18 ] وهي تأخذ كمدخل رسمًا بيانيًا كاملًا غير موجهجي=(V،هـ){\displaystyle G=(V,E)}عدد صحيح موجبك{\displaystyle k}وافتراضر{\displaystyle r} يعتمد ذلك على تحديد حجم الحل الأمثل. تعمل خوارزمية Sh على النحو التالي: اختيار المركز الأولج1{\displaystyle c_{1}} بشكل عشوائي. حتى الآن، يتكون الحل من رأس واحد فقط.ج={ج1}{\displaystyle C=\{c_{1}\}}ثم يختار المركزج2{\displaystyle c_{2}} عشوائياً من المجموعة التي تحتوي على جميع الرؤوس التي تبعد مسافة عنج{\displaystyle C} أكبر من2×ر{\displaystyle 2\times r}. عند هذه النقطة،ج={ج1،ج2}{\displaystyle C=\{c_{1},c_{2}\}}وأخيرًا، يختار المتبقيك-2{\displaystyle k-2} المراكز بنفس الطريقةج2{\displaystyle c_{2}} تم اختيارها. تعقيد خوارزمية Sh هويا(كن){\displaystyle O(kn)}، أينن{\displaystyle n}يمثل عدد الرؤوس.

خوارزمية HS

اقترحت دوريت هوشباوم وديفيد شمويس خوارزمية HS عام 1985، وهي تستند إلى خوارزمية Sh. [ 17 ] من خلال ملاحظة أن قيمةر(الخيار){\displaystyle r({\text{OPT}})}يجب أن يساوي تكلفة بعض المزايا فيهـ{\displaystyle E}وبما أن هناكيا(ن2){\displaystyle O(n^{2})}الحواف فيهـ{\displaystyle E}تُكرر خوارزمية HS بشكل أساسي خوارزمية Sh مع كل تكلفة حافة. ​​تعقيد خوارزمية HS هويا(ن4){\displaystyle O(n^{4})}ومع ذلك، من خلال إجراء بحث ثنائي على المجموعة المرتبة لتكاليف الحواف، يتم تقليل تعقيدها إلىيا(ن2سجل⁡ن){\displaystyle O(n^{2}\log n)}.

خوارزمية غون

اقترح تيوفيلو غونزاليس [ 15 ] ومارتن داير وآلان فريز [ 16 ] خوارزمية غون بشكل مستقل في عام 1985، وهي في الأساس نسخة أكثر قوة من خوارزمية ش. بينما تتطلب خوارزمية ش تخمينًا .ر{\displaystyle r}علىر(الخيار){\displaystyle r({\text{OPT}})}تتجنب خوارزمية غون مثل هذا التخمين من خلال ملاحظة أنه إذا كانت أي مجموعة من الرؤوس على مسافة أكبر من2×ر(الخيار){\displaystyle 2\times r({\text{OPT}})}إذا وُجدت مجموعة رؤوس على مسافة أكبر من 1، فإن أبعد رأس يجب أن يكون داخل هذه المجموعة. لذلك، بدلاً من حساب مجموعة الرؤوس التي تبعد مسافة أكبر من 1 في كل تكرار2×ر{\displaystyle 2\times r}ثم باختيار رأس عشوائي، تقوم خوارزمية غون ببساطة باختيار أبعد رأس عن كل حل جزئيج′{\displaystyle C'}. تعقيد خوارزمية غون هويا(كن){\displaystyle O(kn)}، أينن{\displaystyle n}يمثل عدد الرؤوس.

خوارزمية CDS

اقترح غارسيا دياز وآخرون في عام 2017 [ 19 ] خوارزمية CDS، وهي خوارزمية تقريبية من الدرجة الثالثة، تستوحي أفكارها من خوارزمية غون (الاستدلال على أبعد نقطة)، وخوارزمية HS (التقليم البارامتري)، والعلاقة بين مشكلة مركز الرأس k ومشكلة المجموعة المهيمنة . تتميز خوارزمية CDS بتعقيد زمني قدرهيا(ن4){\displaystyle O(n^{4})}ومع ذلك، من خلال إجراء بحث ثنائي على مجموعة تكاليف الحواف المرتبة، تم اقتراح طريقة استدلالية أكثر كفاءة تُسمى CDSh. تعقيد خوارزمية CDSh هويا(ن2سجل⁡ن){\displaystyle O(n^{2}\log n)}على الرغم من الأداء دون المستوى الأمثل لخوارزمية CDS، والأداء الاستدلالي لخوارزمية CDSh، إلا أن كليهما يقدم أداءً أفضل بكثير من خوارزميات Sh وHS وGon.

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

يمكن إثبات أن مسألة مركز k هي مسألة صعبة من فئة W[2] لتقريبها ضمن عامل 2 − ε لأي قيمة ε > 0، عند استخدام k كمعامل. [ 20 ] وينطبق هذا أيضًا عند استخدام بُعد المضاعفة (في الواقع، بُعد مقياس مانهاتن )، إلا إذا كانت P=NP . [ 11 ] عند النظر إلى المعامل المُركّب المُعطى بواسطة k وبُعد المضاعفة ، تظل مسألة مركز k صعبة من فئة W[1]، ولكن من الممكن الحصول على مخطط تقريب مُعامل . [ 21 ] وهذا ممكن حتى بالنسبة للمتغير ذي سعات الرؤوس، التي تحدد عدد الرؤوس التي يمكن تعيينها لمركز مفتوح للحل. [ 13 ]    

مقارنة تجريبية

تُعدّ بعض مجموعات البيانات المعيارية الأكثر استخدامًا لمسألة مركز الرأس k هي حالات pmed من مكتبة OR-Lib. [ 22 ] وبعض الحالات من مكتبة TSP-Lib. [ 23 ]. يوضح الجدول 1 المتوسط ​​والانحراف المعياري لعوامل التقريب التجريبية للحلول التي تم إنشاؤها بواسطة كل خوارزمية على 40 حالة pmed من مكتبة OR-Lib. [ 19 ].

الجدول 1. عامل التقريب التجريبي على حالات pmed من مكتبة OR-Lib
الخوارزميةμ{\displaystyle \mu }σ{\displaystyle \sigma }تعقيد
HS1.5320.175يا(ن2سجل⁡ن){\displaystyle O(n^{2}\log n)}
غون1.5030.122يا(كن){\displaystyle O(kn)}
سي دي إس إتش1.0350.031يا(ن2سجل⁡ن){\displaystyle O(n^{2}\log n)}
CDS1.0200.027يا(ن4){\displaystyle O(n^{4})}
الجدول 2. عامل التقريب التجريبي على الحالات من مكتبة TSP-Lib
الخوارزميةμ{\displaystyle \mu }σ{\displaystyle \sigma }الخوارزمية
غون1.3960.091يا(كن){\displaystyle O(kn)}
HS1.3180.108يا(ن2سجل⁡ن){\displaystyle O(n^{2}\log n)}
سي دي إس إتش1.1240.065يا(ن2سجل⁡ن){\displaystyle O(n^{2}\log n)}
CDS1.0420.038يا(ن4){\displaystyle O(n^{4})}

الأساليب الاستدلالية متعددة الحدود

خوارزمية جشعة خالصة

تتبع خوارزمية الجشع الخالص (أو Gr) الفكرة الأساسية لخوارزميات الجشع : اتخاذ القرارات المحلية المثلى. في حالة مسألة تحديد مركز k للرؤوس ، يتمثل القرار المحلي الأمثل في اختيار كل مركز بحيث يكون حجم الحل (نصف قطر التغطية) في حده الأدنى في كل تكرار. بعبارة أخرى، المركز الأول الذي يتم اختياره هو الذي يحل مسألة المركز الواحد . أما المركز الثاني الذي يتم اختياره فهو الذي، إلى جانب المركز السابق، يُولّد حلاً بأقل نصف قطر تغطية. ويتم اختيار المراكز المتبقية بنفس الطريقة. تبلغ تعقيد خوارزمية Grيا(كن2){\displaystyle O(kn^{2})}[ 24 ] الأداء التجريبي لخوارزمية Gr ضعيف في معظم حالات القياس المعياري .

خوارزمية التسجيل

طُوِّرت خوارزمية التسجيل (أو Scr) بواسطة يوري ميهيليتش وبوروت روبيتش عام 2005. [ 25 ] تستفيد هذه الخوارزمية من اختزال مسألة مركز الرأس k إلى مسألة مجموعة الهيمنة الدنيا. تُحل المسألة بتقليم الرسم البياني المُدخل بكل قيمة ممكنة لحجم الحل الأمثل، ثم حل مسألة مجموعة الهيمنة الدنيا بطريقة استدلالية. تتبع هذه الطريقة الاستدلالية مبدأ الكسل، الذي يُؤجل كل قرار قدر الإمكان (على عكس الاستراتيجية الجشعة). تبلغ تعقيد خوارزمية Scrيا(ن4){\displaystyle O(n^{4})}يُظهر أداء خوارزمية Scr التجريبي جودةً عاليةً في معظم حالات الاختبار المعيارية. مع ذلك، يصبح وقت تشغيلها غير عملي بسرعة مع ازدياد حجم المدخلات. لذا، يبدو أنها خوارزمية جيدة فقط للحالات الصغيرة.

انظر أيضاً

مراجع

  1. ↑ باتشيكو، خواكين أ.؛ كاسادو، سيلفيا (ديسمبر 2005). "حل نموذجين للموقع مع عدد قليل من المرافق باستخدام أسلوب استدلالي هجين: دراسة حالة واقعية لموارد الرعاية الصحية". الحوسبة وبحوث العمليات . 32 (12): 3075-3091 . doi : 10.1016/j.cor.2004.04.009 . ISSN 0305-0548 . 
  2. ↑ كافيه، أ.؛ نصر، ح. (أغسطس 2011). "حل مشكلة المركز المشروط وغير المشروط باستخدام بحث التناغم المعدل: دراسة حالة واقعية" . ساينتيا إيرانيكا . 18 (4): 867-877 . doi : 10.1016/j.scient.2011.07.010 . ISSN 1026-3098 . 
  3. ↑ حكيمي، إس إل (1964). "المواقع المثلى لمراكز التبديل والمراكز المطلقة والوسائط في الرسم البياني". بحوث العمليات . 12 (3): 450-459 . doi : 10.1287/opre.12.3.450 . JSTOR 168125 . 
  4. 1 2 3 هار-بيليد، سارييل (2011). خوارزميات التقريب الهندسي . بوسطن، ماساتشوستس، الولايات المتحدة الأمريكية: الجمعية الرياضية الأمريكية. ISBN 978-0821849118.
  5. ^ فازيراني ، فيجاي ف. (2003)، خوارزميات التقريب ، برلين: سبرينغر، الصفحات من 47 إلى 48، ISBN  3-540-65367-8
  6. ↑ غونزاليس، تيوفيلو ف. (1985)، "التجميع لتقليل أقصى مسافة بين المجموعات"، علوم الحاسوب النظرية ، المجلد 38، دار نشر إلسيفير ساينس بي في، الصفحات 293-306 ، doi : 10.1016/0304-3975(85)90224-5  
  7. ↑ هوشباوم، دوريت س .؛ شمويز، ديفيد ب. (1986)، "نهج موحد لخوارزميات التقريب لمشاكل الاختناق"، مجلة ACM ، المجلد 33، الصفحات 533-550 ، doi : 10.1145/5925.5933 ، ISSN 0004-5411 ، S2CID 17975253    
  8. ↑ هوشباوم، دوريت س. (1997)، خوارزميات التقريب للمسائل الصعبة من نوع NP ، بوسطن: شركة PWS للنشر، الصفحات 346-398 ، ISBN  0-534-94968-1
  9. ^ كريسينزي، بييرلويجي. كان، فيجو؛ هالدورسون، ماغنوس؛ الأماكن القريبة : Woeginger، Gerhard (2000)، “الحد الأدنى لمركز k”، خلاصة وافية لمشاكل تحسين NP
  10. ↑ فيلدمان، أندرياس إميل (2019-03-01). "تقريبات ذات معلمات ثابتة لمسائل مركز k في الرسوم البيانية ذات الأبعاد المنخفضة للطرق السريعة" (ملف PDF) . Algorithmica . 81 (3): 1031–1052 . doi : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 . S2CID 46886829 .  
  11. 1 2 فيدر، توماس؛ غرين، دانيال (1988-01-01). "الخوارزميات المثلى للتجميع التقريبي" . وقائع الندوة السنوية العشرين لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '88 . نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 434-444 . doi : 10.1145/62212.62255 . ISBN  978-0-89791-264-8. S2CID 658151 . 
  12. ↑ فيلدمان، أندرياس إميل؛ ماركس، دانيال (2020-07-01). "صعوبة مسألة المركز k في شبكات النقل باستخدام المعاملات" (ملف PDF) . Algorithmica . 82 (7): 1989–2005 . doi : 10.1007/s00453-020-00683-w . ISSN 1432-0541 . S2CID 3532236 .  
  13. 1 2 فيلدمان، أندرياس إميل؛ فو، تونغ آنه (2022). "مركز $$k$$ المعمم: التمييز بين المضاعفة وبُعد الطريق السريع" . في بيكوس، مايكل أ.؛ كوفمان، مايكل (محرران). مفاهيم نظرية الرسم البياني في علوم الحاسوب . سلسلة محاضرات في علوم الحاسوب. المجلد 13453. تشام: دار نشر سبرينغر الدولية. الصفحات 215-229 . arXiv : 2209.00675 . doi : 10.1007/978-3-031-15914-5_16 . ISBN   978-3-031-15914-5.
  14. ↑ كاريف، أ.؛ حكيمي، س. ل. (ديسمبر 1979). "نهج خوارزمي لمشاكل تحديد مواقع الشبكات. الجزء الأول: مراكز p". مجلة SIAM للرياضيات التطبيقية . 37 (3): 513-538 . doi : 10.1137/0137040 . ISSN 0036-1399 . 
  15. 1 2 3 غونزاليس، تيوفيلو ف. (1985). "التجميع لتقليل أقصى مسافة بين المجموعات" . علوم الحاسوب النظرية . 38 : 293-306 . doi : 10.1016/0304-3975(85)90224-5 . ISSN 0304-3975 . 
  16. 1 2 3 داير، م. إي.؛ فريز، أ. م. (فبراير 1985). "طريقة استدلالية بسيطة لمسألة مركز p". رسائل بحوث العمليات . 3 (6): 285-288 . doi : 10.1016/0167-6377(85)90002-1 . ISSN 0167-6377 . 
  17. هوشباوم ، دوريت س .؛ شمويز ، ديفيد ب. (مايو 1985). "أفضل طريقة استدلالية ممكنة لمسألة المركز k ". رياضيات بحوث العمليات . 10 (2): 180-184 . doi : 10.1287/moor.10.2.180 . ISSN 0364-765X . 
  18. 1 2 شمويز، ديفيد ب. (1995). "حساب الحلول شبه المثلى لمسائل التحسين التوافقي". التحسين التوافقي . سلسلة DIMACS في الرياضيات المتقطعة وعلوم الحاسوب النظرية. المجلد 20. الصفحات 355-397. CiteSeerX 10.1.1.33.1719 . doi : 10.1090/dimacs/020/07 . ISBN    9780821802397.
  19. 1 2 3 غارسيا-دياز، خيسوس؛ سانشيز-هيرنانديز، جايرو؛ مينتشاكا-مينديز، ريكاردو؛ مينتشاكا-مينديز، رولاندو (2017-07-01). "عندما يُعطي عامل تقريب أسوأ أداءً أفضل: خوارزمية تقريبية من الدرجة 3 لمسألة مركز الرأس k ". مجلة الاستدلال . 23 (5): 349-366 . doi : 10.1007/s10732-017-9345-x . ISSN 1381-1231 . S2CID 254500532 .  
  20. ↑ فيلدمان، أندرياس إميل (2019-03-01). "تقريبات ذات معلمات ثابتة لمسائل k-Center في الرسوم البيانية ذات الأبعاد المنخفضة للطرق السريعة" . Algorithmica . 81 (3): 1031–1052 . arXiv : 1605.02530 . doi : 10.1007 /s00453-018-0455-0 . ISSN 1432-0541 . S2CID 46886829 .  
  21. ↑ فيلدمان، أندرياس إميل؛ ماركس، دانيال (2020-07-01). "صعوبة مسألة المركز k في شبكات النقل باستخدام المعاملات" . Algorithmica . 82 (7): 1989–2005 . arXiv : 1802.08563 . doi : 10.1007/s00453-020-00683-w . ISSN 1432-0541 . S2CID 3532236 .  
  22. ↑ بيزلي، جيه إي (1990). "مكتبة بحوث العمليات: توزيع مسائل الاختبار عبر البريد الإلكتروني". مجلة جمعية بحوث العمليات . 41 (11): 1069-1072 . doi : 10.2307/2582903 . JSTOR 2582903 . 
  23. ↑ راينيلت، جيرهارد (نوفمبر 1991). "TSPLIB - مكتبة مسائل البائع المتجول". مجلة ORSA للحوسبة . 3 (4): 376-384 . doi : 10.1287/ijoc.3.4.376 . ISSN 0899-1499 . 
  24. ↑ رانا، راتان؛ غارغ، ديباك (مارس 2009). "الأساليب الاستدلالية لمسألة مركز K". المؤتمر الدولي للحوسبة المتقدمة IEEE لعام 2009. IEEE. الصفحات 332-335 . doi : 10.1109/iadcc.2009.4809031 . ISBN  9781424429271. S2CID 12453616 . 
  25. ↑ ميهيليتش، يوري؛ روبيتش، بوروت (2005). "حل مشكلة المركز k بكفاءة باستخدام خوارزمية المجموعة المهيمنة" . مجلة الحوسبة وتكنولوجيا المعلومات . 13 (3): 225. CiteSeerX 10.1.1.205.3118 . doi : 10.2498/cit.2005.03.05 . ISSN 1330-1136 .  

للمزيد من القراءة