h***n
发帖数: 276 | 1 I happen to think about a problem which is similar to the class of set-cover
problems. Now I describe such a problem as follows:
Given:
- the set to be covered X={x1, x2, x3, ...} and each element of the set X has
the equal weight (say 1 here)
- the collection of set covers {S1, S2, ...}
(below are some new constraints)
- the sets are organized into groups
- there is an upper-bound for the number of sets which can be chosen from each
group, say ci
The problem is how to pick up a collection of se | y***s
发帖数: 294 | 2 very obvious, from 3-SAT, where each group has a size of 2 and you can
only choose 1.
PS: Actually, proving the simplified special case has been enough for
proving hardness results.
【在 h***n 的大作中提到】
: I happen to think about a problem which is similar to the class of set-cover
: problems. Now I describe such a problem as follows:
: Given:
: - the set to be covered X={x1, x2, x3, ...} and each element of the set X has
: the equal weight (say 1 here)
: - the collection of set covers {S1, S2, ...}
: (below are some new constraints)
: - the sets are organized into groups
: - there is an upper-bound for the number of sets which can be chosen from each
: group, say ci
| m****h
发帖数: 261 | 3 As Yepes said, the problem you defined contains the "Maximum Coverage Problem"
as a special case, and is therefore NP-hard. hehe.
has
each
the
"Maximum
larger
【在 h***n 的大作中提到】
: I happen to think about a problem which is similar to the class of set-cover
: problems. Now I describe such a problem as follows:
: Given:
: - the set to be covered X={x1, x2, x3, ...} and each element of the set X has
: the equal weight (say 1 here)
: - the collection of set covers {S1, S2, ...}
: (below are some new constraints)
: - the sets are organized into groups
: - there is an upper-bound for the number of sets which can be chosen from each
: group, say ci
| r****c
发帖数: 2585 | 4 faint
you have alrady proven the np-hardness, and the log algorithm still works with
minor modification
set-cover
has
each
the
"Maximum
larger
should
【在 y***s 的大作中提到】
: very obvious, from 3-SAT, where each group has a size of 2 and you can
: only choose 1.
: PS: Actually, proving the simplified special case has been enough for
: proving hardness results.
|
|
