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

چکیده انگلیسی
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
Journal: Discrete Optimization - Volume 4, Issue 2, 1 June 2007, Pages 213–220
نویسندگان
Gerhard J. Woeginger, Jiří Sgall,