Fourier meets M\

@misc{citeulike:959693, abstract = {We present a fast algorithm for the subset convolution problem: given functions f and g defined on the lattice of subsets of an n-element set N, compute their subset convolution f*g, defined for all S\subseteq N by (f * g)(S) = \sum\_{T \subseteq S}f(T) g(S\setminus T), where addition and multiplication is carried out in an arbitrary ring. Via M\"{o}bius transform and inversion, our algorithm evaluates the subset convolution in O(n^2 2^n) additions and multiplications, substantially improving upon the straightforward O(3^n) algorithm. Specifically, if the input functions have an integer range {-M,-M+1,...,M}, their subset convolution over the ordinary sum-product ring can be computed in O^*(2^n log M) time; the notation O^* suppresses polylogarithmic factors. Furthermore, using a standard embedding technique we can compute the subset convolution over the max-sum or min-sum semiring in O^*(2^n M) time. To demonstrate the applicability of fast subset convolution, we present the first O^*(2^k n^2 + n m) algorithm for the minimum Steiner tree problem in graphs with n vertices, k terminals, and m edges with bounded integer weights, improving upon the O^*(3^k n + 2^k n^2 + n m) time bound of the classical Dreyfus-Wagner algorithm. We also discuss extensions to recent O^*(2^n)-time algorithms for covering and partitioning problems (Bj\"{o}rklund and Husfeldt, FOCS 2006; Koivisto, FOCS 2006).}, author = {Bj\örklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko }, citeulike-article-id = {959693}, eprint = {cs.DS/0611101}, keywords = {algorithm, fft, stoc}, month = {Nov}, posted-at = {2007-02-21 08:19:59}, priority = {2}, title = {Fourier meets M}, url = {http://arxiv.org/abs/cs.DS/0611101}, year = {2006} }

TY - ELEC ID - citeulike:959693 L3 - citeulike-article-id:959693 TI - Fourier meets M\ N2 - We present a fast algorithm for the subset convolution problem: given functions f and g defined on the lattice of subsets of an n-element set N, compute their subset convolution f*g, defined for all S\subseteq N by (f * g)(S) = \sum_{T \subseteq S}f(T) g(S\setminus T), where addition and multiplication is carried out in an arbitrary ring. Via M\"{o}bius transform and inversion, our algorithm evaluates the subset convolution in O(n^2 2^n) additions and multiplications, substantially improving upon the straightforward O(3^n) algorithm. Specifically, if the input functions have an integer range {-M,-M+1,...,M}, their subset convolution over the ordinary sum-product ring can be computed in O^*(2^n log M) time; the notation O^* suppresses polylogarithmic factors. Furthermore, using a standard embedding technique we can compute the subset convolution over the max-sum or min-sum semiring in O^*(2^n M) time. To demonstrate the applicability of fast subset convolution, we present the first O^*(2^k n^2 + n m) algorithm for the minimum Steiner tree problem in graphs with n vertices, k terminals, and m edges with bounded integer weights, improving upon the O^*(3^k n + 2^k n^2 + n m) time bound of the classical Dreyfus-Wagner algorithm. We also discuss extensions to recent O^*(2^n)-time algorithms for covering and partitioning problems (Bj\"{o}rklund and Husfeldt, FOCS 2006; Koivisto, FOCS 2006). KW - algorithm KW - fft KW - stoc AU - Björklund, Andreas AU - Husfeldt, Thore AU - Kaski, Petteri AU - Koivisto, Mikko PY - 2006/Nov/21/ UR - http://arxiv.org/abs/cs.DS/0611101 ER -