University of Technology Nuremberg, Germany and
https://stoianmihail.github.iomihail.stoian@utn.dehttps://orcid.org/0000-0002-8843-3374
Mihail Stoian <ccs2012> <concept>
<concept_id>10003752.10003809.10011254.10011258</concept_id>
<concept_desc>Theory of computation Dynamic programming</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10003752.10003809.10003636</concept_id> <concept_desc>Theory of
computation Approximation algorithms analysis</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>
[500]Theory of computation Dynamic programming [500]Theory of computation
Approximation algorithms analysis

###### Acknowledgements.

The author thanks Petru Pascu, Radu Vintan, and Altan Birler for their
valuable feedback and insights.

# Sinking an Algorithmic Isthmus: $(1+\varepsilon)$-Approximate Min-Sum Subset
Convolution

Mihail Stoian

###### Abstract

Given functions $f$ and $g$ defined on the subset lattice of order $n$, their
_min-sum_ subset convolution, defined for all $S\subseteq[n]$ as

$(f\star g)(S)=\min_{T\subseteq S}\>\big{(}f(T)+g(S\setminus T)\big{)},$

lies at the heart of several NP-hard optimization problems, such as minimum-
cost $k$-coloring, the prize-collecting Steiner tree, and many others in
computational biology. Despite its importance, its naïve $O(3^{n})$-time
evaluation remains the fastest known, the other alternative being an
$\widetilde{O}(2^{n}M)$-time algorithm for instances where the input functions
have a bounded integer range $\\{-M,\ldots,M\\}$.

We study for the first time the $(1+\varepsilon)$-approximate min-sum subset
convolution and present both a weakly- and strongly-polynomial approximation
algorithm, running in time $\widetilde{O}(2^{n}\log M/\varepsilon)$ and
$\widetilde{O}(2^{\frac{3n}{2}}/\sqrt{\varepsilon})$, respectively. To
demonstrate the applicability of our work, we present the first exponential-
time $(1+\varepsilon)$-approximation schemes for the above optimization
problems.

Our algorithms lie at the intersection of two lines of research that have been
so far considered separately: _sequence_ and _subset_ convolutions in semi-
rings. We also extend the recent framework of Bringmann, Künnemann, and
Węgrzycki [STOC 2019] to the context of subset convolutions.

###### keywords:

subset convolution, min-plus convolution, min-max convolution, dynamic
programming, approximation algorithm

###### category:

##  1 Introduction

Fast subset convolution is one of the tools in parameterized algorithms which
made their way in many of the dynamic programming solutions to well-known NP-
hard problems [13]. Given functions $f$ and $g$ defined on the subset lattice
of order $n$, their _sum-product_ subset convolution is defined for all
$S\subseteq[n]\vcentcolon=\\{1,\ldots,n\\}$ as

$h(S)=(f\ast g)(S)=\displaystyle\sum_{T\subseteq S}f(T)g(S\setminus T).$

Its prominence does not yet come to a surprise since many computationally hard
problems accept a convolution-like shape. The remarkable reduction in time-
complexity from $O(3^{n})$ to $O(2^{n}n^{2})$ by Björklund et al. [4]
represented indeed a breakthrough, allowing these problems to be solved
faster. These problems, however, do indeed reduce to a slightly different
subset convolution, namely the _min-sum_ subset convolution, defined for all
$S\subseteq[n]$ as

$h(S)=(f\star g)(S)=\min_{T\subseteq S}\big{(}f(T)+g(S\setminus T)\big{)}.$
(1)

The naïve algorithm inherently takes $O(3^{n})$-time, as in the case of any
subset convolution: For each set $S$, iterate over all its subsets $T$.111The
running time can be derived from $\sum_{k=0}^{n}{n\choose
k}2^{k}=(1+2)^{n}=3^{n}$. In contrast to the speed-up achieved by Björklund et
al. [4] for the sum-product subset convolution, the naïve algorithm is still
the fastest known for the min-sum subset convolution. This is also the reason
why min-sum subset convolution is not used “as is”, but in a two-step
approach: (i) embed the min-sum semi-ring into the sum-product ring, (ii)
perform the fast subset convolution in this ring instead [4].

This workaround has two limitations: First, the input functions must have a
bounded integer range $\\{-M,\ldots,M\\}$ (for the algorithm to have any
practicality), and second, the running time of the final algorithm will
include a factor depending on $M$, making the algorithm a pseudo-polynomial
one.222Note that the input size itself is on the order of $O(2^{n})$. This is
also where the story behind the min-sum subset convolution ends. Is that all?
In what follows, we argue that there is more to it.

###  1.1 Approximating Min-Sum Subset Convolution

In this light, we propose the $(1+\varepsilon)$-_approximate_ variant of the
min-sum subset convolution, namely: Compute the set function $\widetilde{h}$
such that for all $S\subseteq[n]$ the following holds:

$(f\star g)(S)\leq\widetilde{h}(S)\leq(1+\varepsilon)(f\star g)(S).$

If we could devise a faster-than-naïve algorithm for the approximate
counterpart, this would enable $(1+\varepsilon)$-approximation schemes for a
plethora of computationally hard problems that use min-sum subset convolution
as a primitive. Typically, these are problems on graphs such as the minimum
Steiner tree problem [17], coloring [40], and spanning problems on hypergraphs
[48, 39]. On the application side, min-sum subset convolution and its
counterpart, _max-sum_ subset convolution,333The operations are performed in
the $(\max,+)$-semi-ring. are also present in computational biology [44, 42].
This leads us to our driving research question:

> Are there faster-than-naïve $(1+\varepsilon)$-approximation algorithms for
> min-sum subset convolution?

On another note, Björklund et al. [4] showed that, assuming a bounded input,
one can improve on decades-old stagnant results. The most notable of these was
the $\widetilde{O}(2^{k}n^{2}M+nm\log M)$-time algorithm for the minimum
Steiner tree in graphs with $n$ vertices, $k$ terminals, and $m$ edges with
integer weights bounded by $M$. This is indeed the case for all other hard
problems that reduce to the min-sum subset convolution: They are all
“scapegoats” of the bounded-input assumption, having to accept an additional
factor of $M$ in their time-complexities. This leads us to our next question:

> Are there faster-than-naïve $(1+\varepsilon)$-approximation schemes for
> convolution-like NP-hard optimization problems with running time independent
> of M?

Next, we present our results.

###  1.2 Our results

Overview. We answer our driving questions in the affirmative. The way we
answer them is also intriguing in itself. Let us review it briefly. First, we
bring together two lines of research that have been so far considered
separately:  _sequence_ and _subset_ convolutions in semi-rings. This gives us
both the weakly- and the strongly-polynomial algorithms for the
$(1+\varepsilon)$-approximate min-sum subset convolution. Then, using these
algorithms and a standard approximation technique, we obtain
$(1+\varepsilon)$-approximation algorithms for several convolution-like NP-
hard optimization problems. Our strongly-polynomial algorithm for the
$(1+\varepsilon)$ min-sum subset convolution thus serves for running times
independent of $M$.

Min-Sum Subset Convolution. We revive the line of research on min-sum subset
convolution after nearly two decades, by presenting both a weakly- and a
strongly-polynomial $(1+\varepsilon)$-approximation algorithm for this
problem:

######  Theorem 1.1.

$(1+\varepsilon)$-Approximate min-sum subset convolution can be solved in
$\widetilde{O}(2^{n}\log M/\varepsilon)$-time.

######  Theorem 1.2.

$(1+\varepsilon)$-Approximate min-sum subset convolution can be solved in
$\widetilde{O}(2^{\frac{3n}{2}}/\sqrt{\varepsilon})$-time.

Note that the strongly-polynomial algorithm (Thm. 1.2) outperforms its weakly-
polynomial counterpart (Thm. 1.1) for huge co-domains.444Indeed, a sufficient
condition is $M=\omega(2^{\sqrt{\varepsilon 2^{n+\delta}}})$, for any
$\delta>0$. While our weakly-polynomial algorithm uses the scaling technique,
as does the fastest algorithm for the $(1+\varepsilon)$-approximate min-plus
_sequence_ convolution [37], obtaining the strongly-polynomial algorithm
requires a detour in another semi-ring. Namely, in the course of proving it,
we had to design an algorithm for a more curious convolution, namely the _min-
max_ subset convolution, defined for all $S\subseteq[n]$ as

$h(S)=(f\mathbin{\mathchoice{\ooalign{$\displaystyle\vbox{\hbox{\scalebox{0.82}{$\displaystyle\bigcirc$}}}$\cr$\displaystyle\vee$\cr}}{\ooalign{$\textstyle\vbox{\hbox{\scalebox{0.82}{$\textstyle\bigcirc$}}}$\cr$\textstyle\vee$\cr}}{\ooalign{$\scriptstyle\vbox{\hbox{\scalebox{0.82}{$\scriptstyle\bigcirc$}}}$\cr$\scriptstyle\vee$\cr}}{\ooalign{$\scriptscriptstyle\vbox{\hbox{\scalebox{0.82}{$\scriptscriptstyle\bigcirc$}}}$\cr$\scriptscriptstyle\vee$\cr}}}g)(S)=\min_{T\subseteq
S}\max\\{f(S),g(S\setminus T)\\}.$

To the best of our knowledge, the _min-max_ subset convolution has not yet
been present in the literature. As a by-product, we show that its exact
evaluation does indeed break the natural $O(3^{n})$-time barrier:

Reference | Type | (Semi-)ring | Running Time
---|---|---|---
ad-hoc | exact | any | $O(3^{n})$
Björklund et al. [4] | exact | $(+,\times)$ | $O(2^{n}n^{2})$
Björklund et al. [4] | exact | $(\min,+)$ | $\widetilde{O}(2^{n}M)$
Thm. 1.3, _this work_ | exact | $(\min,\max)$ | $\widetilde{O}(2^{\frac{3n}{2}})$
Thm. 1.1, _this work_ |  $(1+\varepsilon)$-approx. | $(\min,+)$ | $\widetilde{O}(2^{n}\log M/\varepsilon)$
Thm. 1.2, _this work_ |  $(1+\varepsilon)$-approx. | $(\min,+)$ | $\widetilde{O}(2^{\frac{3n}{2}}/\sqrt{\varepsilon})$

Table 1: Reviving research on subset convolutions on _semi-rings_ after nearly
two decades.

######  Theorem 1.3.

Exact min-max subset convolution can be solved in
$\widetilde{O}(2^{\frac{3n}{2}})$-time.

This generalizes Kosaraju’s algorithm [33] for the min-max sequence
convolution to the subset lattice. We need this intermediate result so that we
can instantiate the recent framework of Bringmann, Künnemann, and Węgrzycki
[10], used to obtain the first strongly-polynomial algorithm for the
$(1+\varepsilon)$-approximate min-plus sequence convolution. In particular,
they also showed the equivalence between exact min-max sequence convolution
and the latter.555In the current version of the paper, [10, Thm. 8.2] contains
a typo, namely relating the min-plus sequence convolution to the min-max
_product_ , defined for matrices. The theorem actually refers to convolution,
as can be seen from its proof. We show that this result naturally holds in the
subset setting as well:

######  Theorem 1.4 (Extension of [10, Thm. 1.5]).

For any $c\geq 1$, if one of the following statements is true, then both are:

  * •

$(1+\varepsilon)$-Approximate min-sum subset convolution can be solved in time
$\widetilde{O}(2^{cn}/\mathrm{polylog}(\varepsilon))$,

  * •

Exact min-max subset convolution can be solved in time
$\widetilde{O}(2^{cn})$.

Simply using the main backbone of their framework, the Sum-to-Max-Covering
lemma [10, Thm. 1.7] (we define it later in Sec. 4), one could obtain an
$\widetilde{O}(2^{\frac{3n}{2}}/\varepsilon)$-time algorithm for the
approximate min-sum subset convolution; note that the running time is
independent of $M$. However, the dependence on the parameter $\varepsilon$ can
be indeed improved using a refined analysis. Namely, the same authors
presented an improved approximation algorithm for the min-plus sequence
convolution. We obtain Thm. 1.2 by adapting its analysis to the subset
setting.

In Table 1 we summarize our results, which revive the research on subset
convolutions after nearly two decades and enable out-of-the-box exponential-
time $(1+\varepsilon)$-approximation schemes for several hard optimization
problems, as outlined in the following.

