kirjuri's blog

Help with a problem of optimal partitioning
By kirjuri, history, 7 years ago, In English

Consider the following problem:

We are given N sets {S1, ..., SN} of integers, with 1 ≤ |Si| ≤ 16 (i.e. no set is empty or has more than 16 elements) and . 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 ≤ 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.

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I assume the sets are distinct, right? Also, more importantly, how big is N? I assume that given 16 is a small constant we should look for an exponential complexity in 16, K

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can assume distinct sets (I don't think any generality is lost). You can assume 1 ≤ N ≤ 100000.

    So, let me give you some insight to the motivation of the problem. Feel free to not read this part if not interested: I'm toying with some OpenGL and 3D graphics for some game engine. In order to implement vertex skinning for animations, I receive the data to be drawn as a collection of N triangles. The ith triangle is associated with a set Si of joints/bones which affect each of the vertices of the triangle. The total number of joints/bones of the model is relatively small (~60). Each joint has an associated joint matrix. No more than K different joints can affect a vertex (this is guaranteed by the export format). In order to draw the vertices, you must be pass to the vertex shader each vertex along with the joint matrices of the joints that affect that particular vertex. Since the joint matrices are passed as a uniform array to the vertex shader, you can't have too many of this matrices because of the memory limitations of the GPU. So, what you can do to solve this issue is to partition the original model (set of triangles) into several subsets such that the vertices in every subset are affected overall by a small number of joints (ideally K); however, you want as few partitions as possible since each of the partitions will generate a draw call. And then that's why I was wondering about the optimal way to partition the triangles into a minimum number of partitions such that each partition contains only a limited number of joints. Not sure if all that made a lot of sense, but anyway.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kirjuri (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

After generating some test cases, it appears that there is not a sorting criteria that works in general. Consider the following case:

N=5, K=8
S1={4,5,8}
S2={5,10,11}
S3={1,2,5,11}
S4={3,4,7,8,11,12}
S5={4,5,7,9,10,11}

The optimal solution is to split in two: {S1,S2,S4} and {S3,S5}.

Maybe this reduces to NP somehow? (looks like clique cover)

Any ideas for solution are appreciated!

→ Reply