License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2018.15
URN: urn:nbn:de:0030-drops-88062
Go to the corresponding LIPIcs Volume Portal

Cui, Guangqi ; Dickerson, John ; Durvasula, Naveen ; Gasarch, William ; Metz, Erik ; Prinz, Jacob ; Raman, Naveen ; Smolyak, Daniel ; Yoo, Sung Hyun

A Muffin-Theorem Generator

LIPIcs-FUN-2018-15.pdf (0.5 MB)


Consider the following FUN problem. Given m,s you want to divide m muffins among s students so that everyone gets m/(s) muffins; however, you want to maximize the minimum piece so that nobody gets crumbs. Let f(m,s) be the size of the smallest piece in an optimal procedure.
We study the case where ceil(2m/s)=3 because (1) many of our hardest open problems were of this form until we found this method, (2) we have used the technique to generate muffin-theorems, and (3) we conjecture this can be used to solve the general case. We give (1) an algorithm to find an upper bound for f(m,s) when ceil(2m/s)(and some ways to speed up that algorithm if certain conjectures are true), (2) an algorithm that uses the information from (1) to try to find a lower bound on f(m,s) (a procedure) which matches the upper bound, (3) an algorithm that uses the information from (1) to generate muffin-theorems, and (4) an algorithm that we think works well in practice to find f(m,s) for any m,s.

BibTeX - Entry

  author =	{Guangqi Cui and John Dickerson and Naveen Durvasula and William Gasarch and Erik Metz and Jacob Prinz and Naveen Raman and Daniel Smolyak and Sung Hyun Yoo},
  title =	{{A Muffin-Theorem Generator}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{15:1--15:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Hiro Ito and Stefano Leonardi and Linda Pagli and Giuseppe Prencipe},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-88062},
  doi =		{10.4230/LIPIcs.FUN.2018.15},
  annote =	{Keywords: Fair Division, Theorem Generation}

Keywords: Fair Division, Theorem Generation
Collection: 9th International Conference on Fun with Algorithms (FUN 2018)
Issue Date: 2018
Date of publication: 04.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI