{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:37Z","timestamp":1740109297729,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002835","name":"Chalmers University of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002835","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A splittable good provided in<jats:italic>n<\/jats:italic>pieces shall be divided as evenly as possible among<jats:italic>m<\/jats:italic>agents, where every agent can take shares from at most<jats:italic>F<\/jats:italic>pieces. We call<jats:italic>F<\/jats:italic>the fragmentation and mainly restrict attention to the cases<jats:inline-formula><jats:alternatives><jats:tex-math>$$F=1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>F<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and<jats:inline-formula><jats:alternatives><jats:tex-math>$$F=2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>F<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. For<jats:inline-formula><jats:alternatives><jats:tex-math>$$F=1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>F<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the max\u2013min and min\u2013max problems are solvable in linear time. The case<jats:inline-formula><jats:alternatives><jats:tex-math>$$F=2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>F<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>has neat formulations and structural characterizations in terms of weighted graphs. First we focus on perfectly balanced solutions. While the problem is strongly NP-hard in general, it can be solved in linear time if<jats:inline-formula><jats:alternatives><jats:tex-math>$$m\\ge n-1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>m<\/mml:mi><mml:mo>\u2265<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>-<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and a solution always exists in this case, in contrast to<jats:inline-formula><jats:alternatives><jats:tex-math>$$F=1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>F<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Moreover, the problem is fixed-parameter tractable in the parameter<jats:inline-formula><jats:alternatives><jats:tex-math>$$2m-n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mn>2<\/mml:mn><mml:mi>m<\/mml:mi><mml:mo>-<\/mml:mo><mml:mi>n<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. (Note that this parameter measures the number of agents above the trivial threshold<jats:inline-formula><jats:alternatives><jats:tex-math>$$m=n\/2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>m<\/mml:mi><mml:mo>=<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>\/<\/mml:mo><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>.) The structural results suggest another related problem where unsplittable items shall be assigned to subsets so as to balance the average sizes (rather than the total sizes) in these subsets. We give an approximation-preserving reduction from our original splitting problem with fragmentation<jats:inline-formula><jats:alternatives><jats:tex-math>$$F=2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>F<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>to this averaging problem, and some approximation results in cases when<jats:italic>m<\/jats:italic>is close to either<jats:italic>n<\/jats:italic>or<jats:italic>n<\/jats:italic>\u00a0\/\u00a02.<\/jats:p>","DOI":"10.1007\/s00453-019-00643-z","type":"journal-article","created":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T22:37:06Z","timestamp":1572043026000},"page":"1298-1328","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Dividing Splittable Goods Evenly and With Limited Fragmentation"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4047-7594","authenticated-orcid":false,"given":"Peter","family":"Damaschke","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,10,25]]},"reference":[{"key":"643_CR1","unstructured":"Abboud, A., Lewi, K., Williams, R.: On the parameterized complexity of k-SUM. CoRR arXiv:abs\/1311.3054 (2013)"},{"key":"643_CR2","first-page":"26","volume-title":"Lecture Notes in Computer Science","author":"Yonatan Aumann","year":"2010","unstructured":"Aumann, Y., Dombb, Y.: The efficiency of fair division with connected pieces. In: Saberi, A. (ed.) WINE, LNCS 6484, pp. 26\u201337 (2010)"},{"key":"643_CR3","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF01193837","volume":"47","author":"L Babel","year":"1998","unstructured":"Babel, L., Kellerer, H., Kotov, V.: The $$k$$-partitioning problem. Math. Methods OR 47, 59\u201382 (1998)","journal-title":"Math. Methods OR"},{"key":"643_CR4","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V.R., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci. 7, 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"643_CR5","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.disopt.2012.08.001","volume":"9","author":"K Cechl\u00e1rov\u00e1","year":"2012","unstructured":"Cechl\u00e1rov\u00e1, K., Pill\u00e1rov\u00e1, E.: On the computability of equitable divisions. Discrete Optim. 9, 249\u2013257 (2012)","journal-title":"Discrete Optim."},{"key":"643_CR6","doi-asserted-by":"crossref","unstructured":"Chen, L., Jansen, K., Luo, W., Zhang, G.: An efficient PTAS for parallel machine scheduling with capacity constraints. In: Chan, T.H.H., Li, M., Wang, L. (eds.), COCOA, LNCS 10043, pp. 608\u2013623 (2016)","DOI":"10.1007\/978-3-319-48749-6_44"},{"issue":"4","key":"643_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2000807.2000819","volume":"7","author":"Jeff Edmonds","year":"2011","unstructured":"Edmonds, J., Pruhs, K.: Cake cutting really is not a piece of cake. ACM Trans. Alg. 7, article 51 (2011)","journal-title":"ACM Transactions on Algorithms"},{"key":"643_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, Dallas (1979)"},{"key":"643_CR9","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.ejc.2017.04.002","volume":"64","author":"L Gellert","year":"2017","unstructured":"Gellert, L., Sanyal, R.: On degree sequences of undirected, directed, and bidirected graphs. Eur. J. Comb. 64, 113\u2013124 (2017)","journal-title":"Eur. J. Comb."},{"key":"643_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.12.007","volume":"665","author":"PA Golovach","year":"2017","unstructured":"Golovach, P.A., Mertzios, G.B.: Graph editing to a given degree sequence. Theor. Comput. Sci. 665, 1\u201312 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"643_CR11","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34, 144\u2013162 (1987)","journal-title":"J. ACM"},{"key":"643_CR12","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"DS Hochbaum","year":"1988","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM J. Comput. 17, 539\u2013551 (1988)","journal-title":"SIAM J. Comput."},{"key":"643_CR13","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E Horowitz","year":"1976","unstructured":"Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23, 317\u2013327 (1976)","journal-title":"J. ACM"},{"key":"643_CR14","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"OH Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22, 463\u2013468 (1975)","journal-title":"J. ACM"},{"key":"643_CR15","first-page":"359","volume":"39","author":"H Kellerer","year":"2011","unstructured":"Kellerer, H., Kotov, V.: A $$3\/2$$-approximation algorithm for $$k_i$$-partitioning. Oper. Res. Lett. 39, 359\u2013362 (2011)","journal-title":"Oper. Res. Lett."},{"key":"643_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004)"},{"key":"643_CR17","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.ifacol.2016.07.557","volume":"49","author":"J Martinovic","year":"2016","unstructured":"Martinovic, J., Jorswieck, E., Scheithauer, G.: The skiving stock problem and its application to cognitive radio networks. IFAC-PapersOnLine 49, 99\u2013104 (2016)","journal-title":"IFAC-PapersOnLine"},{"key":"643_CR18","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2006)"},{"key":"643_CR19","doi-asserted-by":"crossref","unstructured":"Procaccia, A.D.: Cake-cutting algorithms. In: Handbook of Computational Social Choice. Cambridge University Press, pp. 261\u2013283 (2015)","DOI":"10.1017\/CBO9781107446984.014"},{"key":"643_CR20","doi-asserted-by":"publisher","first-page":"3365","DOI":"10.1007\/s00453-017-0392-3","volume":"80","author":"R Reitzig","year":"2018","unstructured":"Reitzig, R., Wild, S.: Building Fences Straight and High: An Optimal Algorithm for Finding the Maximum Length You Can Cut $$k$$ Times from Given Sticks. Algorithmica 80, 3365\u20133396 (2018)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00643-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00643-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00643-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,2]],"date-time":"2022-10-02T18:05:20Z","timestamp":1664733920000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00643-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,25]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["643"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00643-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,10,25]]},"assertion":[{"value":"7 May 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}