Applications. Min-sum subset convolution is present in the dynamic programming
formulation of many NP-hard optimization problems. Thus, we obtain
$(1+\varepsilon)$-approximation schemes for these problems as well, such as
the minimum-cost $k$-coloring [15], the prize-collecting Steiner tree, and two
applications in computational biology: the maximum colorful subtree problem
[42], which instead requires the _max-sum_ subset convolution, for which we
devise an $(1-\varepsilon)$-approximation scheme, and a problem on protein
interaction networks [44] (already proposed as an application by Björklund et
al. [4]). We outline two of these results here:

######  Theorem 1.5.

$(1+\varepsilon)$-Approximate minimum-cost $k$-coloring can be solved in
$\widetilde{O}(2^{\frac{3n}{2}}/\sqrt{\varepsilon})$-time.

######  Theorem 1.6.

$(1+\varepsilon)$-Approximate prize-collecting Steiner tree can be solved in
$\widetilde{O}(2^{\frac{3s^{+}}{2}}/\sqrt{\varepsilon})$-time.666The parameter
$s^{+}$ is the number of proper potential terminals; see Appendix C.1 for its
definition.

###  1.3 Related Work

Our work builds a new bridge from sequence convolutions to subset
convolutions. The sequence convolution in the $(\oplus,\otimes)$-semi-ring of
two sequences $a$ and $b$ is computed as $c_{k}=\oplus_{i+j=k}\>(a_{i}\otimes
b_{j})$, while the subset convolution of two set functions $f$ and $g$ in the
same semi-ring is defined as $h(S)=\oplus_{T\subseteq S}\big{(}f(T)\otimes
g(S\setminus T)\big{)}$. Independently on the structure of the convolution,
i.e., either on sequences or on subsets, there are three types of sequence
convolution which predominate in the literature, corresponding to three
different (semi-)rings: (a) $(+,\times)$-ring, (b) $(\min,\max)$-semi-ring,
and (c) $(\min,+)$-semi-ring, respectively. In the following, we outline
previous work for both convolution types.

Sequence Convolution.

  1. (a)

The sequence convolution in the $(+,\times)$-ring can be solved in time
$O(n\log n)$ via FFT.

  2. (b)

In the $(\min,\max)$-semi-ring, Kosaraju presented an
$\widetilde{O}(n\sqrt{n})$-time algorithm [33], and even conjectured that his
algorithm can be improved to $\widetilde{O}(n)$. However, no improvement has
been reported so far [10].

  3. (c)

Whether Min-Plus Sequence Convolution can be computed in time
$O(n^{2-\delta})$ for any $\delta>0$ is still an open problem [16, 34]. The
fastest algorithm to date runs in time $O(n^{2}/2^{\Omega(\sqrt{\log n})})$,
by combining the reduction to Min-Plus Matrix Product by Bremner et al. [9]
and an algorithm for the latter due to Williams [50], subsequently
derandomized by Chan and Williams [12]. In case the values are bounded by a
constant $W$, the convolution can be performed in $\widetilde{O}(nW)$-time
[49, Lemma 5.7.2]. The first $(1+\varepsilon)$-approximation algorithm has
been presented by Backurs et al. [2], as an application for the Tree Sparsity
problem. Their algorithm runs in time $O(\frac{n}{\varepsilon^{2}}\log
n\log^{2}W)$ and has been improved to
$O(\frac{n}{\varepsilon}\log(n/\varepsilon)\log W)$ [37]. Bringmann et al.
[10] finally provided a strongly-polynomial algorithm, i.e., independent of
$W$, in time $\widetilde{O}(n^{3/2}/\sqrt{\varepsilon})$. Their result is
indeed more general, obtaining a framework that can also be applied to All-
Pairs Shortest Pairs (APSP). In this paper, we extend their framework to the
context of subset convolutions, with immediate application in
$(1+\varepsilon)$-approximation schemes of several convolution-like NP-hard
problems.

Subset Convolution.

  1. (a)

Prior to the work of Björklund et al. [4], the best algorithm for any subset
convolution was the straightforward $O(3^{n})$-time evaluation. They provided
an $O(2^{n}n^{2})$-time algorithm for the subset convolution in the
$(+,\times)$-ring, by relating the FFT to the Möbius transform on the subset
lattice. This result found applications in many problems, among them the
Domatic Number and the Chromatic Number (and many others) in
$2^{n}n^{O(1)}$-time [5].

  2. (b)

As far as the $(\min,\max)$-semi-ring is concerned, there is, to our best
knowledge, no algorithm that runs in time better than $O(3^{n})$. In this
paper, we provide such an algorithm, as a by-product.

  3. (c)

On the other hand, the convolution in the $(\min,+)$-semi-ring received more
attention, as it is implicitly present in many hard optimization problems, a
prominent example being the minimum Steiner tree. While so far no
$o(3^{n})$-time algorithm is known to exist for this convolution, a simple
embedding technique can leverage the speed-up obtained for the sum-product
subset convolution. The caveat is that the input values are required to be
bounded by a constant $M$. In this case, the convolution runs in time
$\widetilde{O}(2^{n}M)$ [4] (compare to the $\widetilde{O}(nW)$-time algorithm
for the corresponding sequence convolution). In particular, no
$(1+\varepsilon)$-approximation algorithm has been known until our work.

We provide in Appendix A the definitions of the convolutions we will be
discussing.

###  1.4 Organization

We organize the paper as follows: We begin with the exact algorithm for the
_min-max_ subset convolution (Sec. 3). Subsequently, in Sec. 4, we introduce
our weakly-polynomial algorithm and then present a simple strongly-polynomial
approximation algorithm for the min-sum subset convolution. This serves the
equivalence between the exact _min-max_ subset convolution and the approximate
_min-sum_ subset convolution, using the simple algorithm for the former. Then,
we outline an improved strongly-polynomial approximation scheme for _min-sum_
subset convolution, adapting that of Bringmann et al. [10] to subset setting.
Based on the improved variant, we introduce in Sec. 5 the first
$(1+\varepsilon)$-approximation scheme for the minimum cost $k$-coloring
problem (we outline many other applications in Appendix C). We conclude in
Sec. 6 with several cases that have been considered for the min-plus sequence
convolution, but are completely missing in the subset setting.

##  2 Preliminaries

Notation. We use $\widetilde{O}$-notation to suppress poly-logarithmic factors
in the input size and in $\varepsilon$, but never in $M$ (or in $W$ in the
sequence setting). We denote by $[n]$ the set $\\{1,\ldots,n\\}$ for $n$ a
natural number. To be consistent with the notation used in previous work in
_both_ research fields, we refer to the $(\min,+)$-semi-ring as _min-sum_ for
subset convolutions and as _min-plus_ for sequence convolutions. The same
distinction is done between the terms $M$ and $W$, corresponding to the
largest (finite) input value in the subset and sequence setting, respectively.
We refer to the $(+,\times)$-ring as the sum-product ring, and to the
$(\min,\max)$-semi-ring as the min-max semi-ring. We will later need Iverson’s
bracket notation: Given a property $P$, $[P]$ takes the value $1$ whenever $P$
is true and $0$ otherwise.

Machine Model and Input Format. We follow the same setup as assumed by
Bringmann et al. [10], namely: The input numbers in _approximate_ problems are
represented in floating-point, whereas those in _exact_ problems are integers
in the usual bit representation. This particular setup is needed when
extending the equivalence between exact min-max and approximate min-plus to
the subset setting. To economically use the space for the actual applications,
we postpone the details on the setup to our Appendix F.

##  3 Exact Min-Max Subset Convolution

Both our strongly-polynomial algorithms for evaluating the
$(1+\varepsilon)$-approximate _min-sum_ subset convolution heavily rely on the
_min-max_ subset convolution, defined for all $S\subseteq[n]$ as

$h(S)=(f\mathbin{\mathchoice{\ooalign{$\displaystyle\vbox{\hbox{\scalebox{0.82}{$\displaystyle\bigcirc$}}}$\cr$\displaystyle\vee$\cr}}{\ooalign{$\textstyle\vbox{\hbox{\scalebox{0.82}{$\textstyle\bigcirc$}}}$\cr$\textstyle\vee$\cr}}{\ooalign{$\scriptstyle\vbox{\hbox{\scalebox{0.82}{$\scriptstyle\bigcirc$}}}$\cr$\scriptstyle\vee$\cr}}{\ooalign{$\scriptscriptstyle\vbox{\hbox{\scalebox{0.82}{$\scriptscriptstyle\bigcirc$}}}$\cr$\scriptscriptstyle\vee$\cr}}}g)(S)=\min_{T\subseteq
S}\max\\{f(S),g(S\setminus T)\\}.$ (2)

In this section, we provide an $\widetilde{O}(2^{\frac{3n}{2}})$-time
algorithm for Eq. (2), inspired by Kosaraju’s $\widetilde{O}(n\sqrt{n})$-time
algorithm for min-max _sequence_ convolution [33]. We note that similar
techniques to Kosaraju’s have been considered for the min-max matrix product
by Shapira et al. [45], Williams et al. [47], and Duan and Pettie [18], as
applications to the all-pairs bottleneck pairs problem.

######  Theorem 1.3.

Exact min-max subset convolution can be solved in
$\widetilde{O}(2^{\frac{3n}{2}})$-time.

######  Proof 3.1.

We closely follow Kosaraju’s algorithm for the min-max _sequence_ convolution
[33]: First, we collect all values of $f$ and $g$ in a list and sort it. We
then divide the sorted list into $O(\sqrt{2^{n}})$ chunks. Let
$\mathcal{C}_{i}$ be the current chunk. We apply fast (boolean) subset
convolution on $[f\leq\max\mathcal{C}_{i}]$ and $[g\leq\max\mathcal{C}_{i}]$
and obtain $\hat{h}=[f\leq\max\mathcal{C}_{i}]\ast[g\leq\max\mathcal{C}_{i}]$.
In particular, $\hat{h}\equiv[h\leq\max\mathcal{C}_{i}]$, and thus a non-zero
$\hat{h}(S)$ tells us whether the actual $h(S)$ is bounded above by
$\max\mathcal{C}_{i}$. At this point, we only need to figure out what the
_actual_ value of $h(S)$ is.

To this end, we consider only those sets $S$ for which $\mathcal{C}_{i}$ is
the _first_ chunk that made $\hat{h}(S)$ positive. Let us call this set
$\mathcal{S}_{i}$. We then consider each $S\in\mathcal{S}_{i}$ separately and
compute its exact $h(S)$ value by iterating the $O(\sqrt{2^{n}})$ sets
$U\in\mathcal{C}_{i}$. Formally, we set

$h(S)=\min_{\vbox{\Let@\restore@math@cr\default@tag\halign{\hfil$\m@th\scriptstyle#$&$\m@th\scriptstyle{}#$\hfil\cr
U&\in\mathcal{C}_{i}\\\ U&\subseteq S\crcr}}}\big{(}f(U)+g(S\setminus
U)\big{)}.$ (3)

The correctness follows from construction. Let us analyze the running time.
Sorting the list takes $\widetilde{O}(2^{n})$-time. Then, it takes
$O(|\mathcal{S}_{i}|\sqrt{2^{n}})$-time to evaluate Eq. (3) for each chunk
$\mathcal{C}_{i}$, since $|\mathcal{C}_{i}|=O(\sqrt{2^{n}})$ by construction.
Since we run $O(\sqrt{2^{n}})$ convolutions in the sum-product ring and Eq.
(3) is run only once per $S\subseteq[n]$, the total running time reads
$O(2^{n}n^{2}\sqrt{2^{n}}+2^{n}\sqrt{2^{n}})=\widetilde{O}(2^{\frac{3n}{2}})$.

Notably, the running time given in Thm. 1.3 is faster than $O(3^{n})$. This
algorithm will serve as the basis for our strongly-polynomial approximation
algorithms for _min-sum_ subset convolution.

##  4 Approximate Min-Sum Subset Convolution

We now turn to our original goal: _approximating the min-sum subset
convolution_. There are two ways to do this, either via a weakly-polynomial
time algorithm or a strongly-polynomial time algorithm. Let us start with the
former.

###  4.1 Weakly-Polynomial Algorithm

Algorithm 1 $\textsc{ApxMinSumSubsetConv}(f,g,\varepsilon)$ [Thm. 1.1] –
Running time: $\widetilde{O}(2^{n}\log M/\varepsilon)$

1:procedure Scale($f,q,\varepsilon$)

