An output-sensitive Algorithm to partition a Sequence of Integers into Subsets with equal Sums

DOI10.23638/DMTCS-20-2-18zbMATH Open1411.05021arXiv1811.04014MaRDI QIDQ5377219FDOQ5377219

A. Buchel, Kurt-Ulrich Witt, Ulrich Gilleßen

Publication date: 23 May 2019

Abstract: 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 $tgeqn$ and $kcdott=n+1choose2$, the algorithm partitions the elements of the set $I_n=1,ldots,n$ into $k$ mutually disjoint subsets $T_j$ such that $cu{p}_{j=1}^k{T}_j=I_n$ and $su{m}_{xin{T}_j}x=t$ for each $jin1,2,ldots,k$. The algorithm needs $mathcalO(ncdot(fracn2k+logfracn(n+1)2k))$ steps to insert the $n$ elements of $I_n$ into the $k$ sets $T_j$.

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

zbMATH Keywords

set partition problemcutting sticks problem

Mathematics Subject Classification ID

Partitions of sets (05A18) Elementary theory of partitions (11P81)

   Recommendations

• An algorithm for partitioning an integernas a sum ofkpositive integers 👍 👎
• Partition of a set of integers into subsets with prescribed sums 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• An efficient representation of partitions of integers 👍 👎
• Title not available (Why is that?) 👍 👎
• Optimal Partitioning of Sequences 👍 👎
• Title not available (Why is that?) 👍 👎
• An approximating polynomial algorithm for a sequence partitioning problem 👍 👎
• An exact algorithm for the subset sum problem 👍 👎

This page was built for publication: An output-sensitive Algorithm to partition a Sequence of Integers into Subsets with equal Sums

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