Alexander Büchel ; Ulrich Gilleßen ; Kurt-Ulrich Witt - An output-sensitive Algorithm to partition a Sequence of Integers into Subsets with equal Sums

dmtcs:4994 - Discrete Mathematics & Theoretical Computer Science, January 24, 2019, vol. 20 no. 2 - https://doi.org/10.23638/DMTCS-20-2-18
An output-sensitive Algorithm to partition a Sequence of Integers into Subsets with equal SumsArticle

Authors: Alexander Büchel ; Ulrich Gilleßen ; Kurt-Ulrich Witt

    We present a polynomial time algorithm, which solves a nonstandard Variation of the well-known PARTITION-problem: Given positive integers $n, k$ and $t$ such that $t \geq n$ and $k \cdot t = {n+1 \choose 2}$, the algorithm partitions the elements of the set $I_n = \{1, \ldots, n\}$ into $k$ mutually disjoint subsets $T_j$ such that $\cup_{j=1}^k T_j = I_n$ and $\sum_{x \in T_{j}} x = t$ for each $j \in \{1,2, \ldots, k\}$. The algorithm needs $\mathcal{O}(n \cdot ( \frac{n}{2k} + \log \frac{n(n+1)}{2k} ))$ steps to insert the $n$ elements of $I_n$ into the $k$ sets $T_j$.


    Volume: vol. 20 no. 2
    Section: Discrete Algorithms
    Published on: January 24, 2019
    Accepted on: December 4, 2018
    Submitted on: November 27, 2018
    Keywords: Mathematics - Combinatorics,Computer Science - Data Structures and Algorithms

    Consultation statistics

    This page has been seen 651 times.
    This article's PDF has been downloaded 477 times.