2: return $S\mapsto\begin{cases}\big{\lceil}\frac{2f(S)}{\varepsilon
q}\big{\rceil},&\text{if}\;\big{\lceil}\frac{2f(S)}{\varepsilon
q}\big{\rceil}\leq\big{\lceil}\frac{4}{\varepsilon}\big{\rceil},\\\
\infty,&\text{otherwise.}\\\ \end{cases}$

3:end procedure

4:

5:Set $\widetilde{h}(S)\leftarrow\infty$ for all $S\subseteq[n]$

6:for $q=2^{\left\lceil\log{2M}\right\rceil},\ldots,4,2,1$ do

7:
$f_{q},g_{q}\leftarrow\textsc{Scale}(f,q,\varepsilon),\textsc{Scale}(g,q,\varepsilon)$

8: $h_{q}\leftarrow\textsc{ExactMinSumSubsetConv}(f_{q},g_{q})$

9:
$\widetilde{h}(S)\leftarrow\min\\{\widetilde{h}(S),h_{q}(S)\cdot\frac{\varepsilon
q}{2}\\}$ for all $S\subseteq[n]$

10:end for

11:return $\widetilde{h}$

Our weakly-polynomial algorithm is based on the scaling technique, which has
been successfully used in several graph problems [29, 25, 38, 26, 19]. In the
context of sequence convolution, it has been used by Backurs et al. [2] to
provide the first $(1+\varepsilon)$-approximation scheme for the min-plus
sequence convolution, running in time $O(\frac{n}{\varepsilon^{2}}\log
n\log^{2}W)$. This has been later improved by Mucha et al. [37] to
$O(\frac{n}{\varepsilon}\log(n/\varepsilon)\log W)$-time.

We can use a method similar to that in Ref. [37] and solve the
$(1+\varepsilon)$-approximate min-sum subset convolution in weakly-polynomial
time. The key insight is that we can replace the “heart” of their algorithm,
namely using the exact $\widetilde{O}(nW)$-time min-plus sequence convolution
for bounded input, with the subset counterpart running in time
$\widetilde{O}(2^{n}M)$, due to Björklund et al. [4]. To our best knowledge,
this observation had not appeared in the literature before (since the
applications themselves had no $(1+\varepsilon)$ approximation schemes prior
to our work). We outline our algorithm in Alg. 1.

See 1.1 We prove Thm. 1.1 in Appendix B.

Striving for Strongly-Polynomial Time. While the weakly-polynomial algorithm
allows us to reduce the linear dependence on $M$ in the running time of the
algorithm of Björklund et al. [4] to a logarithmic one, the dependence on $M$
still remains. The caveat is that this dependence will carry over in the
actual applications. _Is this the best we can hope for?_ In the following, we
will show that we can _completely_ discard this dependence.

In a recent breakthrough, Bringmann et al. [10] introduced the first strongly-
polynomial algorithm for evaluating the approximate min-plus _sequence_
convolution: Given two sequences $a$ and $b$, their min-plus convolution777In
this work, since we are dealing with two types of convolution, on sequences
and subsets, respectively, we will consistently add the specification
“sequence” to avoid any confusion. In literature on fine-grained complexity,
this is of course always omitted. is a sequence $c$, where $c_{k}=\min_{i\leq
k}\>(a_{i}+b_{k-i})$. As in our case, its approximate variant asks for a
sequence $\widetilde{c}$ such that
$c_{k}\leq\widetilde{c}_{k}\leq(1+\varepsilon)c_{k}$. Notoriously, previous
work on this problem had employed the scaling trick [52], which relies on the
largest input value $W$ and introduces an additional $\log W$ into the running
time.888As noted above, the term $W$ in the literature on APSP and sequence
convolutions corresponds to $M$ in subset convolutions. The approximate
convolution finds a natural application in the Tree Sparsity problem [11],
where its exact algorithm is prohibitively expensive.

The aforementioned authors asked a fundamental question: _Is it possible to
completely avoid the scaling trick?_ They indeed answered this question
affirmatively, by designing the first _strongly-polynomial_
$(1+\varepsilon)$-approximation schemes for the all-pairs shortest pairs
(APSP) problem and many others, including the min-plus sequence convolution.
Their cornerstone result is the Sum-to-Max-Covering lemma:

######  Lemma 4.1 (Sum-to-Max Covering [10]).

Given vectors $A,B\in\mathbb{R}^{d}_{+}$ and a parameter $\varepsilon>0$,
there are vectors
$A^{(1)},\ldots,A^{(s)},B^{(1)},\ldots,B^{(s)}\in\mathbb{R}^{d}_{+}$ with
$s=O(\frac{1}{\varepsilon}\log\frac{1}{\varepsilon}+\log
d\log\frac{1}{\varepsilon})$ such that for all $i,j\in[d]$:

$A[i]+B[j]\leq\displaystyle\min_{\ell\in[s]}\max\\{A^{(\ell)}[i],B^{(\ell)}[j]\\}\leq(1+\varepsilon)(A[i]+B[j]).$

The vectors $A^{(1)},\ldots,A^{(s)},B^{(1)},\ldots,B^{(s)}$ can be computed in
time $O(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}+d\log
d\log\frac{1}{\varepsilon})$.

The motivation behind their lemma is that min-max sequence convolution can be
solved in $\widetilde{O}(n\sqrt{n})$-time (using Kosaraju’s algorithm [33]),
in contrast to the best-known algorithm for min-plus convolution which runs in
$O(n^{2})$-time. (Indeed, it is an open problem whether this is also the best
that can be achieved [16, 34].) In this light, one can first compute the
auxiliary vectors $A^{(1)},\ldots,A^{(s)},B^{(1)},\ldots,B^{(s)}$ via Lemma
4.1 and then solve the $(1+\varepsilon)$-approximate min-plus sequence
convolution by performing $s$ min-max sequence convolutions.

###  4.2 Simple Strongly-Polynomial Approximation Algorithm

Algorithm 2 $\textsc{ApxMinSumSubsetConv}(f,g,\varepsilon)$ [Lemma 4.2] –
Running time: $\widetilde{O}(2^{\frac{3n}{2}}/\varepsilon)$

1:$\\{f^{(1)},\ldots,f^{(s)},g^{(1)},\ldots,g^{(s)}\\}\leftarrow\textsc{SumToMaxCovering}(f,g,\varepsilon)$
(Lemma 4.1)

2:$h^{(\ell)}\leftarrow\textsc{MinMaxSubsetConv}(f^{(\ell)},g^{(\ell)})$ for
each $\ell\in[s]$

3:$\widetilde{h}(S)\leftarrow\displaystyle\min_{\ell\in[s]}\>\\{h^{(\ell)}[\texttt{idx}(S)]\\}$
for each $S\subseteq[n]$

4:return $\widetilde{h}$

The reader can already see the applicability in our setting: We can apply the
Sum-to-Max Covering lemma in min-sum _subset_ convolution. Indeed, this is the
cornerstone neglected by Bringmann et al. [10]. This key insight is the
building block behind the new results in Sec. 5.

######  Lemma 4.2.

$(1+\varepsilon)$-Approximate min-sum subset convolution can be solved in time
$\widetilde{O}(2^{\frac{3n}{2}}/\varepsilon)$.

######  Proof 4.3.

To apply the Sum-to-Max-Covering lemma, we view the set functions $f$ and $g$,
defined on the subset lattice of order $n$, as vectors in
$\mathbb{R}^{2^{n}}_{+}$. Indeed, the coordinate of a set $S\subseteq[n]$ is
its implicit binary representation. This yields the vectors
$f^{(1)},\ldots,f^{(s)},g^{(1)},\ldots,g^{(s)}\in\mathbb{R}^{2^{n}}_{+}$, with
$s=O(\frac{1}{\varepsilon}\log\frac{1}{\varepsilon}+n\log\frac{1}{\varepsilon})$.
Then, for each $\ell\in[s]$, we perform the _exact_ min-max subset convolution
of $f^{(\ell)}$ and $g^{(\ell)}$. At this point, we do a remark that has also
been done by Bringmann et al. [10]: We first need to replace the entries of
$f^{(\ell)}$ and $g^{(\ell)}$ by their ranks, respectively, since min-max
subset convolution requires, as in the case of Kosaraju’s algorithm, standard
bit representation of integers. Once
$h^{(\ell)}=f^{(\ell)}\mathbin{\mathchoice{\ooalign{$\displaystyle\vbox{\hbox{\scalebox{0.82}{$\displaystyle\bigcirc$}}}$\cr$\displaystyle\vee$\cr}}{\ooalign{$\textstyle\vbox{\hbox{\scalebox{0.82}{$\textstyle\bigcirc$}}}$\cr$\textstyle\vee$\cr}}{\ooalign{$\scriptstyle\vbox{\hbox{\scalebox{0.82}{$\scriptstyle\bigcirc$}}}$\cr$\scriptstyle\vee$\cr}}{\ooalign{$\scriptscriptstyle\vbox{\hbox{\scalebox{0.82}{$\scriptscriptstyle\bigcirc$}}}$\cr$\scriptscriptstyle\vee$\cr}}}g^{(\ell)}$
has been computed, we can take the entry-wise minimum over $\ell\in[s]$, as
outlined in Alg. 2; we use $\texttt{idx}(S)$ to denote the binary
representation of the set $S$, using it to obtain the corresponding coordinate
in an $2^{n}$-dimensional vector.

The total running time accumulates to
$\widetilde{O}(s2^{\frac{3n}{2}})=\widetilde{O}(2^{\frac{3n}{2}}/\varepsilon)$,
since the construction of the auxiliary vectors takes linear time in the
output size.999Precisely, the construction of the auxiliary vectors takes time
$O(\frac{2^{n}}{\varepsilon}\log\frac{1}{\varepsilon}+2^{n}n\log\frac{1}{\varepsilon})$.

Note that Lemma 4.2 is still an intermediate result. In the following, we will
use it to prove the equivalence between exact min-max subset convolution and
approximate min-sum subset convolution. This represents the extension of the
same result at the level of sequence convolutions. We will prove Thm. 1.4 in
Appendix D.1. See 1.4

###  4.3 Improved Strongly-Polynomial Approximation Algorithm

We used the $\widetilde{O}(2^{\frac{3n}{2}}/\varepsilon)$-time algorithm for
the approximate min-sum subset convolution (Lemma 4.2) as a basis for the
equivalence between _approximate_ min-sum subset convolution and _exact_ min-
max subset convolution. In the following, we design an algorithm with an
improved running time of $\widetilde{O}(2^{\frac{3n}{2}}/\sqrt{\varepsilon})$.
Our key insight is that the new algorithm can be analyzed using a toolbox
similar to that of Bringmann et al. [10]. This will be the running time we use
for the applications in Sec. 5 and Appendix C.

We split the main result in the corresponding subcases, namely (i) _distant_
summands and (ii) _close_ summands. The main theorem, Thm. 1.2, will follow
from these.

Algorithm 3 $\textsc{DistantConv}(f,g,\varepsilon)$ [Lemma 4.4]

1:$\\{f^{(1)},\ldots,f^{(s)},g^{(1)},\ldots,g^{(s)}\\}=\textsc{DistantCovering}(f,g,\frac{\varepsilon}{4})$
(see [10, Cor. 5.10])

2:$h^{(\ell)}\leftarrow\textsc{MinMaxSubsetConv}(f^{(\ell)},g^{(\ell)})$ for
any $\ell\in[s]$

3:$\widetilde{h}(S)\leftarrow\frac{1}{1-\varepsilon/2}\cdot\displaystyle\min_{\ell\in[s]}\>\\{h^{(\ell)}[\texttt{idx}(S)]\\}$
for all $S\subseteq[n]$

4:return $\widetilde{h}$

######  Lemma 4.4.

Given set functions $f,g$ on the subset lattice of order $n$ and a parameter
$\varepsilon>0$, let $h=f\star g$ be their min-sum subset convolution. We can
compute in time
$O(2^{\frac{3n}{2}}\mathrm{polylog}(\frac{2^{n}}{\varepsilon}))$ a set
function $\widetilde{h}$ such that for any $S\subseteq[n]$ we have

  1. (i)

$h(S)\leq\widetilde{h}(S)$, and

  2. (ii)

if there is $T\subseteq S$ with $h(S)=f(T)+g(S\setminus T)$ and
$\frac{f(T)}{g(S\setminus
T)}\not\in[\frac{\varepsilon}{4},\frac{4}{\varepsilon}]$, then
$\widetilde{h}(S)\leq(1+\varepsilon)h(S)$.

