Skip to Main content Skip to Navigation
Journal articles

Improved lower bounds for the online bin stretching problem

Michaël Gabay 1 Nadia Brauner 1 Vladimir Kotov 2
1 G-SCOP_ROSP - Recherche Opérationnelle pour les Systèmes de Production
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
2 Department of Applied Mathematics and Computer Science [Minsk]
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.
Keywords : Online algorithms Scheduling Bin stretching Lower bounds
Document type :
Journal articles
Complete list of metadata
https://hal.inria.fr/hal-01379894
Contributor : Nadia Brauner <>
Submitted on : Wednesday, October 12, 2016 - 9:34:28 AM
Last modification on : Tuesday, May 11, 2021 - 11:37:19 AM

Links full text

openaccess

Identifiers

Collections

UGA | G-SCOP | CNRS | PERSYVAL-LAB | G-SCOP_OSP_ROSP

Citation

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

445

 

Contact                    Legal Notice                    Personal Data