d******y
发帖数: 1039 | 1 我现在试图证明对某个分布问题找到某种最好的divide and conquer 策略是np hard的。
可能考虑哪些个np complete problem？谁有类似的规约经验？thanx. |
s***t
发帖数: 113 | 2 I would recommend you take a look at the Appendix of Garey & Johnson. The
NP-complete problem therein may offer you some hints.
。
【在 d******y 的大作中提到】
: 我现在试图证明对某个分布问题找到某种最好的divide and conquer 策略是np hard的。
: 可能考虑哪些个np complete problem？谁有类似的规约经验？thanx.
|
d******y
发帖数: 1039 | 3 thanks.I have already taken a look on those examples before posting this. The
problem that bothers me is that this divide and conquer scheme has a structure
inside,i.e.,geometrical position.
【在 s***t 的大作中提到】
: I would recommend you take a look at the Appendix of Garey & Johnson. The
: NP-complete problem therein may offer you some hints.
:
: 。
|
s***t
发帖数: 113 | |
d******y
发帖数: 1039 | 5 have you ever read some np-hard proof related to divide and conquer? if so,
please give me a link or sth. thanks.
【在 s***t 的大作中提到】
: The
: structure
|
s***t
发帖数: 113 | 6 There may be some mistake in your comment: NP-completeness is the property
of the problem itself, and it is not dependent upon what algorithm you are
using.
I think you are talking about the complexity of your algorithm. If so, you
need to look at some algorithm analysis book to gain some ideas.
【在 d******y 的大作中提到】
: have you ever read some np-hard proof related to divide and conquer? if so,
: please give me a link or sth. thanks.
|
d******y
发帖数: 1039 | 7 I mean the nature of this problem,i.e., finding the optimal divide and conquer
scheme is NP-hard. Sorry for comfusing. :)
【在 s***t 的大作中提到】
: There may be some mistake in your comment: NP-completeness is the property
: of the problem itself, and it is not dependent upon what algorithm you are
: using.
: I think you are talking about the complexity of your algorithm. If so, you
: need to look at some algorithm analysis book to gain some ideas.
|
s***t
发帖数: 113 | 8 then try keywords like clustering or grouping. Maybe there are some links to
known results.
conquer
【在 d******y 的大作中提到】
: I mean the nature of this problem,i.e., finding the optimal divide and conquer
: scheme is NP-hard. Sorry for comfusing. :)
|
s*****t
发帖数: 737 | 9 这个可不好说啊。不过最终还是规约到图论问题去解决。
。
【在 d******y 的大作中提到】
: 我现在试图证明对某个分布问题找到某种最好的divide and conquer 策略是np hard的。
: 可能考虑哪些个np complete problem？谁有类似的规约经验？thanx.
|