In Appendix E.1, we show that Alg. 3 returns such an $\widetilde{h}$. Briefly,
we view the set functions $f,g$ as vectors in $\mathbb{R}^{2^{n}}_{+}$. Hence,
we can use Distant Covering from the framework [10, Cor. 5.10] on $f,g$ with
$\varepsilon^{\prime}\vcentcolon=\frac{\varepsilon}{4}$ and obtain
$f^{(1)},\ldots,f^{(s)},g^{(1)},\ldots,g^{(s)}$ with
$s=O\left(\mathrm{polylog}(\frac{2^{n}}{\varepsilon})\right)$.101010For
completeness, we provide [10, Cor. 5.10] as Lemma E.1 in Appendix E.1. For
each $l\in[s]$, we compute
$h^{(l)}=f^{(l)}\mathbin{\mathchoice{\ooalign{$\displaystyle\vbox{\hbox{\scalebox{0.82}{$\displaystyle\bigcirc$}}}$\cr$\displaystyle\vee$\cr}}{\ooalign{$\textstyle\vbox{\hbox{\scalebox{0.82}{$\textstyle\bigcirc$}}}$\cr$\textstyle\vee$\cr}}{\ooalign{$\scriptstyle\vbox{\hbox{\scalebox{0.82}{$\scriptstyle\bigcirc$}}}$\cr$\scriptstyle\vee$\cr}}{\ooalign{$\scriptscriptstyle\vbox{\hbox{\scalebox{0.82}{$\scriptscriptstyle\bigcirc$}}}$\cr$\scriptscriptstyle\vee$\cr}}}g^{(l)}$
and scale the entry-wise minimum by $\frac{1}{1-2\varepsilon^{\prime}}$.

The case of _close_ summands is covered by the following result:

Algorithm 4 $\textsc{CloseConv}(f,g,\varepsilon)$ [Lemma 4.5]

1:procedure Scale($f,q,\varepsilon$)

2: return $S\mapsto\begin{cases}\big{\lceil}\frac{4}{\varepsilon q}\cdot
f(S)\big{\rceil},&\text{if}\;\frac{\varepsilon q}{16}\leq f(S)\leq q,\\\
\infty,&\text{otherwise.}\\\ \end{cases}$

3:end procedure

4:

5:Set $\widetilde{h}(S)\leftarrow\infty$ for all $S\subseteq[n]$

6:for $q\in\\{1,2,4,\ldots,2^{\left\lceil\log{2M}\right\rceil}\\}$ do

7:
$f_{q},g_{q}\leftarrow\textsc{Scale}(f,q,\varepsilon),\textsc{Scale}(g,q,\varepsilon)$

8: $h_{q}\leftarrow\textsc{ExactMinSumSubsetConv}(f_{q},g_{q})$

9:
$\widetilde{h}(S)\leftarrow\min\\{\widetilde{h}(S),h_{q}(S)\cdot\frac{\varepsilon
q}{4}\\}$ for all $S\subseteq[n]$

10:end for

11:return $\widetilde{h}$

######  Lemma 4.5.

Given set functions $f,g$ on the subset lattice of order $n$ and a parameter
$\varepsilon>0$, let $h=f\star g$ be their min-sum subset convolution. We can
compute in time $\widetilde{O}(2^{\frac{3n}{2}}/\sqrt{\varepsilon})$ a set
function $\widetilde{h}$ such that for any $S\subseteq[n]$ we have

  1. (i)

$h(S)\leq\widetilde{h}(S)$, and

  2. (ii)

if $T\subseteq S$ with $h(S)=f(T)+g(S\setminus T)$ and
$\frac{f(T)}{g(S\setminus
T)}\in[\frac{\varepsilon}{4},\frac{4}{\varepsilon}]$, then
$\widetilde{h}(S)\leq(1+\varepsilon)h(S)$.

In Appendix D.3, we show that Alg. 4 returns such an $\widetilde{h}$. We point
out one aspect that a careful reader will notice, namely that the for-loop at
line 6 (Alg. 4) does indeed use the largest value $M$. At first glance, this
seems to contradict our assumption that we are trying to avoid running times
that include $M$. The key insight to understanding this, used by Bringmann et
al. [10] in the sequence setting, is the fact that $q$ grows geometrically,
and thus the number of entries of $f_{q}$ and $g_{q}$ that are not set to
$\infty$ by Scale is bounded by $O(2^{n}\log\frac{1}{\varepsilon})$, as we
analyze in the proof of Lemma 4.5.

Algorithm 5 $\textsc{ApxMinSumSubsetConv}(f,g,\varepsilon)$ [Thm. 1.2] –
Running time: $\widetilde{O}(2^{\frac{3n}{2}}/\sqrt{\varepsilon})$

1:$\widetilde{h}_{1}\leftarrow\textsc{DistantConv}(f,g,\varepsilon)$

2:$\widetilde{h}_{2}\leftarrow\textsc{CloseConv}(f,g,\varepsilon)$

3:$\widetilde{h}(S)\leftarrow\min\\{\widetilde{h}_{1}(S),\widetilde{h}_{2}(S)\\}$
for all $S\subseteq[n]$

4:Return $\widetilde{h}$

See 1.2

######  Proof 4.6.

We run both algorithms for the distant and close summands and take the entry-
wise minimum. Correctness and running time follow from those of Lemmas 4.4 and
4.5.

##  5 Applications

Armed with the novel strongly-polynomial algorithm for
$(1+\varepsilon)$-approximate min-sum subset convolution running in time
$\widetilde{O}(2^{\frac{3n}{2}}/\sqrt{\varepsilon})$, we can now develop
$(1+\varepsilon)$-approximation schemes111111Or
$(1-\varepsilon)$-approximation schemes where the _max-sum_ subset convolution
is applicable. for a plethora of convolution-like NP-hard optimization
problems. In particular, we target all problems that are “scapegoats” of the
approach employing min-sum subset convolution on bounded input. In other
words, these are all exact algorithms with a dependence on $M$ in their
running time. Our goal is to enable out-of-the-box
$(1+\varepsilon)$-approximation schemes in time
$\widetilde{O}(2^{\frac{3p}{2}}/\sqrt{\varepsilon})$, where $p$ is problem-
specific (as a rule of thumb, it is always the exponent in the running time
$O(3^{p})$ of the exact evaluation). The following problem is intended to
demonstrate this technique.

###  5.1 Minimum-Cost $k$-Coloring

In their book on parameterized algorithms, Cygan et al. [15] propose a variant
of $k$-coloring, which they entitle minimum-cost $k$-coloring, and devise an
$\widetilde{O}(2^{n}M)$-time algorithm for it [14, Thm. 10.18]. We are given
an undirected graph $G$, an integer $k$, and a cost function
$c:V(G)\times[k]\to\\{-M,\ldots,M\\}$. The cost of a coloring
$\chi:V(G)\to[k]$ is defined as $\displaystyle\sum_{v\in V(G)}c(v,\chi(v))$,
i.e., coloring vertex $v$ with color $i$ incurs cost $c(v,i)$. The task is to
determine the minimum cost of a $k$-coloring of $G$ (if such a coloring
exists). To this end, it is handy to introduce a function
$s_{i}:2^{V(G)}\to\mathbb{Z}\cup\\{+\infty\\}$ such that for every $X\subseteq
V(G)$ we have

$s_{i}(X)=\begin{cases}\displaystyle\sum_{x\in X}c(x,i),&\text{if }X\text{ is
an independent set,}\\\ +\infty,&\text{otherwise.}\end{cases}$

Then, one can compute the minimum cost of a $k$-coloring of $G[X]$ as
$(s_{1}\star\ldots\star s_{k})(X)$. This reduces to simply performing $k-1$
min-sum subset convolutions. To this end, the algorithm they propose runs in
$\widetilde{O}(2^{n}M)$-time, by applying the standard min-sum subset
convolution for bounded input. We show how to obtain an
$(1+\varepsilon)$-approximation in
$\widetilde{O}(2^{\frac{3n}{2}}/\sqrt{\varepsilon})$-time; the running time is
independent of $M$.

######  Theorem 5.1.

If $(1+\varepsilon)$-Approximate min-sum subset convolution runs in
$T(n,\varepsilon)$-time, then an $(1+\varepsilon)$-approximate minimum-cost
$k$-coloring can be found in time $O(T(n,\frac{\varepsilon}{k-1}))$.

######  Proof 5.2.

Consider the evaluation of the min-sum subset convolution between two set
functions $f$ and $g$ at each step. Setting a relative error $\delta>0$ for
each convolution call, we obtain a cumulative relative error bounded by
$(1+\delta)^{k-1}$. By setting $\delta=\Theta(\frac{\varepsilon}{k-1})$, we
obtain a relative error of at most $\varepsilon$.

######  Corollary 5.3.

$(1+\varepsilon)$-Approximate Minimum-Cost $k$-Coloring can be solved in
$\widetilde{O}(2^{\frac{3n}{2}}/\sqrt{\varepsilon})$-time.

The corollary proves Thm. 1.5. Referring to Ref. [20, 32], Fomin et al. [23]
point out that if certain reasonable complexity conjectures hold, then
$k$-coloring itself is hard to approximate within $n^{1-\epsilon}$, for any
$\epsilon>0$. It is interesting to ask whether our time bound is optimal for
the $(1+\varepsilon)$-approximation. We leave this as future work.

Other Applications. We provide an extensive section on many other
applications, such as the prize-collecting Steiner tree and two other
applications in computational biology, in Appendix C.

##  6 Further Sinking the Algorithmic “Isthmus”

There seemed to be an unyielding “isthmus” between the results on sequence
convolutions and subset convolutions on semi-rings. This is also due to the
natural difference in the complexity classes they lie in. We argue that the
min-sum subset convolution has been neglected so far, given that the min-plus
_sequence_ convolution has seen a steadily increasing line of research in the
last decade:

Polynomial Speed-ups. Currently, the fastest known algorithm for min-plus
sequence convolution runs in time $O(n^{2}/2^{\Omega(\sqrt{\log n})})$, by
combining the reduction to Min-Plus Matrix Product by Bremner et al. [9] and
an algorithm for the latter due to Williams [50], subsequently derandomized by
Chan and Williams [12]. This has been the culmination of a long line of
research starting with the $O(n^{2}/\log n)$-time algorithm due to Bremner et
al. [9]. This leads us to ask whether such speed-ups can be generalized to the
subset context as well:

> Are there polynomial-factor speed-ups for the min-sum subset convolution?

In particular, we are not aware of any $O(3^{n}/n)$-time algorithm.

Min-Sum Subset Convolution Conjecture. The lack of faster algorithms for this
problem leads us to conjecture that a similar scenario as in the case of the
min-plus sequence convolution [16, 34] is also present in subset convolutions:

######  Conjecture 6.1.

There is no $O((3-\delta)^{n}\mathrm{polylog}(M))$-time exact algorithm for
min-sum subset convolution, with $\delta>0$.

Indeed, an interesting direction for future work is to find out whether both
conjectures are equivalent.

