Improved lower bounds for the online bin stretching problem |
| |
| Authors: | Michaël Gabay Nadia Brauner Vladimir Kotov |
| |
| Institution: | 1.Univ. Grenoble Alpes, CNRS, G-SCOP,Grenoble,France;2.FPMI DMA Department,Belarusian State University,Minsk,Belarus |
| |
| Abstract: | We use game theory techniques to automatically compute improved lower bounds 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 technique and show that it can be generalized to compute lower bounds for any online or semi-online packing or scheduling problem. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
