Splitting necklaces
From MaRDI portal
Let N be an opened necklace with \(k\cdot a_ i\) beads of color i, \(1\leq i\leq t\). A k-splitting of this necklace is a partition of the necklace into k parts, each consisting of a finite number of nonoverlapping intervals of beads whose union captures precisely \(a_ i\) beads of color i, \(1\leq i\leq t\). The size of the k-splitting is the number of cuts that form the intervals of the splitting, which is one less than the total number of these intervals. The main result is the following theorem: Every necklace with \(k\cdot a_ i\) beads of color i, \(1\leq i\leq t\), has a k-splitting of size at most (k-1)\(\cdot t\). The number (k-1)\(\cdot t\) is best possible. The author formulates the continuous version of the k-splitting problem and proves that it generalizes the discrete one. The proof of this version is topological.
Recommendations
Cites work
- A framework for solving VLSI graph layout problems
- A Moment Problem in L 1 Approximation
- Bisection of Circle Colorings
- scientific article; zbMATH DE number 3232606 (Why is no real title available?)
- On a Topological Generalization of a Theorem of Tverberg
- The Borsuk-Ulam Theorem and Bisection of Necklaces
- The Chromatic Number of Kneser Hypergraphs
Cited in
(96)- Necklace bisection with one cut less than needed
- Paintshop, odd cycles and necklace splitting
- A probabilistic spatial distribution model for wire faults in parallel network-on-chip links
- Resource-monotonicity and population-monotonicity in connected cake-cutting
- Computing solutions of the paintshop-necklace problem
- Note on a conjecture of Sierksma
- Consensus-halving via theorems of Borsuk-Ulam and Tucker
- Approximating fair division with a limited number of cuts
- On the computability of equitable divisions
- Two's company, three's a crowd: consensus-halving for a constant number of agents
- Almost envy-freeness for groups: improved bounds via discrepancy theory
- Upper bounds for the necklace folding problems
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- Vanishing of all equivariant obstructions and the mapping degree
- Fair division of mixed divisible and indivisible goods
- Democratic fair allocation of indivisible goods
- Fair cake-cutting among families
- Dold's theorem from viewpoint of strong compatibility graphs
- Computing a small agreeable set of indivisible items
- Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem
- Combinatorial necklace splitting
- Fair splitting of colored paths
- Existence of a simple and equitable fair division: a short proof
- Splitting multidimensional necklaces
- On the Lazarev-Lieb extension of the Hobby-Rice theorem
- Simplotopal maps and necklace splitting
- Convex equipartitions: the spicy chicken theorem
- The Borsuk--Ulam-property, Tucker-property and constructive proofs in combinatorics
- Measure partitions using hyperplanes with fixed directions
- Discrete geometry on colored point sets in the plane -- a survey
- Obstacles for splitting multidimensional necklaces
- Witt vectors. I
- Discrete splittings of the necklace
- Bisection of Circle Colorings
- Splitting multidimensional necklaces and measurable colorings of Euclidean spaces
- On the Placement of a Number of Strings in a Collection of Hats
- Splitting necklaces and measurable colorings of the real line
- The Chromatic Number of Kneser Hypergraphs
- Stiefel manifolds and coloring the pentagon
- scientific article; zbMATH DE number 496046 (Why is no real title available?)
- Fair representation by independent sets
- Thieves can make sandwiches
- Fair division and generalizations of Sperner- and KKM-type results
- The Borsuk-Ulam Theorem and Bisection of Necklaces
- Illumination complexes, -zonotopes, and the polyhedral curtain theorem
- scientific article; zbMATH DE number 927064 (Why is no real title available?)
- Splitting necklaces, with constraints
- Hardness results for consensus-halving
- A nonlinear Lazarev-Lieb theorem: \(L^2\)-orthogonality via motion planning
- A survey of mass partitions
- Dynamic fair resource division
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- scientific article; zbMATH DE number 7561747 (Why is no real title available?)
- On a method of obtaining an approximate solution of an exact fair division problem
- Splitting loops and necklaces: variants of the square peg problem
- Multilabeled Versions of Sperner's and Fan's Lemmas and Applications
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- Polytopal complexes: maps, chain complexes and necklaces
- Equipartitions of measures in $\mathbb{R}^4$
- Reconstructing Odd Necklaces
- The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
- Shorter Labeling Schemes for Planar Graphs
- Fair Cake Division Under Monotone Likelihood Ratios
- Consensus Halving for Sets of Items
- scientific article; zbMATH DE number 7662165 (Why is no real title available?)
- Consensus-Halving: Does It Ever Get Easier?
- The classes PPA-\(k\): existence from arguments modulo \(k\)
- The classes PPA-\(k\): existence from arguments modulo \(k\)
- Envy-free division via configuration spaces
- Colorful Matchings
- Approximately EFX allocations for indivisible chores
- Random necklaces require fewer cuts
- Improved bounds for the binary paint shop problem
- Online Nash welfare maximization without predictions
- Extensions of cut-and-choose fair division
- Proportional allocations of multi-layered cakes
- A new lower bound for multicolor discrepancy with applications to fair division
- On existence theorems
- Words avoiding tangrams
- Connectedness in weighted consensus division of graphical cakes between two agents
- An FPT algorithm for splitting a necklace among two thieves
- Pure Nash equilibria of weighted picking sequence protocol is WEF1 for two agents
- The chromatic number of Kneser hypergraphs via consensus division
- Weighted EF1 allocations for indivisible chores
- An FPT algorithm for splitting a necklace among two thieves
- Restricted existence and approximation algorithms for PMMS
- The chromatic number of Kneser hypergraphs via consensus division
- Fair division with subjective divisibility
- Connected equitable cake division via Sperner's lemma
- Constant inapproximability for PPA
- One-sided markets with externalities
- Efficient splitting of necklaces
- Fair distribution of bundles
- Unfairly splitting separable necklaces
- Approximating EFX through a new notion of fairness
- Topology and combinatorics of partitions of masses by hyperplanes
This page was built for publication: Splitting necklaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1097280)