## References

  * [1] Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Howard Karloff.  Improved approximation algorithms for prize-collecting steiner tree and tsp.  SIAM Journal on Computing, 40(2):309–332, 2011.  arXiv:https://doi.org/10.1137/090771429, doi:10.1137/090771429.
  * [2] Arturs Backurs, Piotr Indyk, and Ludwig Schmidt.  Better approximations for tree sparsity in nearly-linear time.  In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2215–2229. SIAM, 2017.  doi:10.1137/1.9781611974782.145.
  * [3] Daniel Bienstock, Michel X. Goemans, David Simchi-Levi, and David Williamson.  A note on the prize collecting traveling salesman problem.  Mathematical Programming, 59(1):413–420, Mar 1993.  doi:10.1007/BF01581256.
  * [4] Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto.  Fourier meets möbius: Fast subset convolution.  In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, page 67–74, New York, NY, USA, 2007. Association for Computing Machinery.  doi:10.1145/1250790.1250801.
  * [5] Andreas Björklund, Thore Husfeldt, and Mikko Koivisto.  Set partitioning via inclusion-exclusion.  SIAM J. Comput., 39(2):546–563, 2009.  doi:10.1137/070683933.
  * [6] Jannis Blauth, Nathan Klein, and Martin Nägele.  A better-than-1.6-approximation for prize-collecting tsp, 2023.  arXiv:2308.06254.
  * [7] Jannis Blauth and Martin Nägele.  An improved approximation guarantee for prize-collecting tsp.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 1848–1861, New York, NY, USA, 2023. Association for Computing Machinery.  doi:10.1145/3564246.3585159.
  * [8] Sebastian Böcker and Florian Rasche.  Towards de novo identification of metabolites by analyzing tandem mass spectra.  In Christian Huber, Oliver Kohlbacher, Michal Linial, Katrin Marcus, and Knut Reinert, editors, Computational Proteomics, volume 8101 of Dagstuhl Seminar Proceedings (DagSemProc), pages 1–5, Dagstuhl, Germany, 2008. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08101.2, doi:10.4230/DagSemProc.08101.2.
  * [9] David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, and Perouz Taslakian.  Necklaces, convolutions, and x + y.  In Yossi Azar and Thomas Erlebach, editors, Algorithms – ESA 2006, pages 160–171, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
  * [10] Karl Bringmann, Marvin Künnemann, and Karol Wegrzycki.  Approximating apsp without scaling: Equivalence of approximate min-plus and exact min-max.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 943–954, New York, NY, USA, 2019. Association for Computing Machinery.  doi:10.1145/3313276.3316373.
  * [11] Coralia Cartis and Andrew Thompson.  An exact tree projection algorithm for wavelets.  IEEE Signal Processing Letters, 20(11):1026–1029, 2013.  doi:10.1109/LSP.2013.2278147.
  * [12] Timothy M. Chan and Ryan Williams.  Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky, pages 1246–1255.  URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611974331.ch87, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611974331.ch87, doi:10.1137/1.9781611974331.ch87.
  * [13] Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Algebraic techniques: sieves, convolutions, and polynomials, pages 321–355.  Springer International Publishing, Cham, 2015.  doi:10.1007/978-3-319-21275-3_10.
  * [14] Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Algebraic techniques: sieves, convolutions, and polynomials, pages 321–355.  Springer International Publishing, Cham, 2015.  doi:10.1007/978-3-319-21275-3_10.
  * [15] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer Publishing Company, Incorporated, 1st edition, 2015.
  * [16] Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk.  On problems equivalent to (min, +)-convolution.  In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 22:1–22:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.  URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.22, doi:10.4230/LIPICS.ICALP.2017.22.
  * [17] Stuart E Dreyfus and Robert A Wagner.  The steiner problem in graphs.  Networks, 1(3):195–207, 1971.
  * [18] Ran Duan and Seth Pettie.  Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths.  In Claire Mathieu, editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 384–391. SIAM, 2009.  doi:10.1137/1.9781611973068.43.
  * [19] Ran Duan, Seth Pettie, and Hsin-Hao Su.  Scaling algorithms for weighted matching in general graphs.  ACM Trans. Algorithms, 14(1), jan 2018.  doi:10.1145/3155301.
  * [20] Uriel Feige and Joe Kilian.  Zero knowledge and the chromatic number.  In Steven Homer and Jin-Yi Cai, editors, Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, Philadelphia, Pennsylvania, USA, May 24-27, 1996, pages 278–287. IEEE Computer Society, 1996.  doi:10.1109/CCC.1996.507690.
  * [21] Paulo Feofiloff, Cristina G. Fernandes, Carlos Eduardo Ferreira, and José Coelho de Pina.  Primal-dual approximation algorithms for the prize-collecting steiner tree problem.  Inf. Process. Lett., 103(5):195–202, 2007.  URL: https://doi.org/10.1016/j.ipl.2007.03.012, doi:10.1016/J.IPL.2007.03.012.
  * [22] Matteo Fischetti, Markus Leitner, Ivana Ljubić, Martin Luipersbeck, Michele Monaci, Max Resch, Domenico Salvagnin, and Markus Sinnl.  Thinning out steiner trees: a node-based model for uniform edge costs.  Mathematical Programming Computation, 9(2):203–229, Jun 2017.  doi:10.1007/s12532-016-0111-0.
  * [23] Fedor V. Fomin and Dieter Kratsch.  Exact Exponential Algorithms.  Springer-Verlag, Berlin, Heidelberg, 1st edition, 2010.
  * [24] Bernhard Fuchs, Walter Kern, D Molle, Stefan Richter, Peter Rossmanith, and Xinhui Wang.  Dynamic programming for minimum steiner trees.  Theory of Computing Systems, 41:493–500, 2007.
  * [25] Harold N. Gabow.  Scaling algorithms for network problems.  In 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983, pages 248–257. IEEE Computer Society, 1983.  doi:10.1109/SFCS.1983.68.
  * [26] Harold N. Gabow and Robert E. Tarjan.  Faster scaling algorithms for general graph matching problems.  J. ACM, 38(4):815–853, oct 1991.  doi:10.1145/115234.115366.
  * [27] Gerald Gamrath, Thorsten Koch, Stephen J. Maher, Daniel Rehfeldt, and Yuji Shinano.  Scip-jack—a solver for stp and variants with parallelization extensions.  Mathematical Programming Computation, 9(2):231–296, Jun 2017.  doi:10.1007/s12532-016-0114-x.
  * [28] Michel X. Goemans and David P. Williamson.  A general approximation technique for constrained forest problems.  SIAM Journal on Computing, 24(2):296–317, 1995.  arXiv:https://doi.org/10.1137/S0097539793242618, doi:10.1137/S0097539793242618.
  * [29] Andrew V. Goldberg.  Scaling algorithms for the shortest paths problem.  SIAM Journal on Computing, 24(3):494–504, 1995.  arXiv:https://doi.org/10.1137/S0097539792231179, doi:10.1137/S0097539792231179.
  * [30] Juha Harviainen and Mikko Koivisto.  Revisiting bayesian network learning with small vertex cover.  In Robin J. Evans and Ilya Shpitser, editors, Uncertainty in Artificial Intelligence, UAI 2023, July 31 - 4 August 2023, Pittsburgh, PA, USA, volume 216 of Proceedings of Machine Learning Research, pages 819–828. PMLR, 2023.  URL: https://proceedings.mlr.press/v216/harviainen23a.html.
  * [31] David S. Johnson, Maria Minkoff, and Steven Phillips.  The prize collecting steiner tree problem: theory and practice.  In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’00, page 760–769, USA, 2000. Society for Industrial and Applied Mathematics.
  * [32] Subhash Khot and Ashok Kumar Ponnuswami.  Better inapproximability results for maxclique, chromatic number and min-3lin-deletion.  In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, volume 4051 of Lecture Notes in Computer Science, pages 226–237. Springer, 2006.  doi:10.1007/11786986\\_21.
  * [33] S.R. Kosaraju.  Efficient tree pattern matching.  In 30th Annual Symposium on Foundations of Computer Science, pages 178–183, 1989.  doi:10.1109/SFCS.1989.63475.
  * [34] Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider.  On the fine-grained complexity of one-dimensional dynamic programming.  In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 21:1–21:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.  URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.21, doi:10.4230/LIPICS.ICALP.2017.21.
  * [35] Markus Leitner, Ivana Ljubić, Martin Luipersbeck, and Markus Sinnl.  A dual ascent-based branch-and-bound framework for the prize-collecting steiner tree and related problems.  INFORMS J. on Computing, 30(2):402–420, may 2018.  doi:10.1287/ijoc.2017.0788.
  * [36] Ohad Lipsky and Ely Porat.  Approximate pattern matching with the _L_ ${}_{\mbox{1}}$, _L_ ${}_{\mbox{2}}$ and _L_ ${}_{\mbox{{$\infty$}}}$ metrics.  Algorithmica, 60(2):335–348, 2011.  URL: https://doi.org/10.1007/s00453-009-9345-9, doi:10.1007/S00453-009-9345-9.
  * [37] Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk.  A subquadratic approximation scheme for partition.  In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 70–88. SIAM, 2019.  doi:10.1137/1.9781611975482.5.
  * [38] James B. Orlin and Ravindra K. Ahuja.  New scaling algorithms for the assignment and minimum mean cycle problems.  Math. Program., 54:41–56, 1992.  doi:10.1007/BF01586040.
  * [39] Tobias Polzin and Siavash Vahdati Daneshmand.  On steiner trees and minimum spanning trees in hypergraphs.  Oper. Res. Lett., 31(1):12–20, jan 2003.  doi:10.1016/S0167-6377(02)00185-2.
  * [40] Oriana Ponta, Falk Hüffner, and Rolf Niedermeier.  Speeding up dynamic programming for some np-hard graph recoloring problems.  In Manindra Agrawal, Dingzhu Du, Zhenhua Duan, and Angsheng Li, editors, Theory and Applications of Models of Computation, pages 490–501, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
  * [41] Oriana Ponta, Falk Hüffner, and Rolf Niedermeier.  Speeding up dynamic programming for some np-hard graph recoloring problems.  In Manindra Agrawal, Ding-Zhu Du, Zhenhua Duan, and Angsheng Li, editors, Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Xi’an, China, April 25-29, 2008. Proceedings, volume 4978 of Lecture Notes in Computer Science, pages 490–501. Springer, 2008.  doi:10.1007/978-3-540-79228-4\\_43.
  * [42] Imran Rauf, Florian Rasche, François Nicolas, and Sebastian Böcker.  Finding maximum colorful subtrees in practice.  In Benny Chor, editor, Research in Computational Molecular Biology, pages 213–223, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
  * [43] Daniel Rehfeldt and Thorsten Koch.  On the exact solution of prize-collecting steiner tree problems.  INFORMS Journal on Computing, 34(2):872–889, 2022.
  * [44] Jacob Scott, Trey Ideker, Richard M. Karp, and Roded Sharan.  Efficient algorithms for detecting signaling pathways in protein interaction networks.  In Satoru Miyano, Jill Mesirov, Simon Kasif, Sorin Istrail, Pavel A. Pevzner, and Michael Waterman, editors, Research in Computational Molecular Biology, pages 1–13, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
  * [45] Asaf Shapira, Raphael Yuster, and Uri Zwick.  All-pairs bottleneck paths in vertex weighted graphs.  In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’07, page 978–985, USA, 2007. Society for Industrial and Applied Mathematics.
  * [46] Yahui Sun, Marcus Brazil, Doreen A. Thomas, and Saman K. Halgamuge.  The fast heuristic algorithms and post-processing techniques to design large and low-cost communication networks.  IEEE/ACM Trans. Netw., 27(1):375–388, 2019.  doi:10.1109/TNET.2018.2888864.
  * [47] Virginia Vassilevska, Ryan Williams, and Raphael Yuster.  All pairs bottleneck paths and max-min matrix products in truly subcubic time.  Theory Comput., 5(1):173–189, 2009.  URL: https://doi.org/10.4086/toc.2009.v005a009, doi:10.4086/TOC.2009.V005A009.
  * [48] David Michael Warme.  Spanning Trees in Hypergraphs with Applications to Steiner Trees.  PhD thesis, USA, 1998.  AAI9840474.
  * [49] K. Węgrzycki.  Provably Optimal Dynamic Programming.  2019\.  URL: https://books.google.de/books?id=UmYfzwEACAAJ.
  * [50] Ryan Williams.  Faster all-pairs shortest paths via circuit complexity.  In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 664–673, New York, NY, USA, 2014. Association for Computing Machinery.  doi:10.1145/2591796.2591811.
  * [51] Uri Zwick.  All pairs shortest paths in weighted directed graphs – exact and almost exact algorithms.  In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS ’98, page 310, USA, 1998. IEEE Computer Society.
  * [52] Uri Zwick.  All pairs shortest paths using bridging sets and rectangular matrix multiplication.  J. ACM, 49(3):289–317, may 2002.  doi:10.1145/567112.567114.

##  Appendix A Convolution Definitions

Min-Plus Sequence Convolution Input: Sequences
$(a[i])_{i=1}^{n},\,(b[j])_{j=1}^{n}\in\mathbb{R}^{n}_{+}$ Task: Compute
sequence $(c[k])_{k=1}^{n}$ with $a[k]=\displaystyle\min_{i+j=k}(a[i]+b[j])$

Min-Max Sequence Convolution Input: Sequences
$(a[i])_{i=1}^{n},\,(b[j])_{j=1}^{n}\in\mathbb{R}^{n}_{+}$ Task: Compute
sequence $(c[k])_{k=1}^{n}$ with
$c[k]=\displaystyle\min_{i+j=k}\max\\{a[i],b[j]\\}$

Min-Sum Subset Convolution Input: Set functions $f,g$ with
$f(S),g(S)\in\mathbb{R}^{n}_{+}$, for $S\subseteq[n]$ Task: Compute set
function $h$ with $h(S)=\displaystyle\min_{T\subseteq
S}\left(f(T)+g(S\setminus T)\right)$

Min-Max Subset Convolution Input: Set functions $f,g$ with
$f(S),g(S)\in\mathbb{R}^{n}_{+}$, for $S\subseteq[n]$ Task: Compute set
function $h$ with $h(S)=\displaystyle\min_{T\subseteq
S}\max\\{f(T),g(S\setminus T)\\}$

$(1+\varepsilon)$-Approximate Min-Plus Sequence Convolution Input: Sequences
$(a[i])_{i=1}^{n},\,(b[j])_{j=1}^{n}\in\mathbb{R}^{n}_{+}$ Task: Compute a
sequence $(\widetilde{c}[k])_{k=1}^{n}$ with
$c[k]\leq\widetilde{c}[k]\leq(1+\varepsilon)c[k]$ for any $k\in[n]$, where $c$
denotes the output of Min-Plus Sequence Convolution

$(1+\varepsilon)$-Approximate Min-Sum Subset Convolution Input: Set functions
$f,g$ with $f(S),g(S)\in\mathbb{R}^{n}_{+}$, for $S\subseteq[n]$ Task: Compute
a set function $\widetilde{h}$ with
$h(S)\leq\widetilde{h}(S)\leq(1+\varepsilon)h(S)$ for any $S\subseteq[n]$,
where $h$ denotes the output of Min-Sum Subset Convolution

##  Appendix B Weakly-Polynomial Approximation Algorithm

We prove the correctness and analyze the running time of our weakly-polynomial
approximation algorithm for the min-sum subset convolution which uses the
scaling technique. It is an adaptation of the fastest scaling-based
approximation algorithm by Mucha et al. [37] for the min-plus sequence
convolution. To this end, we will use the following lemma, which has been used
by Mucha et al. [37] (see their Lemma 6.2), being inspired by [51, Lemma 5.1]
and [36, Lemma 1]:

######  Lemma B.1 ([37, Lemma 6.2]).

For natural numbers $x,y$, and positive $q,\varepsilon$ satisfying $q\leq x+y$
and $0<\varepsilon<1$ it holds:

$\displaystyle x+y$
$\displaystyle\leq\Big{(}\Big{\lceil}\frac{2x}{q\epsilon}\Big{\rceil}+\Big{\lceil}\frac{2y}{q\epsilon}\Big{\rceil}\Big{)}\frac{q\epsilon}{2}$
$\displaystyle<(x+y)(1+\epsilon),$ $\displaystyle(x+y)(1-\epsilon)$
$\displaystyle<\Big{(}\Big{\lfloor}\frac{2x}{q\epsilon}\Big{\rfloor}+\Big{\lfloor}\frac{2y}{q\epsilon}\Big{\rfloor}\Big{)}\frac{q\epsilon}{2}$
$\displaystyle\leq x+y.$

See 1.1

######  Proof B.2.

To prove the theorem, we can employ similar techniques to the those introduced
by Mucha et al. [37]. The key insight is to replace the exact min-plus
sequence convolution for bounded input with the its subset counterpart.

Let us consider Alg. 1. In each round $q$, we map each value $f(S)$ to
$\big{\lceil}\frac{2f(S)}{\varepsilon q}\big{\rceil}$, if it does not exceed
$\lceil\frac{4}{\varepsilon}\rceil$, where $S\subseteq[n]$; otherwise, it is
set to $\infty$. Then, we run the exact algorithm with the maximum value as
$\lceil\frac{4}{\varepsilon}\rceil$. Once this convolution has been computed,
we obtain the final result, by multiplying the elements by $\frac{\varepsilon
q}{2}$ and updating the minimum in each round.

Let $h(S)=f(T)+g(S\setminus T)$ be the value of the actual min-sum subset
convolution. By construction, there is a round $q$ in which $q\leq h(S)<2q$.
At this point, note that the values $\lceil\frac{2f(T)}{\varepsilon q}\rceil$
and $\lceil\frac{2g(S\setminus T)}{\varepsilon q}\rceil$ are bounded above by
$\lceil\frac{4}{\varepsilon}\rceil$, thus the subset $S$, regarded as an index
in $\tilde{h}$, will be updated. Now consider the previous Lemma B.1: Due to
$q\leq h(S)$, the assumption is satisfied, and thus it holds that the sum lies
between $h(S)$ and $(1+\varepsilon)h(S)$. Since in the following rounds it
still holds that $q\leq h(S)$, any updates at the subset $S$ will remain
valid.

Let us analyze the running time of the algorithm. There are $O(\log M)$
iterations and the exact min-sum subset convolution algorithm runs in
$\widetilde{O}(2^{n}\lceil\frac{4}{\varepsilon}\rceil)$-time. This results in
a total running time of $\widetilde{O}(2^{n}\log M/\varepsilon)$.

##  Appendix C Further Applications

Our extensive list of applications underscores the importance of subset
convolution in semi-rings, and the need for an approximate counterpart to
alleviate the high running times of the exact solutions.

###  C.1 Prize-Collecting Steiner Tree

The Steiner tree problem is one of the well-known NP-hard problems [17]. In
its generalization, the _prize-collecting_ Steiner tree problem (PCSTP), one
penalizes the nodes not included in the chosen tree. Given an undirected graph
$G=(V,E)$ on $n$ vertices, edge weights $c:E\to\mathbb{Q}_{>0}$, and node
weights (or _prizes_) $p:V\to\mathbb{Q}_{>0}$, we search for a tree
$S=(V(S),E(S))\subseteq G$ such that

$C(S):=\displaystyle\sum_{e\in E(S)}c(e)+\displaystyle\sum_{v\in V\setminus
V(S)}p(v)$

is minimized. We note that each Steiner tree instance can be transformed into
a PCSTP instance by setting sufficiently large node weights for the
terminals.121212Recall that for the minimum Steiner tree problem, one enforces
that the tree contains a given set of terminals.

PCSTP was introduced in the 11th DIMACS Challenge (2014), and since then many
solvers have been introduced in the literature pushing the boundaries of what
was possible during the challenge [22, 27, 35, 46]. The first FPT-algorithm
has been recently proposed by Rehfeldt and Koch [43] and runs in time
$\widetilde{O}(3^{s^{+}}n)$, where $s^{+}$ is the number of proper potential
terminals (we will define it later). The problem has witnessed a rich line of
research on approximation algorithms [28, 3, 21, 31, 1, 7], culminating in the
recent 1.599-approximation algorithm due to Blauth et al. [6]. Note that these
approximation algorithms run in polynomial time.

Dynamic Program. The most recent exact algorithm is due to Rehfeldt and Koch
[43] and runs in time $\widetilde{O}(3^{s^{+}})$-time, where $s^{+}$ is the
number of proper potential terminals (see below). Their algorithm resembles
the dynamic program for STP, due to Dreyfus and Wagner [17]. Note that STP
itself has a faster algorithm in $O^{*}(c^{|T|})$-time, for any $c>1$ [24]. As
regards PCSTP, we are not aware of any adaptation of that algorithm to the
prize-collecting setting. To define $s^{+}$, let $T_{p}\vcentcolon=\\{v\in
V\mid p(v)>0\\}$ be the set of _potential terminals_. A terminal $t\in T_{p}$
is _proper_ if

$p(t)>\displaystyle\min_{e\in\delta(\\{t\\})}c(e),$

where $\delta(U):=\big{\\{}\\{u,v\\}\in E\mid u\in U,v\in V\setminus
U\big{\\}}$ for $U\subseteq V$.

Layer-wise Optimization. Rehfeldt and Koch [43] propose to first solve the
rooted variant, RPCSTP, which incorporates the additional constraint that a
non-empty set $T_{f}\subseteq V$, called that of _fixed_ terminals, must be
part of any feasible solution. For this variant, they provide an
$\widetilde{O}(3^{|T_{f}|}n)$-time algorithm. Then, by a transformation from
PCSTP to an equivalent RPCSTP that has no proper potential terminals and
satisfies $|T_{f}|=s^{+}+1$, one can solve the original problem in the same
running time, namely $\widetilde{O}(3^{s+}n)$-time, using a recursion similar
to that of Dreyfus and Wagner for the minimum Steiner tree: Choose and
arbitrary $t_{0}\in T_{f}$, as defined above, and let
$T_{f}^{-}\vcentcolon=T_{f}\setminus\\{t_{0}\\}$. Then, for
$i=2,\ldots,|T_{f}^{-}|$ define the functions $\phi$ and $\gamma$ recursively
as follows [43]:131313The authors denote the functions by $f$ and $g$. We
slightly rename them to avoid any confusion with the functions used in the
actual convolution.

$\displaystyle\phi(T_{i},w)$ $\displaystyle=\displaystyle\min_{T\subsetneq
T_{i}\mid T\neq\varnothing}\>\big{(}\gamma(T,w)+\gamma(T_{i}\setminus
T,w)\big{)}-\displaystyle\sum_{u\in V\setminus\\{w\\}}p(u),$
$\displaystyle\gamma(T_{i},v)$ $\displaystyle=\displaystyle\min_{u\in
V}\>\big{(}\phi(T_{i},u)+d^{\prime}_{pc}(v,u)\big{)},$

with $T_{i}\subseteq T_{f}^{-}$ and $|T_{i}|=i$. The function
$d^{\prime}_{pc}(v,u)$ is the prize-constraint distance between $v$ and $u$.
Since we are only focusing on the _shape_ of the recursion, and the distance
function is not involved in the actual convolution, we refer the reader to
Ref. [43] for more details.

$(1+\varepsilon)$-Approximation. Obtaining the $(1+\varepsilon)$-approximation
scheme is now a simple exercise. Namely, note that $\phi$ is indeed a subset
convolution performed _layer-wise_ based on the cardinality of $T_{i}$. Thus,
there are $s^{+}n$ convolutions performed in total to evaluate
$\gamma(T_{f}^{-},t_{0})$, which stores the value of the optimal solution.
Hence, we can use the same approach as for the previous problem and obtain:

######  Theorem C.1.

If $(1+\varepsilon)$-approximate min-sum subset convolution runs in time
$T(n,\varepsilon)$, then Prize-Collecting Steiner Tree can be
$(1+\varepsilon)$-approximated in
$\widetilde{O}(T(s^{+},\varepsilon/s^{+}n))$-time.

######  Corollary C.2.

$(1+\varepsilon)$-Approximate prize-collecting Steiner tree can be solved in
$\widetilde{O}(2^{\frac{3s^{+}}{2}}/\sqrt{\varepsilon})$-time.

###  C.2 Computational Biology

We outline another application, this time in computational biology, and
briefly touch on another proposed by Björklund et al. [4] in their work on
fast subset convolution. We choose the former because of its intriguing
inapproximability result (see Thm. C.4) and to show an application of _max-
sum_ subset convolution for which we devise a natural
$(1-\varepsilon)$-approximation scheme given our previous results.

Mass Spectrometry. Böcker and Rasche [8] consider the maximum colorful subtree
problem, defined in the following, as an application for the _de novo_
interpretation of metabolite tandem mass spectrometry data.

######  Definition C.3 (Maximum Colorful Subtree).

Given a vertex-colored DAG $G=(V,E)$ with colors $C$ and weights
$w:E\to\mathbb{R}$, find the induced colorful subtree $T=(V_{T},E_{T})$ of $G$
of maximum weight $w(T):=\displaystyle\sum_{e\in e_{T}}w(e)$.

We chose this particular problem due to its intriguing hardness result,
obtained by Rauf et al. [42, Thm. 1]: Consider the relaxation where we drop
the color constraints, resulting in the Maximum Subtree problem. Then,

######  Theorem C.4 ([42, Thm. 1]).

There is no $O(|V|^{1-\delta})$ (polynomial-time) approximation algorithm for
the Phys. Rev. BMaximum Subtree problem for any $\delta>0$, unless P = NP.

