1
$\begingroup$

Is there an algorithm to multiply two polynomials with coefficients in the max-plus semiring $(\mathbb{Z}\cup\{-\infty\}, \max, +)$ which is faster than the trivial one? I'm interested in the coefficients of the product, so I can't ignore the differences between two polynomials which specify the same function. This makes some nice results like the fundamental theorem of algebra (for the tropical semiring) not immediately useful.

The obvious candidates like Karatsuba don't work (the Grothendieck group of $(\mathbb{Z}\cup\{-\infty\}, \max)$ is trivial, so you can't extend the semiring to a ring), but I also haven't been able to come up with a reason why it shouldn't possible.

You can assume the coefficients are monotonically increasing if it makes the algorithm easier/faster.

Improve this question
$\endgroup$
2
  • $\begingroup$ I believe that the ordered property might allow for a $O(n+m)$ algorithm. You can discover it by considering two polynomials ($\sum \alpha_i x^i, \sum \beta_j x^j$) with ordered coefficients and drawing a table where the rows are the coefficients of $(\sum \alpha_i x^i) \cdot \beta_j x^j$ (the table columns should be $x^{2n},...,x^0$). Now notice that you can precompute the prefix sums of $\alpha_n,...,\alpha_0,$ and $\beta_n,...,\beta_0$. Notice that the columns will always be made of a subarray of $\alpha$ and a subarray of $\beta$ thus you can use the prefix sums to compute them. $\endgroup$
    – plshelp
    Mar 13 at 21:40
  • $\begingroup$ If you use binary search for each row to determine the index at which $\beta_j > \alpha_i$ the algorithm takes $O((n+m)\log(n))$, but since the $\beta$ and $\alpha$ are ordered, you can use the two-pointer method for that. $\endgroup$
    – plshelp
    Mar 13 at 21:44

1 Answer 1

Reset to default
1
$\begingroup$

The problem is computing the array $C$ defined as $C_i = \max_{j+k=i} (A_j + B_k)$ given arrays $A$ and $B$. It is called the max-plus convolution, or MaxConv problem. Note that the equivalent min-plus convolution problem is also used in literature.

There is a sub-quadratic time reduction from the 3SUM problem to this problem [1]. The popular 3SUM conjecture states there is no truly sub-quadratic ($O(n^{2-\epsilon})$ for $\epsilon > 0$) algorithm for the 3SUM problem. Therefore, no truly sub-quadratic algorithm is known for the max-plus convolution problem.

If the arrays are monotone, and all values are integers bounded by $O(n)$, subquadratic algorithms are known. Recently, Chi et al. [2] presented an $\tilde{O}(n^{1.5})$-time algorithm for this problem. Note that "monotonically increasing" and "monotonically decreasing" variants are equivalent because we can reverse both arrays as well as the resulting array.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.