An optimal algorithm for a parallel cutting problem.
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.
- An approximation algorithm for the cutting-sticks problem
- Building fences straight and high: an optimal algorithm for finding the maximum length you can cut \(k\) times from given sticks
- A fast algorithm for cutting a rectangle into equal rectangular pieces
- scientific article; zbMATH DE number 1179834
- scientific article; zbMATH DE number 3934748
- An algorithm for the determination of optimal cutting patterns
- Building fences straight and high: an optimal algorithm for finding the maximum length you can cut \(k\) times from given sticks
- Chop vectors and the lattice of integer partitions
- An approximation algorithm for the cutting-sticks problem
- Cutting bamboo down to size
This page was built for publication: An optimal algorithm for a parallel cutting problem.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2715973)