Note that the inapproximability result naturally holds for the Maximum
Colorful Subtree as well, since the latter is a generalization of the former.
In this light, Rauf et al. [42] designed an $\widetilde{O}(3^{k}k|E|)$-time
dynamic program, with $k$ the number of colors, as follows. Let $W(v,S)$ be
the maximal score of a colorful tree with root $v$ and color set $S\subseteq
C$. The table $W$ can be computed by the following recursion [42]:

$\displaystyle W(v,S)=\max$ $\displaystyle\displaystyle\max_{u:c(u)\in
S\setminus\\{c(v)\\},vu\in E}\big{(}W(u,S\setminus\\{c(v)\\})+w(v,u)\big{)},$
(4a) $\displaystyle W(v,S)=\max$
$\displaystyle\displaystyle\max_{\begin{subarray}{c}(S_{1},S_{2}):S_{1}\cap
S_{2}=\\{c(v)\\}\\\ S_{1}\cup
S_{2}=S\end{subarray}}\big{(}W(v,S_{1})+W(v,S_{2})\big{)}.$ (4b)

They remark that the running time can be indeed improved to
$O(2^{n}\mathrm{poly}(|V|,k))$, assuming the problem instance enjoys a bounded
input; that is, using the standard embedding technique to embed the
$(\max,+)$-semi-ring into the $(+,\times)$-ring proposed by Björklund et al.
[4].

Note that Eq. (4b) indeed is a max-sum subset convolution. To see why this is
the case, observe that the expression $W(v,S)$ can be computed via _max-sum_
subset convolution by a layer-wise optimization, i.e., evaluate the
convolution for all sets $S$ of a given cardinality (this is indeed a standard
approach undertaken by Björklund et al. [4] to optimize recursive dynamic
programs). To avoid the constraint $S_{1}\cap S_{2}=\\{c(v)\\}$, we can
introduce $S_{1}^{\prime}=S_{1}\setminus\\{c(v)\\}$ and
$S_{2}^{\prime}=S_{2}\setminus\\{c(v)\\}$, with
$S_{1}^{\prime}\>\dot{\cup}\>S_{2}^{\prime}=S-\\{c(v)\\}$, and compute the
subset convolution for $S\setminus\\{c(v)\\}$ instead. Certainly, we also need
to define the function $f$ used in the convolution so that the weights are the
correct ones. Namely, we set $f(X):=W(v,X\cup\\{c(v)\\})$, for any set
$X\subseteq S\setminus\\{c(v)\\}$.

Our strategy developed for the above problems can be applied to this problem
as well, with the only impediment that the convolution is in the
$(\max,+)$-semi-ring. Extending our results to this convolution, however, is a
simple exercise since maximizing any function $\phi$ is the same as minimizing
$-\phi$. There is a small caveat here: the original framework requires that
the values are positive. To ensure this, we simply need to shift $-\phi$ with
the largest value (with a certain epsilon to ensure strict positivity). We
hence obtain:

######  Corollary C.5.

$(1-\varepsilon)$-Approximate max-sum subset convolution can be solved in time
$\widetilde{O}(2^{\frac{3n}{2}}/\sqrt{\varepsilon})$.

Note that the weakly-polynomial approximation algorithm can also be adapted to
work for the max-sum subset convolution (a similar case holds in the sequence
setting [37]). Since the convolution is called at most $O(k|V|)$ times in the
evaluation of the dynamic program, we obtain an
$(1-\varepsilon)$-approximation for our problem:

######  Theorem C.6.

If $(1-\varepsilon)$-Approximate max-sum subset convolution can be solved in
time $T(n,\varepsilon)$, then maximum colorful subtree can be
$(1-\varepsilon)$-approximated in time $O(T(k,\varepsilon/k|V|))$.

######  Corollary C.7.

$(1-\varepsilon)$-Approximate maximum colorful subtree can be solved in
$\widetilde{O}(2^{\frac{3k}{2}}/\sqrt{\varepsilon})$-time.

Protein Interaction Networks. A similar approach can be considered for the
problem of detecting signaling pathways in protein interaction networks [44],
considered for application by Björklund et al. [4]. We briefly mention that
the problem can also be $(1+\varepsilon)$-approximated in time
$\widetilde{O}(2^{\frac{3k}{2}}/\sqrt{\varepsilon})$. We skip the details and
refer the interested reader to Ref. [4].

###  C.3 Supplementary Applications

Skimming through the current citations of the original paper on fast subset
convolution
[4],141414https://scholar.google.com/scholar?cites=18311787326994519594 we
found further applications that implicitly use the
$\widetilde{O}(2^{n}M)$-time algorithm, namely Bayesian network learning [30],
which uses the max-sum subset convolution, and the convex recoloring problem
[41], which uses the min-sum counterpart instead.

##  Appendix D Missing Proofs

In this section, we provide the missing proofs from the main paper.

###  D.1 Equivalence of Exact Min-Max and Approximate Min-Sum

See 1.4

######  Proof D.1.

To prove the theorem, we can employ similar techniques to the those introduced
by Bringmann et al. [10, Thm. 1.5]. Namely, for the second direction, we use
our algorithm from Lemma 4.2, which approximates the min-sum subset
convolution via the exact min-max subset convolution. If $T(n)$ is the running
time of the exact min-max subset convolution, then the approximation algorithm
runs in time $\widetilde{O}(T(n)/\varepsilon)$. For the first direction, let
$h=f\mathbin{\mathchoice{\ooalign{$\displaystyle\vbox{\hbox{\scalebox{0.82}{$\displaystyle\bigcirc$}}}$\cr$\displaystyle\vee$\cr}}{\ooalign{$\textstyle\vbox{\hbox{\scalebox{0.82}{$\textstyle\bigcirc$}}}$\cr$\textstyle\vee$\cr}}{\ooalign{$\scriptstyle\vbox{\hbox{\scalebox{0.82}{$\scriptstyle\bigcirc$}}}$\cr$\scriptstyle\vee$\cr}}{\ooalign{$\scriptscriptstyle\vbox{\hbox{\scalebox{0.82}{$\scriptscriptstyle\bigcirc$}}}$\cr$\scriptscriptstyle\vee$\cr}}}g$
and $t\vcentcolon=\left\lceil 4(1+\varepsilon)^{2}\right\rceil$. Consider the
functions $f^{\prime}$ and $g^{\prime}$ defined as
$f^{\prime}(S)\vcentcolon=t^{f(S)}$ and $g^{\prime}(S)\vcentcolon=t^{g(S)}$
for $S\subseteq[n]$, respectively.151515Since $f(S)$ and $g(S)$ are integers
in the standard bit representation, we can compute $t^{f(S)}$ and $t^{g(S)}$
by simply writing $f(S)$ and $g(S)$, respectively, into the exponent. Let
$h^{\prime}$ be the $(1+\varepsilon)$-approximate min-sum subset convolution
of $f^{\prime}$ and $g^{\prime}$.

######  Claim 1 (cf. [10]).

It holds $t^{h(S)}\leq h^{\prime}(S)\leq t^{h(S)+1/2}$ for all
$S\subseteq[n]$.

Using the above claim (we prove it below), we can compute $h(S)$ as
$\left\lfloor\log_{t}h^{\prime}(S)\right\rfloor$.161616This can be achieved by
simply reading the exponent of $h^{\prime}(S)$. If
$(1+\varepsilon)$-approximate min-sum subset convolution runs in time $T(n)$,
we obtain an algorithm for exact min-max subset convolution that runs in time
$O(2^{n}+T(n))=\widetilde{O}(T(n))$.

Let us prove Claim 1:

See 1

######  Proof D.2.

Recall that
$h=f\mathbin{\mathchoice{\ooalign{$\displaystyle\vbox{\hbox{\scalebox{0.82}{$\displaystyle\bigcirc$}}}$\cr$\displaystyle\vee$\cr}}{\ooalign{$\textstyle\vbox{\hbox{\scalebox{0.82}{$\textstyle\bigcirc$}}}$\cr$\textstyle\vee$\cr}}{\ooalign{$\scriptstyle\vbox{\hbox{\scalebox{0.82}{$\scriptstyle\bigcirc$}}}$\cr$\scriptstyle\vee$\cr}}{\ooalign{$\scriptscriptstyle\vbox{\hbox{\scalebox{0.82}{$\scriptscriptstyle\bigcirc$}}}$\cr$\scriptscriptstyle\vee$\cr}}}g$
and $h^{\prime}$ is the $(1+\varepsilon)$-approximate min-sum subset
convolution of $f^{\prime},g^{\prime}$, defined as
$f^{\prime}(S)\vcentcolon=t^{f(S)},g^{\prime}(S)\vcentcolon=t^{g(S)}$, where
$t\vcentcolon=\left\lceil 4(1+\varepsilon)^{2}\right\rceil$ and
$\varepsilon>0$. We employ the same proof strategy as in [10, Claim 4.1],
originally designed for the APSP problem.

Fix $S\subseteq[n]$ and observe that

$\displaystyle\min_{T\subseteq S}\left(f^{\prime}(T)+g^{\prime}(S\setminus
T)\right)\leq h^{\prime}(S)\leq(1+\varepsilon)\displaystyle\min_{T\subseteq
S}\left(f^{\prime}(T)+g^{\prime}(S\setminus T)\right)$

holds by definition. Furthermore, there exists an $T^{*}$ such that
$h(S)=\max\\{f(T^{*}),g(S\setminus T^{*})\\}$. Thus, we have

$\displaystyle h^{\prime}(S)$
$\displaystyle\leq(1+\varepsilon)(f^{\prime}(T^{*})+g^{\prime}(S\setminus
T^{*})$ $\displaystyle=(1+\varepsilon)(t^{f(T^{*})}+t^{g(S\setminus T^{*})})$
$\displaystyle=2(1+\varepsilon)t^{\max\\{f(T^{*}),g(S\setminus T^{*})\\}}$
$\displaystyle=2(1+\varepsilon)t^{h(S)}$ $\displaystyle\leq
t^{h(S)+1/2},\text{by $t\geq 4(1+\varepsilon)^{2}$},$

proving the upper-bound. To show the lower-bound, observe that there is an
$T\subset S$ with $h^{\prime}(S)\geq f^{\prime}(T)+g^{\prime}(S\setminus T)$.
Hence,

$\displaystyle h^{\prime}(S)$ $\displaystyle\geq
f^{\prime}(T)+g^{\prime}(S\setminus T)$
$\displaystyle=t^{f(T)}+t^{g(S\setminus T)}$ $\displaystyle\geq
t^{\max\\{f(T),g(S\setminus T)\\}}$ $\displaystyle\geq t^{h(S)}.$

###  D.2 Distant Summands Lemma

We provide the full proof of Lemma 4.4, which takes care of the _distant_
summands case.

See 4.4

######  Proof D.3.

To this end, let us consider Alg. 3. We view the set functions $f,g$ as
vectors in $\mathbb{R}^{2^{n}}_{+}$. Hence, we can use Distant Covering from
the framework [10, Cor. 5.10] on $f,g$ with
$\varepsilon^{\prime}\vcentcolon=\frac{\varepsilon}{4}$ and obtain
$f^{(1)},\ldots,f^{(s)},g^{(1)},\ldots,g^{(s)}$ with
$s=O\left(\mathrm{polylog}(\frac{2^{n}}{\varepsilon})\right)$.171717For
completeness, we provide [10, Cor. 5.10] as Lemma E.1 in Appendix E.1. For
each $l\in[s]$, we compute
$h^{(l)}=f^{(l)}\mathbin{\mathchoice{\ooalign{$\displaystyle\vbox{\hbox{\scalebox{0.82}{$\displaystyle\bigcirc$}}}$\cr$\displaystyle\vee$\cr}}{\ooalign{$\textstyle\vbox{\hbox{\scalebox{0.82}{$\textstyle\bigcirc$}}}$\cr$\textstyle\vee$\cr}}{\ooalign{$\scriptstyle\vbox{\hbox{\scalebox{0.82}{$\scriptstyle\bigcirc$}}}$\cr$\scriptstyle\vee$\cr}}{\ooalign{$\scriptscriptstyle\vbox{\hbox{\scalebox{0.82}{$\scriptscriptstyle\bigcirc$}}}$\cr$\scriptscriptstyle\vee$\cr}}}g^{(l)}$
and scale the entry-wise minimum by $\frac{1}{1-2\varepsilon^{\prime}}$. The
scaling factor removes the extra factor $1-2\varepsilon^{\prime}$ from the RHS
of property (i) of [10, Cor. 5.10], yielding $\widetilde{h}(S)\geq h(S)$ for
any $S\subseteq[n]$. Then, using property (ii) of the same corollary, we have
that for any indices $i,j$ with
$\frac{{f}[i]}{{g}[j]}\not\in[\varepsilon^{\prime},\frac{1}{\varepsilon^{\prime}}]=[\frac{\varepsilon}{4},\frac{4}{\varepsilon}]$
there is an $\ell$ such that $h^{(l)}[i+j]\leq{f}[i]+{g}[j]$. Looking at this
from the perspective of subset convolution, we obtain that for any $T\subseteq
S$ with $\frac{f(T)}{g(S\setminus
T)}\not\in[\frac{\varepsilon}{4},\frac{4}{\varepsilon}]$ there is such an
$\ell$ with $h^{(l)}(S)=f(T)+g(S\setminus T)$. Hence, minimizing over all
$\ell$ and scaling by $\frac{1}{1-\varepsilon/2}<1+\varepsilon$ gives the
second property of our lemma.

The running time is dominated by the application of the min-max subset
convolution $s$ times, leading to a total running time of
$\widetilde{O}(2^{\frac{3n}{2}}s)=O\left(2^{\frac{3n}{2}}\mathrm{polylog}(\frac{2^{n}}{\varepsilon})\right)$.

###  D.3 Close Summands Lemma

The following lemma of Bringmann et al. [10] is helpful in the proof for
_close_ summands.

######  Lemma D.4 ([L]emma 8.6).

approx_min_plus and [37, Lemma B.2]] For any
$x,y,q,\varepsilon\in\mathbb{R}_{+}$ with $x+y\geq q/2$ and
$\varepsilon\in(0,1)$ we have:

