An output-sensitive Algorithm to partition a Sequence of Integers into Subsets with equal Sums
Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 2
Voir la notice de l'article provenant de la source Episciences
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$.
@article{DMTCS_2018_20_2_a18,
author = {B\"uchel, Alexander and Gille{\ss}en, Ulrich and Witt, Kurt-Ulrich},
title = {An output-sensitive {Algorithm} to partition a {Sequence} of {Integers} into {Subsets} with equal {Sums}},
journal = {Discrete mathematics & theoretical computer science},
publisher = {mathdoc},
volume = {20},
number = {2},
year = {2018},
doi = {10.23638/DMTCS-20-2-18},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-2-18/}
}
TY - JOUR AU - Büchel, Alexander AU - Gilleßen, Ulrich AU - Witt, Kurt-Ulrich TI - An output-sensitive Algorithm to partition a Sequence of Integers into Subsets with equal Sums JO - Discrete mathematics & theoretical computer science PY - 2018 VL - 20 IS - 2 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-2-18/ DO - 10.23638/DMTCS-20-2-18 LA - en ID - DMTCS_2018_20_2_a18 ER -
%0 Journal Article %A Büchel, Alexander %A Gilleßen, Ulrich %A Witt, Kurt-Ulrich %T An output-sensitive Algorithm to partition a Sequence of Integers into Subsets with equal Sums %J Discrete mathematics & theoretical computer science %D 2018 %V 20 %N 2 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-2-18/ %R 10.23638/DMTCS-20-2-18 %G en %F DMTCS_2018_20_2_a18
Büchel, Alexander; Gilleßen, Ulrich; Witt, Kurt-Ulrich. An output-sensitive Algorithm to partition a Sequence of Integers into Subsets with equal Sums. Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 2. doi: 10.23638/DMTCS-20-2-18
Cité par Sources :