In this talk, we present two fully polynomial-time approximation schemes (FPTAS) for Subset Sum Ratio. They run in time near O(n^3 / eps) and O(n / eps^2), respectively, improving upon the previously known O(n^4 / eps) bound. The algorithms are based on dynamic programming and approximating (max, +)-convolutions in a divide and conquer fashion.
--------------------
Join Zoom Meeting
Meeting ID: 527 278 8807
Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.