The optimal absolute ratio for online bin packing
- Submitting institution
-
The University of Leicester
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 1402
- Type
- E - Conference contribution
- DOI
-
10.1137/1.9781611973730.94
- Title of conference / published proceedings
- Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015
- First page
- 1425
- Volume
- 2015-January
- Issue
- January
- ISSN
- -
- Open access status
- -
- Month of publication
- December
- Year of publication
- 2014
- URL
-
-
- Supplementary information
-
https://doi.org/10.1137/1.9781611973730.94
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
4
- Research group(s)
-
-
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Bin packing is one of the most fundamental problems in online and approximation algorithms. Although it has been widely studied since the early 1970s, the question about the best possible absolute competitive ratio for online bin packing had been unresolved for over 40 years. This paper settles the question by presenting a 5/3-competitive algorithm, matching the known lower bound. The significance of the result is acknowledged e.g. in a review of bin packing and cutting stock problems by Delorme et al. (EJOR 255(1):1-20, 2016) who write that this paper "closed a long standing open issue on on-line bin packing".
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -