A survey on combinatorial optimization
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913487809150976 |
|---|---|
| author | Le, Phuong |
| author_facet | Le, Phuong |
| contents | This survey revisits classical combinatorial optimization algorithms and extends them to two-stage stochastic models, particularly focusing on client-element problems. We reformulate these problems to optimize element selection under uncertainty and present two key sampling algorithms: SSA and Boost-and-Sample, highlighting their performance guarantees. Additionally, we explore correlation-robust optimization, introducing the concept of the correlation gap, which enables approximations using independent distributions with minimal accuracy loss. This survey analyzes and presents foundational combinatorial optimization methods for researchers at the intersection of this field and reinforcement learning. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_00075 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A survey on combinatorial optimization Le, Phuong Optimization and Control This survey revisits classical combinatorial optimization algorithms and extends them to two-stage stochastic models, particularly focusing on client-element problems. We reformulate these problems to optimize element selection under uncertainty and present two key sampling algorithms: SSA and Boost-and-Sample, highlighting their performance guarantees. Additionally, we explore correlation-robust optimization, introducing the concept of the correlation gap, which enables approximations using independent distributions with minimal accuracy loss. This survey analyzes and presents foundational combinatorial optimization methods for researchers at the intersection of this field and reinforcement learning. |
| title | A survey on combinatorial optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2409.00075 |