Improved lower bounds for the online bin stretching problem

Michaël Gabay 1 Nadia Brauner 1 Vladimir Kotov 2
1 G-SCOP_ROSP - ROSP
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
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.
Type de document :
Article dans une revue
4OR: A Quarterly Journal of Operations Research, Springer Verlag, 2017, 15 (2), pp.183-199. 〈10.1007/s10288-016-0330-2〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01379894
Contributeur : Nadia Brauner <>
Soumis le : mercredi 12 octobre 2016 - 09:34:28
Dernière modification le : lundi 9 avril 2018 - 09:34:01

Identifiants

Collections

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〉

Partager

Métriques

Consultations de la notice

144