Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #12252 > unrolled thread

Re: Discussion regarding Mr. Diabys algorithm

Started byagentmk.mk@googlemail.com
First post2017-10-05 09:13 -0700
Last post2017-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.


Contents

  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

#12252 — Re: Discussion regarding Mr. Diabys algorithm

Fromagentmk.mk@googlemail.com
Date2017-10-05 09:13 -0700
SubjectRe: 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]


#12253

Fromagentmk.mk@googlemail.com
Date2017-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]


#12254

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-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