Ito, Hiro ;
Ueda, Takahiro
How to Solve the CakeCutting Problem in Sublinear Time
Abstract
The cakecutting problem refers to the issue of dividing a cake into pieces and distributing them to players who have different value measures related to the cake, and who feel that their portions should be "fair." The fairness criterion specifies that in situations where n is the number of players, each player should receive his/her portion with at least 1/n of the cake value in his/her measure. In this paper, we show algorithms for solving the cakecutting problem in sublineartime. More specifically, we preassign fair portions to o(n) players in o(n)time, and minimize the damage to the rest of the players. All currently known algorithms require Omega(n)time, even when assigning a portion to just one player, and it is nontrivial to revise these algorithms to run in o(n)time since many of the remaining players, who have not been asked any queries, may not be satisfied with the remaining cake. To challenge this problem, we begin by providing a framework for solving the cakecutting problem in sublineartime. Generally speaking, solving a problem in sublineartime requires the use of approximations. However, in our framework, we introduce the concept of "epsilon nvictims," which means that (epsilon x n) players (victims) may not get fair portions, where 0< epsilon =< 1 is an arbitrary constant. In our framework, an algorithm consists of the following two parts: In the first (Preassigning) part, it distributes fair portions to r < n players in o(n)time. In the second (Completion) part, it distributes fair portions to the remaining nr players except for the (epsilon x n) victims in poly(n)time. There are two variations on the r players in the first part. Specifically, whether they can or cannot be designated. We will then present algorithms in this framework. In particular, an O(r/epsilon)time algorithm for r =< (epsilon x n)/127 undesignated players with (epsilon x n)victims, and an tilde{O}(r^2/epsilon)time algorithm for r =< (epsilon x e^(((sqrt(ln(n)))/7) designated players and epsilon =< 1/e with (epsilon x n)victims are presented.
BibTeX  Entry
@InProceedings{ito_et_al:LIPIcs:2016:5863,
author = {Hiro Ito and Takahiro Ueda},
title = {{How to Solve the CakeCutting Problem in Sublinear Time}},
booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)},
pages = {21:121:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770057},
ISSN = {18688969},
year = {2016},
volume = {49},
editor = {Erik D. Demaine and Fabrizio Grandoni},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5863},
URN = {urn:nbn:de:0030drops58639},
doi = {10.4230/LIPIcs.FUN.2016.21},
annote = {Keywords: sublineartime algorithms, cakecutting problem, simple fair, preassign, approximation}
}
2016
Keywords: 

sublineartime algorithms, cakecutting problem, simple fair, preassign, approximation 
Seminar: 

8th International Conference on Fun with Algorithms (FUN 2016)

Issue date: 

2016 
Date of publication: 

2016 