Re: Discussion regarding Mr. Diabys algorithm

A.L. wrote:
On 14 Nov 2006 08:44:50 -0800, moustapha.diaby@xxxxxxxxxxxxxxxxxx
wrote:


At the risk of repeating myself both Moews' and Hofman's claims are
quite incorrect. ...


Could you FINALLY provide scientific arguments that they are wrong?
Please show exactly what parts of their reasoning are questionable.

A.L.


A.L.:

As to Moews, that is quite simple: Yannakakis's results pertain to the
TSP polytope. I deal with the assignment polytope, which is a
completely different polytope. A key error in Moews' claim is that he
assumes that after city 1 has been "dropped" from consideration (by
being fixed as the end and starting points of travel) the travels over
the remaining cities is still a TSP. But that is not the case in my
model. That remaining problem has the (mathematical programming)
structure of the standard assignment problem: Among other things, there
is no need to return to a starting point, and that makes the *huge*
difference...

As to Hoffman, I will make a more detailed document public when it is
ready, as I said previously.

//MD

.

Relevant Pages

  • Re: P=NP: Linear Programming Formulation of the TSP
    ... David Moews wrote: ... constraints you are adding to the original math prog problem are ... then the new polytope is not the same as the original one. ...
    (comp.theory)
  • Re: P=NP: Linear Programming Formulation of the TSP
    ... > I believe I understand what Dr. Moews is trying to do perfectly. ... then the new polytope is not the same as the original one. ... >>>charaterize the original polytope in terms of these constraints as ... >>>want to identify and discard redundent variables and constraints ...
    (comp.theory)
  • Re: P=NP: Linear Programming Formulation of the TSP
    ... Dr. Moews: I am busy with exams, grading, etc. at this time. ... That is clearly not what Yannakakis says. ... Either the constraints developed by Moews using his xvariables ... then the new polytope is not the same as the original one. ...
    (comp.theory)
  • A reply to Moews on Diaby contradicting Yannakakis
    ... A Response to Moews on: ... it is ALWAYS possible to add any number of redundent variables ... Either the constraints developed by Moews using his xvariables ... then the new polytope is not the same as the original one. ...
    (comp.theory)