Prize-Collecting Forest with Submodular Penalties: Improved Approximation
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_ | 1866910916211113984 |
|---|---|
| author | Ahmadi, Ali Gholami, Iman Hajiaghayi, MohammadTaghi Jabbarzade, Peyman Mahdavi, Mohammad |
| author_facet | Ahmadi, Ali Gholami, Iman Hajiaghayi, MohammadTaghi Jabbarzade, Peyman Mahdavi, Mohammad |
| contents | Constrained forest problems form a class of graph problems where specific connectivity requirements for certain cuts within the graph must be satisfied by selecting the minimum-cost set of edges. The prize-collecting version of these problems introduces flexibility by allowing penalties to be paid to ignore some connectivity requirements.
Goemans and Williamson introduced a general technique and developed a 2-approximation algorithm for constrained forest problems. Further, Sharma, Swamy, and Williamson extended this work by developing a 2.54-approximation algorithm for the prize-collecting version of these problems. Motivated by the generality of their framework, which includes problems such as Steiner trees, Steiner forests, and their variants, we pursued further exploration.
We present a significant improvement by achieving a 2-approximation algorithm for this general model, matching the approximation factor of the constrained forest problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_15445 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Prize-Collecting Forest with Submodular Penalties: Improved Approximation Ahmadi, Ali Gholami, Iman Hajiaghayi, MohammadTaghi Jabbarzade, Peyman Mahdavi, Mohammad Data Structures and Algorithms Constrained forest problems form a class of graph problems where specific connectivity requirements for certain cuts within the graph must be satisfied by selecting the minimum-cost set of edges. The prize-collecting version of these problems introduces flexibility by allowing penalties to be paid to ignore some connectivity requirements. Goemans and Williamson introduced a general technique and developed a 2-approximation algorithm for constrained forest problems. Further, Sharma, Swamy, and Williamson extended this work by developing a 2.54-approximation algorithm for the prize-collecting version of these problems. Motivated by the generality of their framework, which includes problems such as Steiner trees, Steiner forests, and their variants, we pursued further exploration. We present a significant improvement by achieving a 2-approximation algorithm for this general model, matching the approximation factor of the constrained forest problems. |
| title | Prize-Collecting Forest with Submodular Penalties: Improved Approximation |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.15445 |