Help with a problem of optimal partitioning
Difference between en1 and en2, changed 38 character(s)
Consider the following problem:↵

We are given $N$ sets ${S_1,...,S_N}$ of integers, with $1 \le |S_i| \le 16$ (i.e. no set is empty or has more than 16 elements)
 and $|S_1 \cup ... \cup S_N| \le 100$.↵
We want to partition the given sets into the minimum number of partitions such that the number of elements in the union of all sets in any partition doesn't exceed given constant $K \le 16$.↵

Is there a way to sort the sets such that the partitions of the optimal solution are contiguous? (in which case a DP solution to the original problem follows). How to prove such properties for other partition cost functions in general?↵

Thanks!↵

P.S.: I found this: https://books.google.co.uk/books?id=PD3ICgAAQBAJ&pg=PA293&lpg=PA293&dq=Partition+Problems+over+Single-Parameter+Spaces:+Combinatorial+Approach&source=bl&ots=FdNvNpE_96&sig=MQOnuezKZfMUbyACjqZq5adR_rM&hl=en&sa=X&ved=0ahUKEwjrj67K7qTZAhVkJMAKHXW0APIQ6AEILjAA#v=onepage&q&f=false↵
but unfortunately is not available in full.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English kirjuri 2018-02-14 13:04:51 38 Tiny change: 'K \le 16$.\n\nIs t' -> 'K \le 16$. Also, $sum(|S_i|) <= 100$.\n\nIs t'
en1 English kirjuri 2018-02-14 10:40:38 996 Initial revision (published)