في هذه الورقة، نقدم خوارزميات زائفة حتمية فعالة لمشاكل التقسيم الأدنى العالمي وتقسيم s-t الأدنى. زمن تشغيل خوارزمينا لمشكلة التقسيم الأدنى العالمي هو بشكل تقريبي أفضل من أسرع خوارزمية حتمية متسلسلة للتقسيم الأدنى العالمي (هينزينجر، لي، راو، وانغ؛ SODA 2024). علاوة على ذلك، نقوم بتنفيذ خوارزمينا في نماذج البث، PRAM، واستعلامات القطع، حيث لا تُعرف خوارزميات حتمية عالمية فعالة.
أغاروالا وآخرون (الخميس) درسوا هذا السؤال.