Max-convolution through numerics and tropical geometry

06/20/2023
by   Taylor Brysiewicz, et al.
0

The maximum function, on vectors of real numbers, is not differentiable. Consequently, several differentiable approximations of this function are popular substitutes. We survey three smooth functions which approximate the maximum function and analyze their convergence rates. We interpret these functions through the lens of tropical geometry, where their performance differences are geometrically salient. As an application, we provide an algorithm which computes the max-convolution of two integer vectors in quasi-linear time. We show this algorithm's power in computing adjacent sums within a vector as well as computing service curves in a network analysis application.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset