1 Search Results for "Ueda, Takahiro"

Document

DOI: 10.4230/LIPIcs.FUN.2016.21

How to Solve the Cake-Cutting Problem in Sublinear Time

Authors: Hiro Ito and Takahiro Ueda

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract

The cake-cutting 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 cake-cutting problem in sublinear-time. 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 cake-cutting problem in sublinear-time. Generally speaking, solving a problem in sublinear-time requires the use of approximations. However, in our framework, we introduce the concept of "epsilon n-victims," 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 n-r 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.

Cite as

Hiro Ito and Takahiro Ueda. How to Solve the Cake-Cutting Problem in Sublinear Time. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.FUN.2016.21,
  author =	{Ito, Hiro and Ueda, Takahiro},
  title =	{{How to Solve the Cake-Cutting Problem in Sublinear Time}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.21},
  URN =		{urn:nbn:de:0030-drops-58639},
  doi =		{10.4230/LIPIcs.FUN.2016.21},
  annote =	{Keywords: sublinear-time algorithms, cake-cutting problem, simple fair, preassign, approximation}
}

Refine by Author
1 Ito, Hiro
1 Ueda, Takahiro

Refine by Classification

Refine by Keyword
1 approximation
1 cake-cutting problem
1 preassign
1 simple fair
1 sublinear-time algorithms

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Ueda, Takahiro"

How to Solve the Cake-Cutting Problem in Sublinear Time

Abstract

Cite as

Thanks for your feedback!

Could not send message