this optimization problem, I am working on, is kind of making me crazy. ;)
Given is a list o
of sets (with finite cardinality) of strictly positive integer values (Z>0), e.g.:
o_without_sizes =
[ {1, 2, 3, 4}
, {5, 6}
, {2, 3, 4, 5}
, {5, 6, 7}
, {7, 8}
. {9} ]
Every set has a name n
(also in Z>0, but only for identification) and a fixed independent size value s
(also in Z>0), e.g.:
type O = [(Name, Size, Values)]
o =
[ (1, 2, {1, 2, 3, 4})
, (2, 1, {5, 6})
, (3, 2, {2, 3, 4, 5})
, (4, 3, {5, 6, 7})
, (5, 2, {7, 8})
. (6, 1, {9}) ]
These sets are to be combined to unions b
of a maximum size value sum h (>= max s, that means that no set has a size making it too big to fit into a single union)
, e.g. 4.
The goal is to find the b
so that the sum of cadinalities of the unions in it is as small as possible.
here is a bad b
:
size: 3, cardinality: 6, sets: [1,2] , values: [1,2,3,4,5,6]
size: 2, cardinality: 4, sets: [3] , values: [2,3,4,5]
size: 3, cardinality: 3, sets: [4] , values: [5,6,7]
size: 3, cardinality: 3, sets: [5,6] , values: [7,8,9]
cardinality sum: 16
and the optimum b
for this example:
size: 4, cardinality: 5, sets: [3,1] , values: [1,2,3,4,5]
size: 4, cardinality: 3, sets: [2,4] , values: [5,6,7]
size: 3, cardinality: 3, sets: [5,6] , values: [7,8,9]
cardinality sum: 11
Until now I only implemented a naive brute force solution (Haskell code): http://lpaste.net/7204008959806537728
I was hoping to find a dynamic programming solution like it exists for the (Z>0) 0-1 knapsack problem, but did not yet succeed. Is my problem perhaps NP-hard? If so, is it many-one-reducible to SAT or something? Or is there a good approximation?
Of course, if there exists a known efficient optimal algorithm, it would be awesome if you could enlighten me. :)
h
(> max s
)". Can you elaborate? Perhaps split that into two sentences, and define all phrases bebefore using them? What's a "maximum size value sum"? What'sh
? What do you mean by> max s
? In particular: how does the size of a union of sets depend upon the size of the individual sets? $\endgroup$