A lemma and a conjecture on the cost of rearrangements (Q2504906)
From MaRDI portal
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
