Output details
11 - Computer Science and Informatics
University of Leicester
Return to search
Output 0 of 0 in the submission
Article title
A (5/3+epsilon)-approximation for strip packing
Type
D - Journal article
Title of journal
Computational Geometry
Article number
N/A (online first paper)
Volume number
N/A (online firs
Issue number
0
First page of article
-
ISSN of journal
0925-7721
Year of publication
2013
Number of additional authors
3
Additional information
<12>Strip packing models a large number of real-world applications. As Cote et al. (2013) point out, it is very difficult to solve exactly in practice, with instances of size 20 still remaining unsolved after decades. This motivates the study of approximation algorithms. After two SICOMP papers in 1980, there was a series of improvements in the approximation ratio. We reduce the remaining gap to the lower bound by more than 60%. The fact that such a large improvement was possible at a relatively late stage is surprising and may rekindle interest in this problem. Appears in WADS'11 special issue.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
0
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
