Approximate Min-Sum Subset Convolution
<|reference_start|>Approximate Min-Sum Subset Convolution: 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.<|reference_end|>
@article{stoian2024approximate,
    title={Approximate Min-Sum Subset Convolution},
    author={Mihail Stoian},
    journal={arXiv preprint arXiv:2404.11364},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.11364},
    primaryClass={cs.DS}
}