Fast Monotone Summation over Disjoint Sets

Petteri Kaski, Mikko Koivisto, Janne Henrik Korhonen

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Abstrakti

We study the problem of computing an ensemble of multiplesums where the summands in each sum are indexed by subsetsof 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, thesum over the values of all subsetsof size $p$ that are {\em disjoint} from the subset of size $q$.We present an arithmetic circuit that, without subtraction, solves the problemusing $O((n^p+n^q)\log n)$ arithmetic gates, all monotone;for constant $p$, $q$ this is within the factor $\log n$ of theoptimal. The circuit design is based on viewingthe summation as a ``set nucleation'' task and using atree-projection approach to implement the nucleation.Applications include improved algorithms for counting heaviest $k$-paths in a weightedgraph, computing permanents of rectangular matrices, and dynamic feature selectionin machine learning.
Alkuperäiskielienglanti
OtsikkoParameterized and Exact Computation : 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings
ToimittajatDimitrios Thilikos, Gerhard Woeginger
Sivumäärä12
KustantajaSpringer-Verlag
Julkaisupäivä2012
Sivut159-170
ISBN (painettu)978-3-642-33292-0
ISBN (elektroninen)978-3-642-33293-7
DOI - pysyväislinkit
TilaJulkaistu - 2012
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
Tapahtuma7th International Symposium on Parameterized and Exact Computation (IPEC 2012) - Ljubljana, Slovenia
Kesto: 12 syyskuuta 201214 syyskuuta 2012

Julkaisusarja

NimiLecture Notes in Computer Science
KustantajaSpringer Berlin Heidelberg
Vuosikerta7535
ISSN (painettu)0302-9743

Lisätietoja


Volume:
Proceeding volume:

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä