Back to Search
Start Over
Approximate algorithms to pack rectangles into several strips.
- Source :
- Discrete Mathematics & Applications; 2006, Vol. 16 Issue 1, p73-85, 13p, 4 Diagrams
- Publication Year :
- 2006
-
Abstract
- We consider a problem to pack rectangles into several semi-infinite strips of certain widths. We suggest two simply realised online algorithms, that is, algorithms which pack rectangles just at the moments of their arrivals. It is shown that the accuracy of the former algorithm cannot be approximated by any absolute constant. The latter algorithm guarantees a constant multiplicative accuracy, and the obtained estimate of the multiplicative accuracy is unimprovable. The research was supported by the Russian Foundation for Basic Research, grant 05–01–00798. [ABSTRACT FROM AUTHOR]
- Subjects :
- ALGORITHMS
RECTANGLES
ALGEBRA
MATHEMATICS
RESEARCH
Subjects
Details
- Language :
- English
- ISSN :
- 09249265
- Volume :
- 16
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Discrete Mathematics & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 20197622
- Full Text :
- https://doi.org/10.1515/156939206776241264