DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Computational Aspects of Ordered Integer Partitions with Bounds

Glück, Roland and Köppl, Dominik (2020) Computational Aspects of Ordered Integer Partitions with Bounds. Algorithmica, 82, pages2955-2984. Springer Nature. doi: 10.1007/s00453-020-00713-7. ISSN 0178-4617.

Full text not available from this repository.

Official URL: https://link.springer.com/article/10.1007/s00453-020-00713-7


This paper is dedicated to the counting problem of writing an integer number $z$ as a sum of an ordered sequence of $n$ integers from $n$ given intervals, i.e., counting the number of configurations $(z_1,…,z_n)$ with $z=z_1+...+z_n$ for zi\in[x_i,y_i] with integers x_i and y_i and 1\leq i\leq n. We show an algorithm computing this number in $\bigo(n_z lg n)$ average time, and a data structure computing this number in $\bigo(n)$ time, independently of $z$. The data structure is constructed in \bigo(2^nn^3)$ time. Its construction algorithm only depends on the intervals $[x_i,y_i] (1\leq i\leq n)$. This construction algorithm can be parallelized with $p=\bigo(n^3)$ processors, yielding $\bigo(2^n\frac{n^3}{p})$ construction time with high probability.

Item URL in elib:https://elib.dlr.de/137434/
Document Type:Article
Title:Computational Aspects of Ordered Integer Partitions with Bounds
AuthorsInstitution or Email of AuthorsAuthor's ORCID iDORCID Put Code
Glück, RolandUNSPECIFIEDhttps://orcid.org/0000-0001-7909-1942UNSPECIFIED
Köppl, DominikUNSPECIFIEDhttps://orcid.org/0000-0002-8721-4444UNSPECIFIED
Date:8 May 2020
Journal or Publication Title:Algorithmica
Refereed publication:Yes
Open Access:No
Gold Open Access:No
In ISI Web of Science:Yes
Page Range:pages2955-2984
Publisher:Springer Nature
Keywords:Integer Partition, Bounds, Algorithms, Combinatorics
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Aeronautics
HGF - Program Themes:other
DLR - Research area:Aeronautics
DLR - Program:L - no assignment
DLR - Research theme (Project):L - no assignment
Location: Augsburg
Institutes and Institutions:Institute of Structures and Design > Automation and Production Technology
Deposited By: Glück, Dr. Roland
Deposited On:13 Nov 2020 14:08
Last Modified:20 Oct 2023 09:37

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.