Computing Lower Bounds for Online Optimization Problems: Application to the 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
2 Department of Applied Mathematics and Computer Science [Minsk]

We use game theory techniques to automatically compute improved lower bounds on the competitive ratio for the bin stretching problem. Using these techniques, we raise the best lower bound for this problem to 19/14. We explain the technique and show that it can be generalized to compute lower bounds for any online or semi-online packing or scheduling problem. We also present a first lower bound, with value 7/6, on the expected competitive ratio of randomized algorithms for the bin stretching problem.

Mots clés: Bin Stretching; Online Algorithms; Competitive Analysis; Lower Bounds

Domaines: Recherche opérationnelle [math.OC]

Michaël Gabay, Nadia Brauner, Vladimir Kotov. Computing Lower Bounds for Online Optimization Problems: Application to the Bin~Stretching Problem. 2013. ⟨hal-00921663v1⟩