Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Fast Monotone Summation over Disjoint Sets
verfasst von : Petteri Kaski, Mikko Koivisto, Janne H. Korhonen
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the problem of computing an ensemble of multiple sums where the summands in each sum are indexed by subsets of size
p
of an
n
-element ground set. More precisely, the task is to compute, for each subset of size
q
of the ground set, the sum over the values of all subsets of size
p
that are
disjoint
from the subset of size
q
. We present an arithmetic circuit that, without subtraction, solves the problem using
O
((
n
p
+
n
q
)log
n
) arithmetic gates, all monotone; for constant
p
,
q
this is within the factor log
n
of the optimal. The circuit design is based on viewing the summation as a “set nucleation” task and using a tree-projection approach to implement the nucleation. Applications include improved algorithms for counting heaviest
k
-paths in a weighted graph, computing permanents of rectangular matrices, and dynamic feature selection in machine learning.