DC FieldValueLanguage
dc.contributor.authorJojić, Duškoen_US
dc.contributor.authorPanina, Gaianeen_US
dc.contributor.authorŽivaljević, Radeen_US
dc.date.accessioned2021-07-14T11:59:31Z-
dc.date.available2021-07-14T11:59:31Z-
dc.date.issued2021-
dc.identifier.issn0895-4801-
dc.identifier.urihttp://researchrepository.mi.sanu.ac.rs/handle/123456789/4621-
dc.description.abstractWe prove several versions of Alon's necklace-splitting theorem, subject to additional constraints, as illustrated by the following results. (1) The "almost equicardinal necklace-splitting theorem" claims that, without increasing the number of cuts, one guarantees the existence of a fair splitting such that each thief is allocated almost the same number of pieces of the necklace (including "degenerate pieces" if they exist), provided the number of thieves r = p\nu is a prime power. By "almost the same" we mean that for each pair of thieves one of them can be given at most one piece more (one piece less) than the other. (2) The "binary splitting theorem" claims that if r = 2d and the thieves are associated with the vertices of a d-cube, then, without increasing the number of cuts, one can guarantee the existence of a fair splitting such that adjacent pieces are allocated to thieves that share an edge of the cube. This result provides a positive answer to the "binary splitting necklace conjecture" in the case r = 2d from Conjecture 2.11 in [M. Asada et al., SIAM J. Discrete Math., 32 (2018), pp. 591-610]. (3) An interesting variation arises when the thieves have their own individual preferences. We prove several envy-free, fair necklace-splitting theorems of various level of generality, as illustrated by the envy-free versions of (a) Alon's original necklace-splitting theorem, (b) the almost equicardinal splitting theorem, and (c) the binary splitting theorem, etc.en_US
dc.publisherSIAMen_US
dc.relation.ispartofSIAM Journal on Discrete Mathematicsen_US
dc.subjectCollectively unavoidable complexes | Configuration space/test map scheme | Envy-free division | Necklace-splitting theoremen_US
dc.titleSplitting necklaces, with constraintsen_US
dc.typeArticleen_US
dc.identifier.doi10.1137/20M1331949-
dc.identifier.scopus2-s2.0-85108728324-
dc.contributor.affiliationMechanicsen_US
dc.contributor.affiliationMathematical Institute of the Serbian Academy of Sciences and Arts-
dc.relation.firstpage1268-
dc.relation.lastpage1286-
dc.relation.issue2-
dc.relation.volume35-
dc.description.rank~M23-
item.cerifentitytypePublications-
item.grantfulltextnone-
item.openairetypeArticle-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.fulltextNo Fulltext-
crisitem.author.orcid0000-0001-9801-8839-
Show simple item record

SCOPUSTM   
Citations

6
checked on Jun 21, 2024

Page view(s)

83
checked on May 9, 2024

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.