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.↵
↵
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.↵
