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

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

t g e q n

and

k c d o t t = n + 1 c h o o s e 2

, the algorithm partitions the elements of the set

I_{n} = 1, l d o t s, n

into

k

mutually disjoint subsets

T_{j}

such that

c u p_{j = 1}^{k} T_{j} = I_{n}

and

s u m_{x i n T_{j}} x = t

for each

j i n 1, 2, l d o t s, k

. The algorithm needs

m a t h c a l O (n c d o t (f r a c n 2 k + l o g f r a c n (n + 1) 2 k))

steps to insert the

n

elements of

I_{n}

into the

k

sets

T_{j}

.

Recommendations

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)