{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T15:04:58Z","timestamp":1775055898828,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,11,19]],"date-time":"2016-11-19T00:00:00Z","timestamp":1479513600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Doctoral Fellowships of Excellence Program"},{"name":"Mordecai and Monique Katz Graduate Fellowship Program"},{"name":"ISF","award":["1083\/13 and 1241\/12"],"award-info":[{"award-number":["1083\/13 and 1241\/12"]}]},{"name":"BSF","award":["2012344"],"award-info":[{"award-number":["2012344"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,1,31]]},"abstract":"<jats:p>\n            We consider the classic problem of envy-free division of a heterogeneous good (\u201ccake\u201d) among several agents. It is known that, when the allotted pieces must be connected, the problem cannot be solved by a finite algorithm for three or more agents. The impossibility result, however, assumes that the entire cake must be allocated. In this article, we replace the entire-allocation requirement with a weaker\n            <jats:italic>partial-proportionality<\/jats:italic>\n            requirement: the piece given to each agent must be worth for it at least a certain positive fraction of the entire cake value. We prove that this version of the problem is solvable in bounded time even when the pieces must be connected. We present simple, bounded-time envy-free cake-cutting algorithms for (1) giving each of\n            <jats:italic>n<\/jats:italic>\n            agents a connected piece with a positive value; (2) giving each of three agents a connected piece worth at least 1\/3; (3) giving each of four agents a connected piece worth at least 1\/7; (4) giving each of four agents a disconnected piece worth at least 1\/4; and (5) giving each of\n            <jats:italic>n<\/jats:italic>\n            agents a disconnected piece worth at least (1 \u2212 \u03f5)\/\n            <jats:italic>n<\/jats:italic>\n            for any positive \u03f5.\n          <\/jats:p>","DOI":"10.1145\/2988232","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T14:01:46Z","timestamp":1479736906000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Waste Makes Haste"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7497-5834","authenticated-orcid":false,"given":"Erel","family":"Segal-Halevi","sequence":"first","affiliation":[{"name":"Bar-Ilan University, Ramat-Gan 5290002, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avinatan","family":"Hassidim","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat-Gan 5290002, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yonatan","family":"Aumann","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat-Gan 5290002, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,11,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-015-0943-y"},{"key":"e_1_2_1_2_1","volume-title":"A generalization of the AL method for fair allocation of indivisible objects. Economic Theory Bulletin","author":"Aziz Haris","year":"2015"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897522"},{"key":"e_1_2_1_4_1","volume-title":"A discrete and bounded envy-free cake cutting protocol for any number of agents. To appear in Proceedings of FOCS","author":"Aziz Haris","year":"2016"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2004.03.006"},{"key":"e_1_2_1_6_1","volume-title":"Two-person fair division of indivisible items: An efficient, envy-free algorithm. Social Science Research Network Working Paper Series (5","author":"Brams Steven J.","year":"2013"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1995.11990526"},{"key":"e_1_2_1_8_1","volume-title":"Taylor","author":"Brams Steven J.","year":"1996"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.07.005"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 30th AAAI Conference on Artificial Intelligence. http:\/\/arxiv.org\/abs\/1307","author":"Br\u00e2nzei Simina"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1116"},{"key":"e_1_2_1_12_1","unstructured":"The Sage Developers. 2015. SageMath the Sage Mathematics Software System (Version 6.7). http:\/\/www.sagemath.org.  The Sage Developers. 2015. SageMath the Sage Mathematics Software System (Version 6.7). http:\/\/www.sagemath.org."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.17"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000819"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68880-8_16"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90005-2"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 27th AAAI Conference on Artificial Intelligence. 555--561","author":"Kurokawa David"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2000.12005263"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1661445.1661484"},{"key":"e_1_2_1_20_1","volume-title":"Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, Jerome Lang, and Ariel D","author":"Procaccia Ariel D."},{"key":"e_1_2_1_21_1","volume-title":"Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts. (13","author":"Reitzig Raphael","year":"2015"},{"key":"e_1_2_1_22_1","volume-title":"Webb","author":"Robertson Jack M.","year":"1998"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02158-9_25"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence. 1021--1028","author":"Segal-Halevi Erel","year":"2015"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 14th International Conference on Autonomous Agents and Multi-Agent Systems. 901--908","author":"Segal-Halevi Erel","year":"2015"},{"key":"e_1_2_1_26_1","first-page":"1","article-title":"The problem of fair division","volume":"16","author":"Steinhaus Hugo","year":"1948","journal-title":"Econometrica"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1980.11995109"},{"key":"e_1_2_1_28_1","volume-title":"Envy-free cake divisions cannot be found by finite protocols. Electronic Journal of Combinatorics (Jan","author":"Stromquist Walter","year":"2008"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.2307\/2589747"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2006.07.003"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2988232","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2988232","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:40:07Z","timestamp":1750218007000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2988232"}},"subtitle":["Bounded Time Algorithms for Envy-Free Cake Cutting with Free Disposal"],"short-title":[],"issued":{"date-parts":[[2016,11,19]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1,31]]}},"alternative-id":["10.1145\/2988232"],"URL":"https:\/\/doi.org\/10.1145\/2988232","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,19]]},"assertion":[{"value":"2015-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}