A lemma and a conjecture on the cost of rearrangements (Q2504906)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A lemma and a conjecture on the cost of rearrangements |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A lemma and a conjecture on the cost of rearrangements |
scientific article |
Statements
A lemma and a conjecture on the cost of rearrangements (English)
0 references
1 February 2007
0 references
Given a line of books, which are either of black cover or of white cover, what is the minimum cost of sorting them out using transpositions (of blocks) so that books of the same color are put one after another? The lemma referred to in the title is the main result of this paper and states that the cost is at least logarithmic under certain assumptions on the configuration of books. Two (not one but closely related) conjectures are formulated for a continuous version of the problem.
0 references
