حدود تقريب مشددة على خوارزمية بسيطة للحد الأدنى من متوسط وقت البحث في الأشجار

ظهر الثابت الرسومي EPT-sum في عدة مجالات غير مترابطة في السنوات الأخيرة: كدالة هدف للتجمع الهرمي، وكإصدار أكثر دقة لمشكلة تصنيف الحواف الكلاسيكية، وأيضًا، عندما تكون المدخلات شجرة موزونة بالرؤوس، كمقياس لطول البحث المتوسط/المتوقع في مجموعة مرتبة جزئيًا. يُعرف EPT-sum للرسم البياني G بأنه الحد الأدنى لمجموع عمق كل ورقة في شجرة تقسيم الحواف (EPT)، وهي شجرة متجذرة حيث تتوافق الأوراق مع الرؤوس في G وتتوافق العقد الداخلية مع الحواف في G. يتم تقديم خوارزمية بسيطة تقرب EPT-sum على الأشجار من خلال اختيار الحافة الأكثر توازنًا في شجرة المدخلات G لبناء EPT من G بشكل متكرر. بسبب سرعتها، تُستخدم هذه الخوارزمية ذات القطع المتوازن في الممارسة العملية. في هذه الورقة، نوضح أن خوارزمية القطع المتوازن تعطي تقريبًا قدره 1.5 لـ EPT-sum على الأشجار، مما يعني تحليلًا مشددًا ويجيب على سؤال طرحه Cicalese وآخرون في عام 2014.