Approximate Min-Sum Subset Convolution
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913462796419072 |
|---|---|
| author | Stoian, Mihail |
| author_facet | Stoian, Mihail |
| contents | Exponential-time approximation has recently gained attention as a practical way to deal with the bitter NP-hardness of well-known optimization problems. We study for the first time the $(1 + \varepsilon)$-approximate min-sum subset convolution. This enables exponential-time $(1 + \varepsilon)$-approximation schemes for problems such as minimum-cost $k$-coloring, the prize-collecting Steiner tree, and many others in computational biology. Technically, we present both a weakly- and strongly-polynomial approximation algorithm for this convolution, running in time $\widetilde O(2^n \log M / \varepsilon)$ and $\widetilde O(2^\frac{3n}{2} / \sqrt{\varepsilon})$, respectively. Our work revives research on tropical subset convolutions after nearly two decades. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_11364 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximate Min-Sum Subset Convolution Stoian, Mihail Data Structures and Algorithms Exponential-time approximation has recently gained attention as a practical way to deal with the bitter NP-hardness of well-known optimization problems. We study for the first time the $(1 + \varepsilon)$-approximate min-sum subset convolution. This enables exponential-time $(1 + \varepsilon)$-approximation schemes for problems such as minimum-cost $k$-coloring, the prize-collecting Steiner tree, and many others in computational biology. Technically, we present both a weakly- and strongly-polynomial approximation algorithm for this convolution, running in time $\widetilde O(2^n \log M / \varepsilon)$ and $\widetilde O(2^\frac{3n}{2} / \sqrt{\varepsilon})$, respectively. Our work revives research on tropical subset convolutions after nearly two decades. |
| title | Approximate Min-Sum Subset Convolution |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.11364 |