A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917048975622144 |
|---|---|
| author | Chevalier, Baptiste Yamaguchi, Shimpei Roga, Wojciech Takeoka, Masahiro |
| author_facet | Chevalier, Baptiste Yamaguchi, Shimpei Roga, Wojciech Takeoka, Masahiro |
| contents | In this paper, we present the Monte-Carlo Compressive Optimization algorithm, a new method to solve a combinatorial optimization problem that is assumed compressible. The method relies on random queries to the objective function in order to estimate generalized moments. Next, a greedy algorithm from compressive sensing is repurposed to find the global optimum when not overfitting to samples. We provide numerical results giving evidences that our methods overcome state-of-the-art dual annealing. Moreover, we also give theoretical justification of the algorithm success and analyze its properties. The practicality of our algorithm is enhanced by the ability to tune heuristic parameters to available computational resources. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_24755 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization Chevalier, Baptiste Yamaguchi, Shimpei Roga, Wojciech Takeoka, Masahiro Optimization and Control Quantum Physics In this paper, we present the Monte-Carlo Compressive Optimization algorithm, a new method to solve a combinatorial optimization problem that is assumed compressible. The method relies on random queries to the objective function in order to estimate generalized moments. Next, a greedy algorithm from compressive sensing is repurposed to find the global optimum when not overfitting to samples. We provide numerical results giving evidences that our methods overcome state-of-the-art dual annealing. Moreover, we also give theoretical justification of the algorithm success and analyze its properties. The practicality of our algorithm is enhanced by the ability to tune heuristic parameters to available computational resources. |
| title | A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization |
| topic | Optimization and Control Quantum Physics |
| url | https://arxiv.org/abs/2510.24755 |