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.