Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.00075 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |