Approximate Min-Sum Subset Convolution

Abstract

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+\epsilon )$-approximate min-sum subset convolution. This enables exponential-time $(1+\epsilon )$-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 $\tilde{O}(2^n\log M/\epsilon )$ and $\tilde{O}(2^{\frac{3n}{2}}/\sqrt{\epsilon })$, respectively. Our work revives research on tropical subset convolutions after nearly two decades.

To appear at WAOA 2024; updates: shorter title, motivation in abstract, minor typos; original results unchanged