Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

Improved lower bounds for the online bin stretching problem

Abstract : We use game theory techniques to automatically compute improved lowerbounds on the competitive ratio for the bin stretching problem. Using these techniques,we improve the best lower bound for this problem to 19/14. We explain the techniqueand show that it can be generalized to compute lower bounds for any online or semi-online packing or scheduling problem.
Document type :
Journal articles
Complete list of metadata
Contributor : Nadia Brauner Connect in order to contact the contributor
Submitted on : Wednesday, October 12, 2016 - 9:34:28 AM
Last modification on : Tuesday, May 11, 2021 - 11:37:19 AM

Links full text




Michaël Gabay, Nadia Brauner, Vladimir Kotov. Improved lower bounds for the online bin stretching problem. 4OR: A Quarterly Journal of Operations Research, Springer Verlag, 2017, 15 (2), pp.183-199. ⟨10.1007/s10288-016-0330-2⟩. ⟨hal-01379894⟩



Record views