شجرة الانتشار الحد الأدنى المتوازية بشكل كبير في الفضاءات المترية العامة

ندرس مشكلة شجرة الانتشار الحد الأدنى (MST) في نموذج الحوسبة المتوازية بشكل كبير (MPC). تركيزنا بشكل خاص على نظام *أقل من خطي بدقة* في MPC حيث المساحة لكل آلة هي O (n^). هنا n هو عدد القمم والثابت (0، 1) يمكن أن يصبح صغيرًا بشكل تعسفي. تقبل مشكلة MST خوارزمية بسيطة ومعروفة O (n) -round في نموذج MPC. عندما يمكن أن تكون الأوزان تعسفية، يتطابق هذا مع حد أدنى شرطي قدره (n) والذي يتبع من فرضية 1vs2-Cycle المعروفة. على هذا النحو، يركز الكثير من الأدبيات على كسر الحاجز اللوغاريتمي في نسخ أكثر هيكلية من المشكلة، مثل عندما تتوافق القمم مع نقاط في الفضاءات الإقليدية منخفضة أو عالية الأبعاد. في هذا العمل، نركز بشكل عام على الفضاءات المترية. أي أن جميع الأوزان الثنائية يتم تقديمها وضمانها لتلبية عدم المساواة المثلثية، ولكنها غير مخططة من نواحٍ أخرى. نُظهر أنه لأي > 0، يمكن العثور على MST تقريبية (1+) في O (1 + n) جولة، وهي أول خوارزمية جولات o (n) لإيجاد أي تقريب ثابت في هذا السياق. بالإضافة إلى كونها قابلة للتطبيق على دالات الوزن الأكثر عمومية، فإن خوارزميتنا تُحسن أيضًا بشكل طفيف من تعقيد جولات O (n n) من JMNZ24، SODA'24 وتحسن بشكل كبير تقديرها من ثابت كبير إلى 1+. فيما يتعلق بالحد الأدنى، نثبت أنه تحت فرضية 1vs2-Cycle، هناك حاجة إلى (1) جولات لإيجاد MST تقريبية (1+) في المترية العامة. وتجدر الإشارة إلى أنه بينما يتمسّك العديد من الحدود الدنيا الحالية في نموذج MPC تحت فرضية 1vs2-Cycle