An optimal algorithm for a parallel cutting problem.
type: Item
instance of: scholarly article
zbMATH Open document ID: 1064.05146
author: J. Ginsburg
author: Bill Sands
publication date: 2005-07-20T00:00:00Z
Mathematics Subject Classification ID: 05D99
Mathematics Subject Classification ID: 05A17
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 1600945
zbMATH Keywords: celery
zbMATH Keywords: knife
zbMATH Keywords: cake cutting
zbMATH Keywords: minimum number of cuts
zbMATH Keywords: integer partition
MaRDI profile type: MaRDI publication profile
title: An optimal algorithm for a parallel cutting problem.
published in: Ars Combinatoria
review text: Several sticks of celery with various integer lengths are to be cut into pieces of unit length by a knife that can cut at most \(w\) sticks at a time. What is the minimum number of cuts to do it and by what procedure it can be achieved? The authors prove that the following algorithm is optimal: at each stage cut the \(w\) longest sticks (or all sticks longer than 1 if there are fewer than \(w\) of them) in half or as nearly in half as possible. Example: \(w=3\) and the sticks are \(9,6\). One obtains \(5,4,3^2\) by cut one, \(3^2,2^4,1\) by cut two, \(2^5,1^5\) by cut three, \(2^2, 1^{11}\) by cut four, and \(1^{15}\) by cut five.
reviewed by: Martin Klazar
description: scientific article; zbMATH DE number 1600945