Fast Monotone Summation over Disjoint Sets

DOI10.1007/978-3-642-33293-7_16MaRDI QIDQ4899250zbMATH OpenOpenAlexFDO

Authors Petteri Kaski, Mikko Koivisto, Janne H. Korhonen

Publication date 7 January 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.0554

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Nonnumerical algorithms (68W05)

Abstract: 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)logn)$ arithmetic gates, all monotone; for constant $p$, $q$ this is within the factor $logn$ 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.

Recommendations

• Fast monotone summation over disjoint sets
• Discretized sum-product for large sets
• Computing efficiently the nondominated subset of a set sum
• Monochromatic sumsets
• scientific article; zbMATH DE number 3878935
• Multifold sumsets and fast decreasing of concentration functions
• scientific article; zbMATH DE number 742759
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Faster min-plus product for monotone instances

Cited in

(2)

• Fast monotone summation over disjoint sets
• Exact Parameterized Multilinear Monomial Counting via k-Layer Subset Convolution and k-Disjoint Sum

This page was built for publication: Fast Monotone Summation over Disjoint Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4899250)