Computational bounds on randomized algorithms for online bin stretching
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913368478056448 |
|---|---|
| author | Lhomme, Antoine Catusse, Nicolas Brauner, Nadia |
| author_facet | Lhomme, Antoine Catusse, Nicolas Brauner, Nadia |
| contents | A frequently studied performance measure in online optimization is competitive analysis. It corresponds to the worst-case ratio, over all possible inputs of an algorithm, between the performance of the algorithm and the optimal offline performance. However, this analysis may be too pessimistic to give valuable insight on a problem. Several workarounds exist, such as randomized algorithms. This paper aims to propose computational methods to construct randomized algorithms and to bound their performance on the classical online bin stretching problem. A game theory method is adapted to construct lower bounds on the performance of randomized online algorithms via linear programming. Another computational method is then proposed to construct randomized algorithms which perform better than the best deterministic algorithms known. Finally, another lower bound method for a restricted class of randomized algorithm for this problem is proposed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_19071 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computational bounds on randomized algorithms for online bin stretching Lhomme, Antoine Catusse, Nicolas Brauner, Nadia Optimization and Control Computer Science and Game Theory A frequently studied performance measure in online optimization is competitive analysis. It corresponds to the worst-case ratio, over all possible inputs of an algorithm, between the performance of the algorithm and the optimal offline performance. However, this analysis may be too pessimistic to give valuable insight on a problem. Several workarounds exist, such as randomized algorithms. This paper aims to propose computational methods to construct randomized algorithms and to bound their performance on the classical online bin stretching problem. A game theory method is adapted to construct lower bounds on the performance of randomized online algorithms via linear programming. Another computational method is then proposed to construct randomized algorithms which perform better than the best deterministic algorithms known. Finally, another lower bound method for a restricted class of randomized algorithm for this problem is proposed. |
| title | Computational bounds on randomized algorithms for online bin stretching |
| topic | Optimization and Control Computer Science and Game Theory |
| url | https://arxiv.org/abs/2405.19071 |