$x+y\leq\left(\left\lceil\frac{4x}{q\varepsilon}\right\rceil+\left\lceil\frac{4y}{q\varepsilon}\right\rceil\right)\frac{q\varepsilon}{4}\leq(1+\varepsilon)(x+y).$

######  Proof D.5.

The lower-bound follows immediately. To show the upper-bound, note that

$\left(\left\lceil\frac{4x}{q\varepsilon}\right\rceil+\left\lceil\frac{4y}{q\varepsilon}\right\rceil\right)\frac{q\varepsilon}{4}\leq
x+y+2\frac{q\varepsilon}{4}=x+y+\varepsilon\frac{q}{2}\leq(1+\varepsilon)(x+y).$

We now prove Lemma 4.5, which takes care of the _close_ summands case.

See 4.5

######  Proof D.6.

To this end, let us consider Alg. 4. Its correctness can be shown in a similar
way as in Ref. [10] (or equivalently Ref. [37]), namely: Property (i) follows
directly from the lower-bound provided by Lemma D.4. To show property (ii), we
make the following observation: For any $T\subseteq S$ with
$h(S)=f(T)+g(S\setminus T)$ there exists $q$ with $\frac{q}{2}\leq
f(T)+g(S\setminus T)\leq q$. This implies $f(T),g(S\setminus T)\leq q$ and
$\max\\{f(T),g(S\setminus T)\\}\geq\frac{q}{4}$. Now, with the additional
assumption $\frac{f(T)}{g(S\setminus
T)}\in[\frac{\varepsilon}{4},\frac{4}{\varepsilon}]$, we have

$\min\\{f(S),g(S\setminus
T)\\}\geq\frac{\varepsilon}{4}\max\\{f(T),g(S\setminus
T)\\}\geq\frac{\varepsilon q}{16},$

and hence, in the $q$th round, neither $f_{q}(T)$ nor $g_{q}(S\setminus T)$
are set to $\infty$. Finally, using the upper-bound of Lemma D.4, we obtain
$\widetilde{h}(S)\leq(1+\varepsilon)\left(f(T)+g(S\setminus
T)\right)=(1+\varepsilon)h(S)$.

Let us analyze its running time. To this end, let $\alpha_{q}$ be the number
of entries of $f_{q}$ that are not set to $\infty$, i.e., $\alpha_{q}=\\{S\mid
f_{q}(S)<\infty\\}$; define $\beta_{q}$ similarly. We show that the exact min-
sum subset convolution of $f_{q}$ and $g_{q}$ can be performed in time
$O\left(\min\\{\alpha_{q}\beta_{q},\frac{2^{n}}{\varepsilon}\\}\mathrm{polylog}(\frac{2^{n}}{\varepsilon})\right)$
as follows.

First, we analyze lines 7-8. To maintain the intermediate functions $f_{q}$
and $g_{q}$, we use an event queue to skip the rounds with $\alpha_{q}=0$ or
$\beta_{q}=0$, since in such cases the min-sum subset convolution is filled
with $\infty$ and would have been skipped in line 10 anyway. Additionally, we
can perform the transitions $f_{q}\rightarrow f_{q+1}$, $g_{q}\rightarrow
g_{q+1}$, i.e., between two consecutive iterations, in time proportional to
the number of non-$\infty$ entries, i.e., $O(\alpha_{q}+\beta_{q})$, which is
l.e.q. $O(\min\\{\alpha_{q}\beta_{q},\frac{2^{n}}{\varepsilon}\\})$.

There are now two ways to compute the exact convolution of $f_{q}$ and
$g_{q}$. First, naively performing the convolution between the non-$\infty$
entries takes time $O(\alpha_{q}\beta_{q})$: Consider _disjoint_
$T_{1},T_{2}\subseteq[n]$ such that $f_{q}(T_{1})\neq\infty$ and
$g_{q}(T_{2})\neq\infty$. Then, we can update $h_{q}(T_{1}\cup T_{2})$ with
the value of $f_{q}(T_{1})+g_{q}(T_{2})$, if smaller. The second way exploits
the fact that the values in $f_{q}$ and $g_{q}$ are _bounded_. Indeed,
consider the procedure Scale (within Alg. 4) which maps $f(U)$ to
$\left\lceil\frac{4}{\varepsilon q}f(U)\right\rceil$, if $\frac{\varepsilon
q}{16}\leq f(U)\leq q$. This imposes that $f_{q}$ only takes values bounded by
$\left\lceil\frac{4}{\varepsilon}\right\rceil$; analogously for $g_{q}$. We
can hence use the $\widetilde{O}(2^{n}M)$-time algorithm for bounded input, as
described by Björklund et al. [4] (and mentioned several times in our
motivation), by setting
$M=\left\lceil\frac{4}{\varepsilon}\right\rceil$.181818Indeed, this running
time corresponds to that of the FFT-based solution in the sequence setting
[49, Lemma 5.7.2], namely $\widetilde{O}(nW)$. The running time can thus be
bounded by

$\displaystyle\sum_{q}\min\\{\alpha_{q}\beta_{q},2^{n}/\varepsilon\\}\mathrm{polylog}(2^{n}/\varepsilon),$

by using the better of the two ways. As in Ref. [10], we introduce a threshold
$\lambda$ and split the previous sum into two cases w.r.t. $\lambda$, i.e.,
$\beta_{q}\leq\lambda$ and $\beta_{q}>\lambda$. At this point, observe that
the second case can occur at most
$O(\frac{2^{n}}{\lambda}\log\frac{1}{\varepsilon})$ times. To see why this is
the case, consider an entry $f(U)$ for $U\subseteq[n]$. Since $q$ grows
geometrically, there are $O(\log\frac{1}{\varepsilon})$ rounds in which $f(U)$
is not set to $\infty$. Hence, we obtain
$\sum_{q}\alpha_{q}=O(2^{n}\log\frac{1}{\varepsilon})$; similarly,
$\sum_{q}\beta_{q}=O(2^{n}\log\frac{1}{\varepsilon})$. With this observation,
we can bound the running time by

$\displaystyle\left(\displaystyle\sum_{\beta_{q}\leq\lambda}\alpha_{q}\beta_{q}+\displaystyle\sum_{\beta_{q}>\lambda}\frac{2^{n}}{\varepsilon}\right)\mathrm{polylog}(2^{n}/\varepsilon)$
$\displaystyle\leq\left(\lambda\cdot
2^{n}\log\frac{1}{\varepsilon}+\frac{2^{n}}{\varepsilon}\frac{2^{n}}{\lambda}\log\frac{1}{\varepsilon}\right)\mathrm{polylog}(2^{n}/\varepsilon)$
$\displaystyle\leq\left(\lambda\cdot
2^{n}+\frac{(2^{n})^{2}}{\varepsilon\lambda}\right)\mathrm{polylog}(2^{n}/\varepsilon).$

The expression is minimized for
$\lambda=\left(2^{n}/\varepsilon\right)^{1/2}$, yielding the total running
time of $\widetilde{O}(2^{\frac{3n}{2}}/\sqrt{\varepsilon})$.

##  Appendix E Auxiliary Results

In this section, we state for completeness several results from the framework
of Bringmann et al. [10] that we used throughout our paper, along with their
corresponding references.

###  E.1 Distant Covering Lemma

######  Lemma E.1 (Distant Covering [10, Cor. 5.10]).

Given vectors $A,B\in\mathbb{R}^{d}_{+}$ and a parameter $\varepsilon>0$,
there exist vectors
$A^{(1)},\ldots,A^{(s)},B^{(1)},\ldots,B^{(s)}\in\mathbb{R}^{d}_{+}$ with
$s=O(\log d\log\frac{1}{\varepsilon})$ such that

  1. (i)

for all $i,j\in[d]$ and all $l\in[s]$:
$\max\\{A^{(l)}[i],B^{(l)}[j]\\}\geq(1-2\varepsilon)(A[i]+B[j])$, and

  2. (ii)

for all $i,j\in[d]$ if $\frac{A[i]}{B[j]}\not\in[\varepsilon,1/\varepsilon]$
then $\exists l\in[s]$: $\max\\{A^{(l)}[i],B^{(l)}[j]\\}\leq A[i]+B[j]$.

The auxiliary vectors $A^{(1)},\ldots,A^{(s)},B^{(1)},\ldots,B^{(s)}$ can be
computed in time $O(d\log d\log\frac{1}{\varepsilon})$.

##  Appendix F Input Format

For simplicity, we will denote by $n$ the input size corresponding to the
problem. Note that the natural input size for subset convolutions on a subset
lattice of order $k$ is indeed $2^{k}$.

We follow the setup introduced by Bringmann et al. [10]: Input numbers in all
_approximate_ problems are represented in floating-point, while those in
_exact_ problems are represented in the standard bit representation. The
choice of this particular input format is motivated by the use of floating-
point operations in the equivalences of approximate min-sum subset convolution
and exact min-max subset convolution (see Thm. 1.4).

Namely, in the reduction from exact min-max to approximate min-sum, we need to
_exponentiate_ the given numbers. However, under the standard bit
representation, this requires shifting from $O(\log n)$-bit integers to
$\mathrm{poly}(n)$-bit integers. Understandably, this is not efficient enough.
The main observation of Bringmann et al. [10] is that if $m$ is an $O(\log
n)$-bit integer in bit-representation, then one can store $2^{m}$ as a
floating-point number by storing $m$ as the exponent. This implies that the
floating-point number has an $O(\log n)$-bit exponent (and an $O(1)$-bit
mantissa). For the other direction, i.e., from approximate min-sum in
floating-point representation to exact min-max in bit representation, we use
the fact that for exact min-max we can replace the input numbers by their
_ranks_ , yielding $O(\log n)$-bit integers in bit representation [10].

Bit Representation. The standard bit representation is used for the exact min-
max subset convolution. The key observation is that we can replace the actual
input numbers by their _ranks_ , the position in the sorted order of _all_
input numbers (this takes near-linear time and, in our context, does not
modify the time-complexity of the algorithms). This construction ensures that
the numbers are integers in $\\{1,\ldots,\mathrm{polylog}(n)\\}$ and, hence,
take $O(\log n)$ bits.

Floating-Point Representation. As regards the $(1+\varepsilon)$-approximate
problems, we assume that the input is given in floating-point format,
following the setup proposed Bringmann et al. [10]. In particular, if the
input numbers are in the range $[1,M]$, it suffices to store for each input
number $w$ its rounded algorithm $e=\left\lfloor\log_{2}w\right\rfloor$,
requiring $O(\log\log M)$ bits, and an approximation of the mantissa, i.e.,
$w/2^{e}$, requiring only $O(\log\frac{1}{\varepsilon})$ bits, yielding a
total of $O(\log\log M+\log\frac{1}{\varepsilon})$ bits. We refer the reader
to Ref. [10] for more details.