Min sum subset convolution solved below three to the n barrier
Truly Sub-$3^n$ Min-Sum Subset Convolution and Join Ordering
Data Structures and AlgorithmsDatabases
Summary
Min-sum subset convolution is a mathematical problem important in computing and database queries. The authors show it can be transformed into another matrix multiplication problem and solved faster than before. Using a recent breakthrough algorithm for matrix multiplication, they reduce the exponential running time from about 3 to the power of n down to slightly less than 3 to the power of n. This improvement also speeds up determining the best order to join tables in a database query.
What this means in practice
- •For database engineers: Optimize the order of joining tables in complex queries faster with a new algorithm running below the previous 3^n time barrier.
- •For algorithm developers: Implement faster exact algorithms for min-sum subset convolution to improve performance in combinatorial optimization tasks.
Authors
Mihail Stoian
Abstract
We present a deterministic reduction from min-sum subset convolution to min-plus matrix product. We show that if the min-plus product of two $D\times D$ matrices with $β$-bit integer entries can be computed in $D^{3-δ}\operatorname{poly}(β,\log D)$ time for a fixed rational $0<δ<1$, then min-sum subset convolution on an $n$-element universe can be solved in $(2+2^{-δ})^n 2^{O(\sqrt n\log(n+1))}\operatorname{poly}(n,β)$ time. Instantiating this reduction with the recent breakthrough on subcubic min-plus matrix product by Alman and Vassilevska Williams gives a Las Vegas algorithm with expected running time $O^*(2.9987^n)$ and a deterministic algorithm with running time $O^*(2.9997^n)$, strictly breaking the longstanding $3^n$ computational barrier. Notably, these speedups translate directly to database query optimization, yielding the same expected and deterministic running-time bounds for join ordering under the $C_{\mathrm{out}}$ cost function.