کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141896 957100 2007 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the complexity of cake cutting
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
On the complexity of cake cutting
چکیده انگلیسی

In the cake cutting problem, n≥2n≥2 players want to cut a cake into nn pieces so that every player gets a ‘fair’ share of the cake by his/her own measure.We prove that in a certain, natural cake cutting model, every fair cake division protocol for nn players must use Ω(nlogn)Ω(nlogn) cuts and evaluation queries in the worst case. Up to a small constant factor, this lower bound matches a corresponding upper bound in the same model obtained by Even and Paz, from 1984.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 4, Issue 2, 1 June 2007, Pages 213–220
نویسندگان
, ,