Help with a problem of optimal partitioning
Разница между en1 и en2, 38 символ(ов) изменены
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.↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский 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 Английский kirjuri 2018-02-14 10:40:38 996 Initial revision (published)