We can do convolution in $O(nlgn)$ for plus/multiply polynomials with fft. However the approach doesn't seem very generalisable to rings in general. Has there been any progress over the naive $O(n^2)$ convolution for the max/plus ring?

up vote 9 down vote accepted

There is a more general question on mathoverflow.

I asked a similar question on CS.SE. jbapple provided a good answer. To quote

"Necklaces, Convolutions, and X+Y", By Bremner et al. shows a $O\left(\frac{n^2(\lg \lg n)^3}{\lg^2 n}\right)$ algorithm for this problem on the real RAM and a $O(n \sqrt{n})$ algorithm in the nonuniform linear decision tree model.

Any improvement to this bound will shed light to a few tough open problems like sorting $X+Y$ and all pair shortest path.

If one of the function is convex/concave, we can solve the problem in $O(n\log n)$ time. See "Speeding up Dynamic Programming", By Eppstein et al..

  • Thank you. I also enjoyed reading about this on the mathoverflow link. – Thomas Ahle Nov 26 '13 at 17:13
  • I'm wondering if "monotonically increasing" might be a useful property. – Thomas Ahle Nov 26 '13 at 17:16
  • 1
    The first problem the authors tries to solve in the Necklaces paper is monotonically increasing. It's likely there is no known algorithm that performs better than the general case. – Chao Xu Nov 26 '13 at 17:41

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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