3 papers
cs.DS2024
Approximate Min-Sum Subset Convolution
Mihail Stoian
Exponential-time approximation has recently gained attention as a practical way to deal with the bitter NP-hardness of well-known optimization problems. We study for the first time…
cs.DS2024
TSP Escapes the Curse
Mihail Stoian
The dynamic programming solution to the traveling salesman problem due to Bellman, and independently Held and Karp, runs in time , with no improvement in the last sixty…
cs.DS2024
Did Fourier Really Meet Möbius? Fast Subset Convolution via FFT
Mihail Stoian
In their seminal work on subset convolution, Björklund, Husfeldt, Kaski and Koivisto introduced the now well-known -time evaluation of the subset convolution in the su…