An approximation algorithm for the cutting-sticks problem

DOI10.1016/J.IPL.2014.09.007zbMATH Open1302.68321OpenAlexW2032912512MaRDI QIDQ477614FDOQ477614

Authors: Jagadish M 

Publication date: 9 December 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2014.09.007

Recommendations

• An optimal algorithm for a parallel cutting problem.
• A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths
• Building fences straight and high: an optimal algorithm for finding the maximum length you can cut \(k\) times from given sticks
• A near-optimal solution to a two-dimensional cutting stock problem
• The two-dimensional cutting stock problem revisited

zbMATH Keywords

approximation algorithmscutting-sticks problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial aspects of partitions of integers (05A17)

Cites Work

• On the Problem of Partitioning {1, 2, � , n} into Subsets having Equal Sums

Cited In (3)

• Building fences straight and high: an optimal algorithm for finding the maximum length you can cut \(k\) times from given sticks
• An optimal algorithm for a parallel cutting problem.
• On the Placement of a Number of Strings in a Collection of Hats

This page was built for publication: An approximation algorithm for the cutting-sticks problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477614)