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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我现在试图证明对某个分布问题找到某种最好的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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我现在试图证明对某个分布问题找到某种最好的divide and conquer 策略是np hard的。 : 可能考虑哪些个np complete problem?谁有类似的规约经验?thanx.
|