Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #12252 > unrolled thread
| Started by | agentmk.mk@googlemail.com |
|---|---|
| First post | 2017-10-05 09:13 -0700 |
| Last post | 2017-10-08 00:42 +0100 |
| Articles | 3 — 2 participants |
Back to article view | Back to comp.theory
This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by
below is the oldest one visible, not the original post.
Re: Discussion regarding Mr. Diabys algorithm agentmk.mk@googlemail.com - 2017-10-05 09:13 -0700
Re: Discussion regarding Mr. Diabys algorithm agentmk.mk@googlemail.com - 2017-10-07 04:11 -0700
Re: Discussion regarding Mr. Diabys algorithm Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-10-08 00:42 +0100
| From | agentmk.mk@googlemail.com |
|---|---|
| Date | 2017-10-05 09:13 -0700 |
| Subject | Re: Discussion regarding Mr. Diabys algorithm |
| Message-ID | <fbb80586-2c8c-4934-bf16-b287431a1cf3@googlegroups.com> |
The number of feasible solutions has nothing to do with the number of constraints!!. In fact, less constraints often lead to more feasible solutions. This is obvious even if you are no LP expert.
[toc] | [next] | [standalone]
| From | agentmk.mk@googlemail.com |
|---|---|
| Date | 2017-10-07 04:11 -0700 |
| Message-ID | <c562b58f-8f43-45eb-855d-06e17348f29c@googlegroups.com> |
| In reply to | #12252 |
Another point is the understanding of the flow in the Diaby algorithm. It took me some weeks to get the point, the model is quite counter-intuitive and I am no LP expert at all. The mistake many of the participants make here is to interpret the flow wrong. The flow is not comparable to a "river". You have to imagine rather all flows separately, starting with value '1' in each city. These flows can 'distribute' in infinitely many ways, but have only finitely many OPTIMAL TSP paths. Linear Programming is powerful enough to find these optimal solutions polynomially. Another crucial trick is to model the flow in the constraints and not with (then too many) variables. So the polynomiality is achieved. Quite ingenious I think, and suprising, I would have bet that P <> NP. Now I am SURE that P=NP.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2017-10-08 00:42 +0100 |
| Message-ID | <877ew64j9q.fsf@bsb.me.uk> |
| In reply to | #12253 |
agentmk.mk@googlemail.com writes: > Another point is the understanding of the flow in the Diaby > algorithm. It took me some weeks to get the point, And now you are replying to yourself in a thread that is more than a decade old. <snip> > ... Now I am SURE that P=NP. You may be but the Clay Mathematics Institute is not! -- Ben.
[toc] | [prev] | [standalone]
Back to top | Article view | comp.theory
csiph-web