Key points are not available for this paper at this time.
نstudى مشكلة التوزيع العادل لـ M عنصر غير قابل للتقسيم بين N وكيلًا باستخدام المفهوم الشائع لحصة الحد الأقصى الأدنى كمعيار لعدالة التوزيع. حصة الحد الأقصى الأدنى لوكيل هي القيمة الأكبر التي يمكنها ضمانها لنفسها إذا سُمح لها باختيار تقسيم العناصر إلى N حزم (واحدة لكل وكيل)، بشرط أن تتلقى أقل حزمة تفضلها. يوفر توزيع حصة الحد الأقصى الأدنى لكل وكيل حزمة تساوي على الأقل حصته. بينما من المعروف أن مثل هذا التوزيع قد لا يوجد ، قدمت سلسلة من الأعمال خوارزميات تقريب 2/3 حيث يحصل كل وكيل على حزمة تساوي على الأقل 2/3 من حصته. مؤخرًا، حسّن Ghodsi وآخرون، 2018 ضمانة التقريب إلى 3/4. تستخدم الأعمال السابقة خوارزميات معقدة، باستثناء Barman وKrishna Murthy، 2017 التي تعد حلاً جشعًا بسيطًا لكنها تتطلب تقنيات تحليل معقدة. في هذه الورقة، نقترح تقريب 2/3 لحصة الحد الأقصى الأدنى الذي يقدم كلًا من خوارزمية بسيطة وتحليل مباشر. على العكس من الخوارزميات الأخرى، يسمح نهجنا بفهم بسيط وبديهي لسبب نجاحه.
درس Garg وآخرون (ثلاثاء ،) هذا السؤال.